數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告：設(shè)計(jì)一個(gè)演示用運(yùn)算優(yōu)先法對算數(shù)表達(dá)式求值過程的程序

1、.實(shí)習(xí)報(bào)告題目：設(shè)計(jì)一個(gè)演示用運(yùn)算優(yōu)先法對算數(shù)表達(dá)式求值過程的程序。班級(jí)：姓名：學(xué)號(hào)：完成日期：一、需求分析1 建立運(yùn)算數(shù)棧 SqStack1 和運(yùn)算符棧 SqStack2輔助分析算符有限關(guān)系.2 用戶輸入以“ #”結(jié)尾的算數(shù)表達(dá)式， 本程序需要用戶自行輸入表達(dá)式（運(yùn)算符可以是加 （+）；減（- ）；乘（* ）；除（/ ）；括號(hào)（），以字符形式讀入，在讀入的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)的識(shí)別處理，在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。3 在程序的適當(dāng)位置輸出運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的內(nèi)容，即演示運(yùn)算操作。4 測試數(shù)據(jù)見原題。5 程序執(zhí)行的命令包括：（1）建立算數(shù)表達(dá)

2、式；（2）得到運(yùn)算表達(dá)式的值；（3）演示運(yùn)算過程。二、概要設(shè)計(jì)1. 設(shè)定棧的抽象數(shù)據(jù)類型定義：ADT Stack數(shù)據(jù)對象D ai | ai charSet, i=1,2,.,n,n0 ;.數(shù)據(jù)關(guān)系：R1 <ai-1, ai >| ai-1, aiD, i=2,.,n （約定 an 端為棧頂， a1 端為棧底）基本操作：InitStack（&S）操作結(jié)果：構(gòu)造一個(gè)空棧S。Gettop(S,&e)初始條件：棧 S 已存在。操作結(jié)果：若棧S 不空，則以 e 返回棧頂元素。Push(&S,e)初始條件：棧S 已存在。操作結(jié)果：插入元素e 為新的棧頂元素。Pop(&a

3、mp;S,&e)初始條件：棧S 已存在且非空。操作結(jié)果：刪除S 的棧頂元素，并用e 返回其值。ADT Stack2. 本程序包括三個(gè)模塊（1）主程序模塊：Void main( )初始化；函數(shù)；;.（ 2）棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型（ 3）運(yùn)算模塊實(shí)現(xiàn)運(yùn)算并演示其過程模塊各模塊之間調(diào)用關(guān)系如下：主程序模塊運(yùn)算模塊棧模塊三、詳細(xì)設(shè)計(jì)1、元素類型、結(jié)點(diǎn)類型typedef structint *base;int *top;int stacksize;SqStack1;/操作數(shù)棧typedef structchar *base;char *top;int stacksize;SqStack2;/操

4、作符棧2、 棧類型typedef structchar *base;char *top;int stacksize;Stack;/棧類型棧的基本操作設(shè)置如下：void InitStack(Stack &S)/初始化，設(shè) S 為空棧（ S.top=NULL ）;.Status GetTop(Stack S,ElemType e)/若棧 S 不空，則以 e 帶回棧頂元素并返回 TRUE，否則返回 FALSE Status Push(Stack&S,ElemType e)/若分配空間成功，則在S 的棧頂插入新的棧頂元素e，并返回 TRUE ，/否則返回 FALSE 其中部分操作的算法

