四則運(yùn)算表達(dá)式求值(棧+二叉樹,c++版)

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

2、 (12-6) 輸出：21 23 12 6 -*+二、概要設(shè)計(jì)抽象數(shù)據(jù)類型為實(shí)現(xiàn)上述程序的功能，應(yīng)以字符串存儲(chǔ)用戶的輸入，以及計(jì)算出的結(jié)果。算法的基本思想根據(jù)題目要求，利用二叉樹后序遍歷來實(shí)現(xiàn)表達(dá)式的轉(zhuǎn)換。該算法的基本模塊包括二叉樹的建立以及如何把輸入的中綴表達(dá)式利用二叉樹后序遍歷轉(zhuǎn)化為后綴表達(dá)式。1、首先要將輸入的中綴表達(dá)式(數(shù)字字符)存入到二叉樹中，由于存在兩位或者兩位 以上的數(shù)，甚至還有小數(shù)，所以考慮用字符型指針存儲(chǔ)數(shù)字字符和操作符。2、為了便于將中綴表達(dá)式存入二叉樹中，在錄入中綴表達(dá)式后，要進(jìn)行相應(yīng)的處理， 比如去掉空格符，添加結(jié)束標(biāo)志，如 ='、'#'等。3、

3、中綴表達(dá)式存入到二叉樹的過程中，要注意處理的順序，如 +、'-'號(hào)的優(yōu)先級(jí) 比*、'/'號(hào)的 低，當(dāng)遇到*、'/'號(hào)時(shí)，要判斷樹以上的節(jié)點(diǎn)中是否有+、'-'號(hào)，有的話要與其交換位置。遇到(時(shí)要反復(fù)創(chuàng)建二叉樹的結(jié)點(diǎn)，構(gòu)建子二叉樹，考慮 到括號(hào)內(nèi)要處理的步驟可能會(huì)較多，可以考慮用遞歸。遇到)時(shí)則直接結(jié)束此子二叉樹的建立。此外二叉樹中葉子結(jié)點(diǎn)存儲(chǔ)操作數(shù)，非葉子結(jié)點(diǎn)存儲(chǔ)操作碼。4、對(duì)創(chuàng)建好的二叉樹進(jìn)行后序遍歷，即可得到相應(yīng)的后綴表達(dá)式，實(shí)現(xiàn)方法可以用遞 歸的方式，由于后面還要計(jì)算表達(dá)式的值，故便利的過程中要將結(jié)點(diǎn)中得到的數(shù)據(jù)存入新的字符數(shù)

4、組中。程序的流程程序由三個(gè)模塊組成：(1) 輸入模塊：完成一個(gè)中綴表達(dá)式的輸入，存入字符串?dāng)?shù)組arrayMax中。(2) 計(jì)算模塊：設(shè)計(jì)一個(gè)建立二叉樹的函數(shù)，Node* crtTree(Node* root),傳入根結(jié)點(diǎn)指針，返回根結(jié)點(diǎn)指針，該函數(shù)的實(shí)現(xiàn)還要反復(fù)使用另一個(gè)函數(shù)chargetOp(Node *temp),其將數(shù)字字符存入一個(gè)結(jié)點(diǎn)，并返回?cái)?shù)字字符的后一 個(gè)符號(hào)。void deal()函數(shù)功能是對(duì)字符數(shù)組進(jìn)行處理。void output(Node*root);函數(shù)功能是獲得處理后的字符串，也就是中綴表達(dá)式轉(zhuǎn)化為的后綴表達(dá)式。(3) 輸出模塊：如果該中綴表達(dá)式正確，那么在字符界面上輸出

5、其后綴表達(dá)式和表 達(dá)式的值；如果不正確，在字符界面上輸出表達(dá)式錯(cuò)誤提示。三、詳細(xì)設(shè)計(jì)物理數(shù)據(jù)類型題目要求輸入的四則運(yùn)算表達(dá)式運(yùn)算符只有加減乘除，操作數(shù)有整數(shù)和小數(shù)， 為了能夠存儲(chǔ)，采用C語言中的字符串?dāng)?shù)組。char chMax;算法的時(shí)空分析算法的運(yùn)行時(shí)間主要耗費(fèi)在二叉樹的建立過程中?？梢园l(fā)現(xiàn)，每當(dāng)遇到一個(gè)運(yùn)算符或操作數(shù)時(shí)，都要調(diào)用一次函數(shù) char getOp（Node *temp） ,來將其存入二叉樹的結(jié)點(diǎn)中，其 中也會(huì)遇到遞歸的情況，但耗時(shí)可以忽略。所以假設(shè)輸入的字符串中字符個(gè)數(shù)為N,則算法的時(shí)間復(fù)雜度為O（N）。輸入和輸出的格式輸入本程序可以將輸入的四則運(yùn)算表達(dá)式（中綴表達(dá)式）轉(zhuǎn)換為后

