四則運(yùn)算表達(dá)式求值實(shí)驗(yàn)報告

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告HUNAN UNIVERSITY課程實(shí)習(xí)報告題 目： 四則運(yùn)算表達(dá)式求值 學(xué)生姓名： 學(xué)生學(xué)號： 專業(yè)班級： 指導(dǎo)老師： 完 成 日 期 ： 一、需求分析四則運(yùn)算表達(dá)式求值，將四則運(yùn)算表達(dá)式用中綴表達(dá)式表示，然后轉(zhuǎn)換為后綴表達(dá)式，并計(jì)算結(jié)果。本程序要求利用二叉樹后序遍歷來實(shí)現(xiàn)表達(dá)式的轉(zhuǎn)換，同時可以使用實(shí)驗(yàn)2的結(jié)果來求解后綴表達(dá)式的值。在字符界面上輸入一個中綴表達(dá)式，回車表示結(jié)束。如果該中綴表達(dá)式正確，那么在字符界面上輸出其后綴表達(dá)式，其中后綴表達(dá)式中兩相鄰操作數(shù)之間利用空格隔開；如果不正確，在字符界面上輸出表達(dá)式錯誤提示。測試數(shù)據(jù)輸入：21+23*（12-6）輸出：21 23

2、12 6 -*+二、詳細(xì)設(shè)計(jì)輸入和輸出的格式輸入本程序可以將輸入的四則運(yùn)算表達(dá)式（中綴表達(dá)式）轉(zhuǎn)換為后綴表達(dá)式輸出后綴表達(dá)式為：/輸出結(jié)果的位置表達(dá)式的值為：/輸出結(jié)果的位置三、調(diào)試分析本次實(shí)驗(yàn)的難點(diǎn)主要是在建立二叉樹的問題上。關(guān)于如何把中綴表達(dá)式存入二叉樹中，我參考了網(wǎng)上的一些方法，成功實(shí)現(xiàn)了目標(biāo)，但是卻遇到了一個問題，那就是不能處理小數(shù)，甚至兩位或兩位以上的整數(shù)。因?yàn)槿绻捎米址麛?shù)組來存儲操作數(shù)，運(yùn)算符合一位整數(shù)還可以處理，但對于兩位數(shù)就就會出問題，最后我改進(jìn)采用字符串?dāng)?shù)組來存儲操作數(shù)，成功解決了問題。另外在處理輸入的非法表達(dá)式問題中，我也費(fèi)了很大功夫，但總體問題不大。四、測試結(jié)果五、用戶

3、使用說明（可選）1、運(yùn)行程序時提示輸入四則運(yùn)算表達(dá)式本程序可以將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，并計(jì)算結(jié)果請輸入四則運(yùn)算表達(dá)式：輸出后綴表達(dá)式為：表達(dá)式的值為：程序源代碼（c+）#include<iostream> #include<string> #include<stack>#include<iomanip>const int Max=100;using namespace std; class Node public: char chMax; /考慮到數(shù)值有時會是兩位數(shù)，所以使用字符串?dāng)?shù)組Node* lChild; Node* rChild;

4、Node() strcpy(ch,""); lChild=rChild=NULL; Node() if(lChild!=NULL) delete lChild; if(rChild!=NULL) delete rChild; ; static int count=0; static char arrayMax; /保存原始的中綴表達(dá)式static char str2*Max; /保存后序遍歷出來的字符串，為表達(dá)式求值提供方便static int k=0; char getOp(Node *temp); /temp指針保存每個結(jié)點(diǎn)，返回的是運(yùn)算符Node* crtTree(N

5、ode* root); /傳入根結(jié)點(diǎn)指針，返回根結(jié)點(diǎn)指針void output(Node *root); /獲得處理后的字符串bool isError(char); /判斷字符是否有問題void deal(); /對字符數(shù)組進(jìn)行處理double value(string); / 計(jì)算后綴表達(dá)式，得到其結(jié)果。 int main() Node* root=NULL; cout<<"輸入中綴表達(dá)式："cin.getline(array,40); deal(); root=crtTree(root); cout<<"輸出后綴表達(dá)式："ou

6、tput(root); cout<<str<<endl; cout<<"輸出后綴表達(dá)式的值："if(value(str)!=0)cout<<fixed<<setprecision(2)<<value(str)<<endl; elsecout<<"A Wrong Input!"<<endl;return 0; /將數(shù)字字符存入一個結(jié)點(diǎn)，并返回?cái)?shù)字字符的后一個符號char getOp(Node *temp)int i=0; if( isError(ar

7、raycount) ) exit(0); while(arraycount<='9'&&arraycount>='0'|arraycount='.') temp->chi=arraycount; i+; count+; temp->chi='0' count+; return arraycount-1; /傳入根結(jié)點(diǎn)指針，返回根結(jié)點(diǎn)指針Node* crtTree(Node* root) Node *p,*q; char op; if(root=NULL) root=new Node;p=ne

8、w Node; op=getOp(root); while(op!='=') q=new Node; q->ch0=op; q->ch1='0' switch(op) case '+': case '-':q->lChild=root; root=q;p=new Node; op=getOp(p); root->rChild=p; break; case '*': case '/':if(root->ch0='+'|root->ch0='-

9、') p=new Node; strcpy(p->ch,root->ch); p->lChild=root; p->rChild=q; op=getOp(root); root=p; else q->lChild=root; root=q; p=new Node; op=getOp(p);root->rChild=p; break; case '(':p=root; while(p->rChild) p=p->rChild; if(p->lChild=NULL) p->lChild=crtTree(p->

10、lChild); /遞歸創(chuàng)建括號里的指針op=arraycount; count+; break; else p->rChild=crtTree(p->rChild); /遞歸創(chuàng)建括號里的指針op=arraycount; count+; break; case ')': return root; return root; /傳入根結(jié)點(diǎn)，后序遍歷,賦值給另一個字符數(shù)組（主要是為了給后序的計(jì)算表達(dá)式值提供方便）void output(Node *root) int n; if(root) output(root->lChild); output(root->

11、rChild); n=0; while(root->chn!='0') strk+=root->chn+;strk+=' ' bool isError(char ch) /判斷每個字符是否有錯if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&!(ch<='9'&&ch>='0')&&ch!='.'&

12、&ch!='('&&ch!=')')cout << "字符錯誤！" return true; return false; void deal() /對字符數(shù)組進(jìn)行處理int i=0,n=0; while(arrayi) if(arrayi=' '|arrayi='=') i+; arrayn+=arrayi+; arrayn+='='arrayn='0' double value(string s2) / 計(jì)算后綴表達(dá)式，得到其結(jié)果。 stac

13、k < double> s; double x,y; int i = 0; while(i < s2.length() ) if(s2i = ' ') i+; switch(s2i) case '+': if(s.size()>=2)x = s.top(); s.pop(); x += s.top(); s.pop(); i+; break; elsereturn 0;case '-': if(s.size()>=2)x = s.top(); s.pop(); x =s.top()-x; s.pop(); i+; b

14、reak; elsereturn 0;case '*': if(s.size()>=2)x = s.top(); s.pop(); x *= s.top(); s.pop(); i+; break; elsereturn 0; case '/': if(s.size()>=2)if( s.top()=0) return 0;elsex = s.top(); s.pop(); x = s.top()/x; s.pop(); i+; break; elsereturn 0; default : x = 0; while('0' <= s2i&&s2i <= '9') x = x*10+s2i - '0' i+; if(s2i = '.&#