1、實習報告題目：算術表達式求值演示。一、 需求分析1.以字符序列的形式從終端輸入語法正確的、不含變量的整數表達式。2.利用教科書表3.1給出的算符優(yōu)先關系，實現對算數四則混合運算表達式的求值。3.仿照教科書的例子在求值中運用符棧、運算數棧、輸入字符和主要操作的變化過程。4.程序執(zhí)行的命令包括：(1)構造空棧；(2) 判斷符號優(yōu)先級;(3) 判斷是否為七種運算符之一;(4)運算求解算術表達式。5.測試數據(1)3*(7-2);(2)8;(3)1+2+3+4;(4)88-1*5;(5)1024*4/8;(6)(20+2)*(6/2);(7)3-3-3;(8)8/(9-9);(9)2*(6+2*(3+

2、6*(6+6);(10)(6+6)*6+3)*2+6)*2;二、概要設計1.設定棧的抽象數據類型定義：ADT Stack數據對象：D=ai|aiCharSet,i=1,2,，n,n0數據關系：R1=| ai -1, ai D,i=2,，n基本操作：InitStack（&S）操作結果：構造一個空棧S。GetTop (S，&e)初始條件：棧S已存在。操作結果：若棧S不空，則以e返回棧頂元素。Push(&S, e)初始條件：棧S已存在。操作結果：在棧S的棧頂插入新的棧頂元素e。Pop(&S, &e)初始條件：棧S已存在。操作結果：刪除S的棧頂元素，用e返回其值。 ADT Stack2.設定運算表達式

3、的抽象數據類型為：ADT EvaluateExpression數據對象：D=ai| ai為數字及運算符，i=1,2,，n,n0數據關系：R1= 基本操作：Precede(a1 , a2)初始條件：字符a1，a2存在。操作結果：判定運算符的優(yōu)先級In( d )初始條件：字符d存在。操作結果：判斷c是否為七種運算符之一Operate(a, theta, b )初始條件：字符a, theta, b存在。操作結果：運算表達式結果。 ADT EvaluateExpression3.本程序包含3個模塊：（1）主程序模塊：int main() 初始化；do接受命令：處理命令：return 0;(2)棧模塊實

4、現棧抽象數據類型(3)求解算術表達式模塊實現算術表達式數據類型各模塊之間的調用關系如下：主程序模塊 棧模塊 求解算術表達式模塊三、詳細設計1.數據類型、字符類型。typedef double SElemType;/ 數據類型char Precede(char a1 ,char a2) char r; /字符類型2.棧類型typedef struct SqStack SElemType *base; SElemType *top; int stacksize;SqStack;棧的基本操作設置如下：void InitStack (SqStack &S)/構造一個空棧bool GetTop (SqS

5、tack S,SElemType &e) /若棧不空，則用e返回S的棧頂元素，并返回true；否則返回falsebool Push(SqStack &S,SElemType e) /插入元素為e的新的棧頂元素bool Pop(SqStack &S,SElemType &e)/若棧不空，則刪除S的棧頂元素，用e返回其值其中部分操作的算法：bool Push(SqStack &S,SElemType e) /插入元素為e的新的棧頂元素 if(S.top-S.base=S.stacksize) /棧滿，追加存儲空間 S.base=(SElemType*)realloc(S.base,(S.stack

6、size+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(-1); /存儲空間分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e;/top自增 return true;bool Pop(SqStack &S,SElemType &e)/若棧不空，則刪除S的棧頂元素，用e返回其值 if(S.top=S.base) return false; e=*-S.top; /刪除一個元素,top減一 return true ;3. 求解算術表達式的偽算法SElem

7、Type EvaluateExpression( ) SqStack OPTR,OPND;/OPTR和OPND分別為運算符棧和運算數棧 char c; char Data20;/定義此數組為了存放整數或小數 SElemType a,b,d,e; InitStack(OPTR);/構造一個運算符棧 InitStack(OPND);/構造一個運算數棧 Push(OPTR,n);/將換行符壓入棧底 c=getchar(); GetTop(OPTR,e); while(c!=n|e!=n)/棧頂不是換行符且輸入不是換行符 if(In(c)/是符號則進棧 switch(Precede(e,c) case

8、: /退棧并將運算結果入棧 Pop(OPTR,e); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,e,b); break; else if(c=0&c=9|c=.) Push(OPND,c-48); c=getchar(); else couterror!輸入錯誤!endl; exit(-1); GetTop(OPTR,e); GetTop(OPND,e); return e;4.主函數和其他函數的偽算法int main()/主程序 SElemType result;/初始定義 cout請輸入表達式endl;/輸出輸入要求 result=Eval

9、uateExpression();/執(zhí)行函數操作命令 cout結果為:resultendl;/輸出結果 return 0;char Precede(char a1 ,char a2)/判定運算符的優(yōu)先級函數。 char r; switch(a2) case+: case-:/加減運算優(yōu)先級相同 if(a1=(|a1=n) r=; break; case*: case/: /乘除運算優(yōu)先級相同 if(a1=*|a1=/|a1=) r=; else r=; break; case(: if(a1=) cout括號匹配錯誤!endl; exit(-1); else r=; break; case):

10、 if(a1=() r=; else if(a1=n) couterror!沒有左括號; break; casen: switch(a1) casen: r=; break; case(: couterror!沒有右括號; break; return r;bool In(char d)/判斷c是否為七種運算符之一的函數 switch(d) case+: case-: case*: case/: case(: case): casen: return true; default: return false; 5.函數的調用關系圖反映了演示程序的結構層次： 主程序Initialization Re

11、adCommand Interpret Init EvaluateExpression PrintEvaluateExpression InitStack Push Pop GetTop四、調試分析1.這次作業(yè)思路比較簡單，核心問題就是表達式的運算，要區(qū)分運算符的優(yōu)先順序。通過運用棧后進先出的特點實現算法功能，調用push和pop等函數，實現一系列操作。2.調試過程中，起初想打換行符時打成了，忘了打字母n,結果程序調試總是有錯誤，改成n后便成功運行了，可見，細節(jié)之處也很重要。3.運用了很多的棧的基本操作，讓我對棧的內容熟悉了不少，收獲很大。4本題中時間復雜度為O（n）五、用戶手冊本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：EvaluateExpression.exe。六、測試結果(1) 請輸入表達式：3*(7-2);結果為：15(2) 請輸入表達式：8;結果為：8(3) 請輸入表達式：1+2+3+4;結果為：10(4) 請輸入表達式：88-1*5;結果為：82(5) 請輸入表達式：1024*4/8;結果為：512(6) 請輸入表達