6、綴表達(dá)式提示請(qǐng)輸入四則運(yùn)算表達(dá)式：提示 等待輸入輸出提示后綴表達(dá)式為：輸出結(jié)果的位置表達(dá)式的值為：輸出結(jié)果的位置四、調(diào)試分析本次實(shí)驗(yàn)的難點(diǎn)主要是在建立二叉樹的問題上。關(guān)于如何把中綴表達(dá)式存入二叉樹中， 我參考了網(wǎng)上的一些方法， 成功實(shí)現(xiàn)了目標(biāo)，但是卻遇到了一個(gè)問題， 那就是不能處理小數(shù)， 甚至兩位或兩位以上的整數(shù)。因?yàn)槿绻捎米址麛?shù)組來存儲(chǔ)操作數(shù)，運(yùn)算符合一位整數(shù)還可以處理，但對(duì)于兩位數(shù)就就會(huì)出問題，最后我改進(jìn)采用字符串?dāng)?shù)組來存儲(chǔ)操作數(shù)，成功解決了問題。另外在處理輸入的非法表達(dá)式問題中，我也費(fèi)了很大功夫，但總體問題不大。五、測(cè)試結(jié)果輸人中緩表達(dá)式：21M3*（12川）諭出后舞表達(dá)式，21 23

7、 12 6 - * + 諭出后綴表達(dá)式的值；159.001-_- _I_I . 、 輸入中綴莪達(dá)式:11*(18-5.3)-32/1.6愉出后綴表達(dá)式；2.1 1S 5. 3 - * 32 1.6 / -輸出后綴表達(dá)式的值；e.67_ -18- H_1_I I_I_I II_|_| 瑜人申繳表達(dá)式士 +2的輸出后綴表達(dá)式;2 3%十輸出后綴未達(dá)式的值；2Wrcng Input! 一 _I -t- _I_. 六、用戶使用說明（可選）1、本程序的運(yùn)行環(huán)境為 DOS操作系統(tǒng)2、運(yùn)行程序時(shí)提示輸入四則運(yùn)算表達(dá)式本程序可以將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，并計(jì)算結(jié)果請(qǐng)輸入四則運(yùn)算表達(dá)式：輸出后綴表達(dá)式為:

8、表達(dá)式的值為:七、附錄（可選）程序源代碼（C+ ）1、利用二叉樹后序遍歷來實(shí)現(xiàn)表達(dá)式的轉(zhuǎn)換: #include<iostream> #include<string>#include<stack> #include<iomanip> const int Max=100;using namespace std; class Nodepublic:char chMax;考慮到數(shù)值有時(shí)會(huì)是兩位數(shù)，所以使用字符串?dāng)?shù)組Node* lChild;Node* rChild;Node()strcpy(ch,"");lChild=rChild=N

9、ULL;Node()if(lChild!=NULL) delete lChild;if(rChild!=NULL) delete rChild;static int count=0;/保存原始的中綴表達(dá)式保存后序遍歷出來的字符串，為表達(dá)式求值提供方便/temp 指針保存每個(gè)結(jié)點(diǎn)，返回的是運(yùn)算符/傳入根結(jié)點(diǎn)指針，返回根結(jié)點(diǎn)指針/獲得處理后的字符串/判斷字符是否有問題/對(duì)字符數(shù)組進(jìn)行處理/計(jì)算后綴表達(dá)式，得到其結(jié)果。static char arrayMax;static char str2*Max;static int k=0;char getOp(Node *temp);Node* crtTre

