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

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

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

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

4、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，否則返回 FALSEStatus Push(Stack&S,ElemType e)/若分配空間成功，則在 S 的棧頂插入新的棧頂元素 e，并返回 TRUE，/ 否則返回 FALSE 其中部分操作的算法：Status Push(Stack &S,Ele

5、mType e)/若分配空間成功，則在 S 的棧頂插入新的棧頂元素 e，并返回 TRUE；/ 否則棧不變，并返回 FALSE if(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;else p=S.top;S.top=S.top-next;e=p-:data;S.si

6、ze-;return TRUE;3、運(yùn)算代碼int Operate(int a,char theta,int b) /計算表達(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) /求值char a=0;char theta;int b,c,number=0;IntInitStack(OPND);CharIni

7、tStack(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);/ 處z=10*x+ya = getchar();IntPush(OPND,number);printf( 主要操作： Push(OPND,%d)elseswitch(Precede(a,CharGetTop(OPTR)case :theta=CharPop(OPTR);

8、 c=IntPop(OPND); b=IntPop(OPND); IntPush(OPND,Operate(b,theta,c); printf( 主 要 操 作 ： ,b,theta,c);break;printf(OPND 棧 ： %d 棧： %cn,IntGetTop(OPND),CharGetTop(OPTR);理多位整數(shù),number);,a);,a);Operate(%d,%c,%d)OPTRprintf(The result is %d.n,IntGetTop(OPND); / return OK;打印輸出表達(dá)式值4. 主函數(shù)和其他函數(shù)的代碼void main() / 主函數(shù)，使

9、用自定義函數(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)先級判斷int i,j;char Table88= ,+,-,*,/,(,),#, +,-,*, /,(, ,#, ,=,; / 優(yōu)先級表格for(i=0;i8;i+)if(Table0i=a) / 縱坐標(biāo)尋找 b

10、reak;for(j=0;j8;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;/ 不是，返回 05函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：四、調(diào)試分析算術(shù)表達(dá)式求值程序較為龐大，調(diào)試花費(fèi)時間較多，主要是在 for 循 環(huán)和 while 循環(huán)時容易出錯，對于涉及的循環(huán)的操作開始和結(jié)束條件設(shè) 置很關(guān)鍵。五、用戶手冊1. 本程序開發(fā)

11、環(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á)式計算結(jié)果。六、測試結(jié)果1.2.34.七、附錄源程序文件名清單：1.cpp /1.exe /stdio.h stdlib.h / string.h / math.h /主程序可執(zhí)行文件/ 程序中用到的頭文件程序中用到的頭文件 程序中用到的頭文件 程序中用到的頭文件程序代碼：#include#include#include棧模塊SIZE*sizeof(int);#in

12、clude #define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1 /* typedef struct SqStack1/運(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 if

13、(!S-base) exit(ERROR);S-top=S-base;S-stacksize=STACK_INIT_SIZE;void CharInitStack(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

14、 e;char CharGetTop(SqStack2 *S) /取棧頂元素char e;if(*S).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 CharPo

15、p(SqStack2 *S)char e;if(*S).top=(*S).base) return 0;e=*-(*S).top; return e;/ 算模塊 char Precede(char a,char b)/運(yùn)/ 算優(yōu)先級判斷 int i,j;char Table88= ,+,-,*,/,(,),#,+,(,; /優(yōu)先級表格for(i=0;i8;i+)if(Table0i=a) / 縱坐標(biāo)尋找break;for(j=0;j8;j+) / 橫坐標(biāo)尋找if(Tablej0=b)break;return Tableji;int Operate(int a,char theta,int b)

16、 / 計算表達(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 In(char c)/判斷 c 是否為操作符if ( c=( | c=+ | c=- | c = * | c=/ | c=) | c=# |return 1;/如果是操作符返回 1elsereturn 0;/不是，返回 0int result(SqStack1 *OPND,SqStack2 *OPTR) /求值 char a=

17、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();IntPush(OPND,number);printf( 主 要 操 作 ： Push(OPND,%d),number);elseswitch(Precede(a,CharGetTop(OPTR)case :theta=CharPop(OPTR);c=IntPop(OPND);b=IntPop(OPND); IntPush(OPND,Operate(b,theta,c);printf( 主 要 操 作 ： Operate(%d,%c,%d) ,b,theta,c);b