數(shù)據(jù)結構實習報告：設計一個演示用運算優(yōu)先法對算數(shù)表達式求值過程的程序

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

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

3、mp;S,&e)初始條件：棧S 已存在且非空。操作結果：刪除S 的棧頂元素，并用e 返回其值。ADT Stack2. 本程序包括三個模塊（1）主程序模塊：Void main( )初始化；函數(shù)；;.（ 2）棧模塊實現(xiàn)棧抽象數(shù)據(jù)類型（ 3）運算模塊實現(xiàn)運算并演示其過程模塊各模塊之間調用關系如下：主程序模塊運算模塊棧模塊三、詳細設計1、元素類型、結點類型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;/棧類型棧的基本操作設置如下：void InitStack(Stack &S)/初始化，設 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、運算代碼int Operate(int a,char theta,int b) /計算表達式值：主要是將大的表達式轉化成小的表達式進行逐步求值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)/ 不是運算符則進棧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); /打印輸出表達式值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ōu)先級判斷int i,j;char Table88=' ','

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

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

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

14、(i=0;i<8;i+)if(Table0i=a) /縱坐標尋找break;for(j=0;j<8;j+) /橫坐標尋找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ù)的調用關系圖反映了演示程序的層次結構：mainresultInitStackPushGetTopInPrecedePop四、調試分析算術表達式求值程序較為龐大，調試花費時間較多，主要是在for循環(huán)和 while 循環(huán)時容易出錯，對于涉及的循環(huán)的操作開始和結束條件設置很關鍵。五、用戶手冊1. 本程序開發(fā)環(huán)境為 VC 6.0，運行環(huán)境為 dos 操作系統(tǒng)，執(zhí)行文件為：1.exe2. 運行該程序后 ,產(chǎn)生如下圖所示的界面：;.3. 按照提示輸入一組表達式。4. 輸入完成后，按回車鍵。5. 屏幕上打印出對應于該表達式的后綴表達式。6. 打印表達式計算結果。六、測試結果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/運算數(shù)棧int *base;int *top;int stacksize;SqStack1;typedef struct SqStack2/運算符棧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;/*運算模塊char Precede(char a,char b)/運算優(yōu)先級判斷int i,j;char Table88=' ','+','-','*','/','(',')','#', '+','>','>','<','<','<','>','>'

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

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

23、;<','<','<','<','<',' ','=', ; /優(yōu)先級表格for(i=0;i<8;i+);.if(Table0i=a) / 縱坐標尋找break;for(j=0;j<8;j+) / 橫坐標尋找if(Tablej0=b)break;return Tableji;int Operate(int a,char theta,int b) / 計算表達式值：主要是將大的表達式轉化成小的表達式進行逐步求值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)/不是運算符則進棧number=0;while(!In(a)number = number*10