10、e(Node* root);void output(Node *root);bool isError(char);void deal();double value(string);int main()Node* root=NULL;cout<<"輸入中綴表達(dá)式:cin.getline(array,40);deal();root=crtTree(root);cout<<"輸出后綴表達(dá)式:output(root);cout<<str<<endl;cout<<"輸出后綴表達(dá)式的值："if(value(

11、str)!=0)cout<<fixed<<setprecision(2)<<value(str)<<endl;elsecout<<"A Wrong Input!"<<endl;return 0;將數(shù)字字符存入一個(gè)結(jié)點(diǎn)，并返回?cái)?shù)字字符的后一個(gè)符號(hào)char getOp(Node *temp)int i=0;if( isError(arraycount)exit(0);while(arraycount<='9'&&arraycount>='0'|ar

12、raycount='.') 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=new Node;op=getOp(root);while(op!='=')q=new Node;q->ch0=op;q->ch1='0'switch(op)case 

13、9;+':case '-':q->lChild=root;root=q;p=new Node;op=getOp(p);root->rChild=p;break;casel*1case '/':if(root->ch0='+'|root->ch0='-') p=new Node; strcpy(p->ch,root->ch); p->lChild=root; p->rChild=q; op=getOp(root); root=p; else q->lChild=root;

14、 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->lChild);/ 遞歸創(chuàng)建括號(hào)里的指針op=arraycount; count+; break; elsep->rChild=crtTree(p->rChild); 遞歸創(chuàng)建括號(hào)里的指針op=arraycount; count+; break;cas

15、e ')': return root; return root; 傳入根結(jié)點(diǎn)，后序遍歷，賦值給另一個(gè)字符數(shù)組(主要是為了給后序的計(jì)算表達(dá)式值提供 方便)void output(Node *root)int n;if(root)output(root->lChild);output(root->rChild);n=0;while(root->chn!='0')strk+=root->chn+;strk+尸；bool isError(char ch) /判斷每個(gè)字符是否有錯(cuò)if(ch!='+'&&ch!=

16、9;-'&&ch!='*'&&ch!=7'&&!(ch<='9'&&ch>='0')&&ch!=.'&&ch!='(' &&ch!=')')cout << "字符錯(cuò)誤！"return true;return false;void deal()/對(duì)字符數(shù)組進(jìn)行處理int i=0,n=0;while(arrayi)if(arrayi='

17、; '|arrayi='=')i+;arrayn+=arrayi+;arrayn+='='arrayn='0'double value(string s2)/計(jì)算后綴表達(dá)式，得到其結(jié)果。stack < doubles;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

18、+; break;elsereturn 0;case '-':if(s.size()>=2)x = s.top(); s.pop(); x =s.top()-x; s.pop(); i+; break;elsereturn 0;casel*1if(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(

19、); 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 = '.')double k = 10.0;y = 0;i+;while('0' <= s2i&&s2i <= '9')y += (s2i-'0')/k);i+;k *= 10;x +=

20、 y;break;if(x!=0)s.push(x);if( s.size()=1 )return s.top();elsereturn 0;2、利用堆棧來實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。#include <iostream>#include <string>#include <stack>#include <iomanip> using namespace std;int cmp(char ch)switch(ch)/運(yùn)算符優(yōu)先級(jí)case '+': case '-': return 1;case '*&#

21、39;: case '/': return 2;default : return 0;void change(string &s1, string &s2) stack <char> s;s.push('#');int i = 0;while(i < s1.length()s1的長(zhǎng)度，不包括0if(s1i='(')s.push(s1i+);else if(s1i = ')') while( s.top() != '(')s2 += s.top();s2 +=''s.

22、pop();/中綴表達(dá)式轉(zhuǎn)變后綴表達(dá)式分成四個(gè)級(jí)別來檢驗(yàn)中綴表達(dá)式/s1.length()/級(jí)別一/級(jí)別二是為了s.pop();i+;/級(jí)別三else if( s1i = '+'|s1i = '-'|s1i = '*'|s1i = '/' )while( cmp(s.top() >= cmp(s1i) )s2 += s.top();s2 +=''s.pop();s.push(s1i);i+;else/級(jí)別四while('0' <= s1i&&s1i <= '

23、9'|s1i = '.')s2 += s1i+;s2 +=''while(s.top() != '#')s2 += s.top();s2 +=''s.pop()；double value(string &s2) stack <double> s;double x,y;int i = 0;while(i < s2.length()-1) s2.length()-1if(s2i='') i+；switch(s2i)/最后一步/計(jì)算后綴表達(dá)式，得到其結(jié)果。/由于s2的最后一位是空格，影響判斷，所以用x = s.top(); s.pop(); x += s.top(); s.pop(); i+;case '+': if(s.size()>=2)break; else return 0;case '-': if(s.size()>=2)x = s.top(); s.pop(); x =s.top()-x; s.pop(); i+; break;else return 0;case '*': if(s.size()>=2)x = s.top(); s.pop(); x *= s.t