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

數(shù)據(jù)結(jié)構(gòu)——實(shí)驗(yàn)報(bào)告5/11HUNANUNIVERSITY課程實(shí)習(xí)報(bào)告題目：四則運(yùn)算表達(dá)式求值 學(xué)生姓名：周華毅學(xué)生學(xué)號(hào)：201308010411 專業(yè)班級(jí)：計(jì)科1304 指導(dǎo)老師： 吳帆 2015/5/1一、需求分析四則運(yùn)算表達(dá)式求值，將四則運(yùn)算表達(dá)式用中綴表達(dá)式表示，然后轉(zhuǎn)換為后綴表達(dá)式，并計(jì)算結(jié)果。本程序要求利用二叉樹后序遍歷來(lái)實(shí)現(xiàn)表達(dá)式的轉(zhuǎn)換，同時(shí)可以使用實(shí)驗(yàn)2的結(jié)果來(lái)求解后綴表達(dá)式的值。在字符界面上輸入一個(gè)中綴表達(dá)式，回車表示結(jié)束。如果該中綴表達(dá)式正確，那么在字符界面上輸出其后綴表達(dá)式，其中后綴表達(dá)式中兩相鄰操作數(shù)之間利用空格隔開；如果不正確，在字符界面上輸出表達(dá)式錯(cuò)誤提示。測(cè)試數(shù)據(jù) 輸入：21+23*（12-6）輸出：2123126-*+二、概要設(shè)計(jì) 抽象數(shù)據(jù)類型為實(shí)現(xiàn)上述程序的功能，應(yīng)以字符串存儲(chǔ)用戶的輸入，以及計(jì)算出的結(jié)果。算法的基本思想根據(jù)題目要求，利用二叉樹后序遍歷來(lái)實(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、中綴表達(dá)式存入到二叉樹的過(guò)程中，要注意處理的順序，如‘+’、‘-’號(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á)式的值，故便利的過(guò)程中要將結(jié)點(diǎn)中得到的數(shù)據(jù)存入新的字符數(shù)組中。程序的流程程序由三個(gè)模塊組成：輸入模塊：完成一個(gè)中綴表達(dá)式的輸入，存入字符串?dāng)?shù)組array[Max]中。計(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)。voiddeal()函數(shù)功能是對(duì)字符數(shù)組進(jìn)行處理。voidoutput(Node*root);函數(shù)功能是獲得處理后的字符串，也就是中綴表達(dá)式轉(zhuǎn)化為的后綴表達(dá)式。輸出模塊：如果該中綴表達(dá)式正確，那么在字符界面上輸出其后綴表達(dá)式和表達(dá)式的值；如果不正確，在字符界面上輸出表達(dá)式錯(cuò)誤提示。三、詳細(xì)設(shè)計(jì)物理數(shù)據(jù)類型 case'*': case'/': if(root->ch[0]=='+'||root->ch[0]=='-'){ p=newNode; strcpy(p->ch,root->ch); p->lChild=root; p->rChild=q; op=getOp(root); root=p; }else{ q->lChild=root; root=q; p=newNode; 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=array[count]; count++; break; }else{ p->rChild=crtTree(p->rChild);//遞歸創(chuàng)建括號(hào)里的指針 op=array[count]; count++; break; } case')': returnroot; } } returnroot;}//傳入根結(jié)點(diǎn)，后序遍歷,賦值給另一個(gè)字符數(shù)組（主要是為了給后序的計(jì)算表達(dá)式值提供方便）voidoutput(Node*root){ intn; if(root){ output(root->lChild); output(root->rChild); n=0; while(root->ch[n]!='\0') str[k++]=root->ch[n++]; str[k++]=''; }}boolisError(charch){//判斷每個(gè)字符是否有錯(cuò) if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&!(ch<='9'&&ch>='0')&&ch!='.'&&ch!='('&&ch!=')'){ cout<<"字符錯(cuò)誤！"; returntrue; } returnfalse;}voiddeal(){//對(duì)字符數(shù)組進(jìn)行處理 inti=0,n=0; while(array[i]){ if(array[i]==''||array[i]=='=') i++; array[n++]=array[i++]; } array[n++]='='; array[n]='\0';}doublevalue(strings2){//計(jì)算后綴表達(dá)式，得到其結(jié)果。stack<double>s;doublex,y;inti=0; while(i<s2.length()){if(s2[i]=='')i++;switch(s2[i]) { case'+': if(s.size()>=2){ x=s.top();s.pop();x+=s.top();s.pop();i++;break; } else return0; case'-': if(s.size()>=2){ x=s.top();s.pop();x=s.top()-x;s.pop();i++;break; }else return0; case'*': if(s.size()>=2){ x=s.top();s.pop();x*=s.top();s.pop();i++;break; }else return0; case'/': if(s.size()>=2){ if(s.top()==0)return0; else{ x=s.top();s.pop();x=s.top()/x;s.pop();i++;break; } }else return0; default: x=0; while('0'<=s2[i]&&s2[i]<='9'){ x=x*10+s2[i]-'0'; i++; } if(s2[i]=='.'){ doublek=10.0; y=0; i++; while('0'<=s2[i]&&s2[i]<='9'){ y+=((s2[i]-'0')/k); i++; k*=10; } x+=y; } break;} if(x!=0) s.push(x);} if(s.size()==1) returns.top(); else return0;}2、利用堆棧來(lái)實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。#include<iostream>#include<string>#include<stack>#include<iomanip>usingnamespacestd;intcmp(charch){//運(yùn)算符優(yōu)先級(jí)switch(ch){case'+':case'-':return1;case'*':case'/':return2;default:return0;}}voidchange(string&s1,string&s2){//中綴表達(dá)式轉(zhuǎn)變后綴表達(dá)式stack<char>s;s.push('#');inti=0;while(i<s1.length()){//分成四個(gè)級(jí)別來(lái)檢驗(yàn)中綴表達(dá)式//s1.length()是為了s1的長(zhǎng)度，不包括\0if(s1[i]=='(')//級(jí)別一s.push(s1[i++]);elseif(s1[i]==')'){//級(jí)別二 while(s.top()!='('){s2+=s.top();s2+='';s.pop();}s.pop();i++; }elseif(s1[i]=='+'||s1[i]=='-'||s1[i]=='*'||s1[i]=='/'){//級(jí)別三 while(cmp(s.top())>=cmp(s1[i])){s2+=s.top();s2+='';s.pop();}s.push(s1[i]);i++;}else{//級(jí)別四while('0'<=s1[i]&&s1[i]<='9'||s1[i]=='.'){s2+=s1[i++];}s2+='';}}while(s.top()!='#'){//最后一步s2+=s.top();s2+='';s.pop();}}doublevalue(string&s2){//計(jì)算后綴表達(dá)式，得到其結(jié)果。stack<double>s;doublex,y;inti=0;while(i<s2.length()-1){//由于s2的最后一位是空格，影響判斷，所以用s2.length()-1if(s2[i]=='')i++;switch(s2[i]){ case'+':if(s.size()>=2){x=s.top();s.pop();x+=s.top();s.pop();i++;break;} elsereturn0; case'-':if(s.size()>=2){x=s.top();s.pop();x=s.top()-x;s.pop();i++;break;} elsereturn0; case'*':if(s.size()>=2){x=s.top();s.pop();x*=s.top();s.pop();i++;break;} elsereturn0; case'/':if(s.size()>=2){x=s.top();s.pop();x=s.top()/x;s.pop();i++;break;} elsereturn0;default:{x=0;while('0'<=s2[i]&&s2[i]<='9'){x=x*10+s2[i]-'0';i++;}if(s2[i]=='.'){doublek=10.0;y=0;