5、：Status Push(Stack &S,ElemType e)/若分配空間成功，則在S 的棧頂插入新的棧頂元素e，并返回 TRUE ；/否則棧不變，并返回FALSEif(MakeNode(p,e)P.next=S.top;S.top=p;S.size+;Return TRUE;else return FALSE;Status Pop(Stack &S,ElemType &e)/若棧不空，則刪除S 的棧頂元素并以e 帶回其值，且返回TRUE ，/否則返回 FALSE，且 e 無意義if(StackEmpty(S) return FALSE;elsep=S.top;S.

6、top=S.top->next;e=p->:data;S.size-;return TRUE;3、運(yùn)算代碼int Operate(int a,char theta,int b) /計(jì)算表達(dá)式值：主要是將大的表達(dá)式轉(zhuǎn)化成小的表達(dá)式進(jìn)行逐步求值int c;if(theta='+') c=a+b;else if(theta='-') c=a-b;else if(theta='*') c=a*b;else c=a/b;return c;/Operateint result(SqStack1 *OPND,SqStack2 *OPTR) /求值c

7、har a=0;char theta;int b,c,number=0;.IntInitStack(OPND);CharInitStack(OPTR);CharPush(OPTR,'#');a=getchar();while(a!='#' | CharGetTop(OPTR)!='#')printf("輸入字符： %c",a);if(!In(a)/ 不是運(yùn)算符則進(jìn)棧number=0;while(!In(a)number = number*10 +(a-48);/處理多位整數(shù)z=10*x+ya = getchar();IntPu

8、sh(OPND,number);printf("主要操作： Push(OPND,%d)",number);elseswitch(Precede(a,CharGetTop(OPTR)case '<':CharPush(OPTR,a);a=getchar();printf("主要操作： Push(OPTR,%c)",a);break;case '=':CharPop(OPTR);a=getchar();printf("主要操作： Pop(OPTR,%c)",a);break;case '>

9、;':theta=CharPop(OPTR);c=IntPop(OPND);b=IntPop(OPND);IntPush(OPND,Operate(b,theta,c);printf("主要操作：Operate(%d,%c,%d)",b,theta,c);break;printf("OPND棧：%dOPTR棧： %cn",IntGetTop(OPND),CharGetTop(OPTR);.printf("The result is %d.n",IntGetTop(OPND); /打印輸出表達(dá)式值return OK;4. 主函數(shù)

10、和其他函數(shù)的代碼void main() /主函數(shù)，使用自定義函數(shù)完成功能SqStack1 s1,*OPND;SqStack2 s2,*OPTR;OPND=&s1;OPTR=&s2;printf("Please enter an expression with a end of '#'.n");printf("The Expression:");result(OPND,OPTR);char Precede(char a,char b)/運(yùn)算優(yōu)先級(jí)判斷int i,j;char Table88=' ','

11、+','-','*','/','(',')','#', '+','>','>','<','<','<','>','>', '-','>','>','<','<','<','>',

12、'>', '*','>','>','>','>','<','>','>', '/','>','>','>','>','<','>','>', '(','<','<','&

13、lt;','<','<','=',' ', ')','>','>','>','>',' ','>','>','#','<','<','<','<','<',' ','=',; /優(yōu)先級(jí)表格for

14、(i=0;i<8;i+)if(Table0i=a) /縱坐標(biāo)尋找break;for(j=0;j<8;j+) /橫坐標(biāo)尋找if(Tablej0=b)break;return Tableji;int In(char c)/ 判斷 c 是否為操作符if ( c='(' | c='+' | c='-' | c = '*' | c='/' | c=')' | c='#' | c='')return 1;/ 如果是操作符返回1elsereturn 0;/ 不是，返回

15、0;.5函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：mainresultInitStackPushGetTopInPrecedePop四、調(diào)試分析算術(shù)表達(dá)式求值程序較為龐大，調(diào)試花費(fèi)時(shí)間較多，主要是在for循環(huán)和 while 循環(huán)時(shí)容易出錯(cuò)，對于涉及的循環(huán)的操作開始和結(jié)束條件設(shè)置很關(guān)鍵。五、用戶手冊1. 本程序開發(fā)環(huán)境為 VC 6.0，運(yùn)行環(huán)境為 dos 操作系統(tǒng)，執(zhí)行文件為：1.exe2. 運(yùn)行該程序后 ,產(chǎn)生如下圖所示的界面：;.3. 按照提示輸入一組表達(dá)式。4. 輸入完成后，按回車鍵。5. 屏幕上打印出對應(yīng)于該表達(dá)式的后綴表達(dá)式。6. 打印表達(dá)式計(jì)算結(jié)果。六、測試結(jié)果1.2.3;.4.七、

16、附錄源程序文件名清單：1.cpp/主程序1.exe/可執(zhí)行文件stdio.h/ 程序中用到的頭文件stdlib.h/程序中用到的頭文件string.h/程序中用到的頭文件math.h/程序中用到的頭文件程序代碼：#include<stdio.h>#include<stdlib.h>#include<string.h>.#include<math.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1/*棧模塊typedef struct S

17、qStack1/運(yùn)算數(shù)棧int *base;int *top;int stacksize;SqStack1;typedef struct SqStack2/運(yùn)算符棧char *base;char *top;int stacksize;SqStack2;void IntInitStack(SqStack1 *S)S->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S->base) exit(ERROR);.S->top=S->base;S->stacksize=STACK_INIT_SIZE;void Cha

18、rInitStack(SqStack2 *S)S->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!S->base) exit(ERROR);S->top=S->base;S->stacksize=STACK_INIT_SIZE;int IntGetTop(SqStack1 *S) /取棧頂元素int e;if(*S).top=(*S).base)return 0;e=*(*S).top-1);return e;char CharGetTop(SqStack2 *S) /取棧頂元素char e;if(*S)

19、.top=(*S).base) return 0;.e=*(*S).top-1);return e;int IntPush(SqStack1 *S,int e)*(*S).top+=e;return OK;int CharPush(SqStack2 *S,char e)*(*S).top+=e;return OK;int IntPop(SqStack1 *S)int e;if(*S).top=(*S).base) return 0;e=*-(*S).top;return e;int CharPop(SqStack2 *S);.char e;if(*S).top=(*S).base) retur

20、n 0;e=*-(*S).top;return e;/*運(yùn)算模塊char Precede(char a,char b)/運(yùn)算優(yōu)先級(jí)判斷int i,j;char Table88=' ','+','-','*','/','(',')','#', '+','>','>','<','<','<','>','>'

21、;, '-','>','>','<','<','<','>','>', '*','>','>','>','>','<','>','>', '/','>','>','>','

22、;>','<','>','>', '(','<','<','<','<','<','=',' ', ')','>','>','>','>',' ','>','>', '#','

23、;<','<','<','<','<',' ','=', ; /優(yōu)先級(jí)表格for(i=0;i<8;i+);.if(Table0i=a) / 縱坐標(biāo)尋找break;for(j=0;j<8;j+) / 橫坐標(biāo)尋找if(Tablej0=b)break;return Tableji;int Operate(int a,char theta,int b) / 計(jì)算表達(dá)式值：主要是將大的表達(dá)式轉(zhuǎn)化成小的表達(dá)式進(jìn)行逐步求值int c;if(theta='+

24、') c=a+b;else if(theta='-') c=a-b;else if(theta='*') c=a*b;else c=a/b;return c;/Operateint In(char c)/判斷 c 是否為操作符if ( c='(' | c='+' | c='-' | c = '*' | c='/' | c=')' | c='#' | c='')return 1;/如果是操作符返回1;.elsereturn 0;/

25、不是，返回 0int result(SqStack1 *OPND,SqStack2 *OPTR) /求值char a=0;char theta;int b,c,number=0;IntInitStack(OPND);CharInitStack(OPTR);CharPush(OPTR,'#');a=getchar();while(a!='#' | CharGetTop(OPTR)!='#')printf(" 輸入字符： %c",a);if(!In(a)/不是運(yùn)算符則進(jìn)棧number=0;while(!In(a)number = number*10