C++與數(shù)據(jù)結(jié)構(gòu)專題設(shè)計(jì)三 簡(jiǎn)易計(jì)算器

1、C+與數(shù)據(jù)結(jié)構(gòu)專題設(shè)計(jì)報(bào)告簡(jiǎn)易計(jì)算器C+與數(shù)據(jù)結(jié)構(gòu)專題設(shè)計(jì)簡(jiǎn)易計(jì)算器目錄一問題描述2二具體要求2三數(shù)據(jù)結(jié)構(gòu)3四設(shè)計(jì)與實(shí)現(xiàn)31.系統(tǒng)首頁：42.進(jìn)行簡(jiǎn)單的四則運(yùn)算5五測(cè)試與結(jié)論111.表達(dá)式錯(cuò)誤的情況122.所要計(jì)算的數(shù)據(jù)過大或過小的情況15六.總結(jié)與思考17七附源代碼18 一問題描述由鍵盤輸入一算術(shù)表達(dá)式，以中綴形式輸入，試編寫程序?qū)⒅芯Y表達(dá)式轉(zhuǎn)換成一棵二叉表達(dá)式樹，通過對(duì)該的后序遍歷求出計(jì)算表達(dá)式的值。二具體要求a要求對(duì)輸入的表達(dá)式能判斷出是否合法。不合法要有錯(cuò)誤提示信息。b將中綴表達(dá)式轉(zhuǎn)換成二叉表達(dá)式樹。c后序遍歷求出表達(dá)式的值三數(shù)據(jù)結(jié)構(gòu)一棵表達(dá)式樹，它的樹葉是操作數(shù)，如常量或變量名字，而

2、其他的結(jié)點(diǎn)為操作符。a建立表達(dá)式樹。二叉樹的存儲(chǔ)采用了鏈?zhǔn)酱鎯?chǔ)。當(dāng)要?jiǎng)?chuàng)建二叉樹時(shí)，先從表達(dá)式尾部向前搜索，找到第一個(gè)優(yōu)先級(jí)最低的運(yùn)算符，建立以這個(gè)運(yùn)算符為數(shù)據(jù)元素的根結(jié)點(diǎn)。注意到表達(dá)式中此運(yùn)算符的左邊部分對(duì)應(yīng)的二叉绔為根結(jié)點(diǎn)的左子樹，右邊部分對(duì)應(yīng)的是二叉绔為根結(jié)點(diǎn)的右子樹，根據(jù)地這一點(diǎn)，可用遞歸調(diào)用自己來完成對(duì)左右子樹的構(gòu)造。b求表達(dá)式的值。求值時(shí)同樣可以采用遞歸的思想，對(duì)表達(dá)式進(jìn)行后序遍歷。先遞歸調(diào)用自己計(jì)算左子樹所代表的表達(dá)式的值，再遞歸調(diào)用自己計(jì)算右子樹代表的表達(dá)式的值，最后讀取根結(jié)點(diǎn)中的運(yùn)算符，以剛才得到的左右子樹的結(jié)果作為操作數(shù)加以計(jì)算，得到最終結(jié)果。四設(shè)計(jì)與實(shí)現(xiàn)為了使用二叉樹實(shí)現(xiàn)表

3、達(dá)式的順序運(yùn)算，我們分別構(gòu)造了結(jié)點(diǎn)類，用來作為二叉樹的基本結(jié)構(gòu)，后構(gòu)造二叉樹類，構(gòu)造函數(shù)并建立根節(jié)點(diǎn)，先對(duì)二叉樹的根節(jié)點(diǎn)進(jìn)行運(yùn)算，再通過對(duì)當(dāng)前節(jié)點(diǎn)的左孩子右孩子節(jié)點(diǎn)進(jìn)行判斷、計(jì)算、刪除，以一個(gè)遞歸調(diào)用函數(shù)即后序遍歷，從根節(jié)點(diǎn)開始計(jì)算，如果子樹中不為空且不為數(shù)據(jù)則先遍歷左子樹然后遍歷右子樹然后計(jì)算根節(jié)點(diǎn)，從而實(shí)現(xiàn)按照運(yùn)算符優(yōu)先級(jí)順序完成表達(dá)式計(jì)算的功能。并在每次計(jì)算完成后詢問操作者意愿從而決定是否進(jìn)行下一次運(yùn)算。以下介紹程序功能的實(shí)現(xiàn)：1. 系統(tǒng)首頁：功能提示，輸入待計(jì)算的表達(dá)式，以完成計(jì)算：相應(yīng)代碼：system("cls");cout<<"*&quo

4、t;<<endl;cout<<" 二叉樹計(jì)算器"<<endl;cout<<"*"<<endl;char c;while(choice='y'|choice='Y') cout<<"n請(qǐng)輸入表達(dá)式:n" cin>>infix; cout<<"-"<<'n' cout<<"表達(dá)式為: "<<infix<<

5、9;n' 2.進(jìn)行簡(jiǎn)單的四則運(yùn)算對(duì)輸入的表達(dá)式首先判斷正誤，然后按照運(yùn)算的優(yōu)先級(jí)分別進(jìn)行運(yùn)行，并且分別輸出每步運(yùn)算的結(jié)果。先進(jìn)行乘方，然后乘除，最后再計(jì)算加減，先算括號(hào)內(nèi)后算括號(hào)外，正確度一目了然。（1）對(duì)于負(fù)數(shù)也可以進(jìn)行相應(yīng)的加減乘除以及乘方的運(yùn)算。對(duì)于負(fù)數(shù)的運(yùn)算，也和正數(shù)一樣，先算括號(hào)內(nèi)的后算括號(hào)外的，其次算乘方，再算乘除，最后進(jìn)行加減的運(yùn)算。負(fù)數(shù)的加減乘除：負(fù)數(shù)的乘方運(yùn)算：（1） 正指數(shù)冪運(yùn)算：（2） 負(fù)指數(shù)冪運(yùn)算： 可以進(jìn)行小數(shù)的計(jì)算，對(duì)于小數(shù)采用浮點(diǎn)數(shù)的存儲(chǔ)方式和輸出方式，計(jì)算精度可以取到小數(shù)點(diǎn)后五位。小數(shù)的加減乘除：小數(shù)的運(yùn)算，依然按照先乘除后加減，先算括號(hào)內(nèi)后算括號(hào)外的順

6、序運(yùn)算。小數(shù)的乘方和開方：（1） 正小數(shù)冪次方：（2） 負(fù)小數(shù)冪次方：（3） 開正小數(shù)次方：（4） 開負(fù)小數(shù)次方：五測(cè)試與結(jié)論 此報(bào)告在C-Free5.0環(huán)境下進(jìn)行測(cè)試。C-Free是一款C/C+集成開發(fā)環(huán)境（IDE）。C-Free中集成了C/C+代碼解析器，能夠?qū)崟r(shí)解析代碼，并且在編寫的過程中給出智能的提示。C-Free提供了對(duì)目前業(yè)界主流C/C+編譯器的支持，可以在C-Free中輕松切換編譯器?？啥ㄖ频目旖萱I、外部工具以及外部幫助文檔，使在編寫代碼時(shí)得心應(yīng)手。完善的工程/工程組管理使你能夠方便的管理自己的代碼。以下是各種測(cè)試用例。注：較為簡(jiǎn)單和常規(guī)的測(cè)試用例在上一部分“算法的實(shí)現(xiàn)”中已經(jīng)給

7、出，下面只給出一些具有代表性的測(cè)試用例。1.表達(dá)式錯(cuò)誤的情況在表達(dá)式錯(cuò)誤的情況下，程序能夠運(yùn)行，但是不能夠正常運(yùn)算，而是給出錯(cuò)誤的提示信息，提醒重新輸入正確的表達(dá)式。下圖表示以0作為除數(shù)時(shí)程序所給的提示信息“Infinity”下圖為計(jì)算表達(dá)式0（-3）時(shí)候的輸出，由于表達(dá)式?jīng)]有數(shù)學(xué)意義，所以也就沒有正確的結(jié)果，因而程序運(yùn)行后得到的結(jié)果是“Infinity”.下圖顯示的是輸入的表達(dá)式不符合數(shù)學(xué)規(guī)律時(shí)的錯(cuò)誤提示信息。下圖表示輸入表達(dá)式中含有不合法的字符，例如字母時(shí)候，程序運(yùn)行時(shí)所給的提示信息。下圖所示為表達(dá)式錯(cuò)誤的另外一種情形，即輸入的括號(hào)多余的情形。下面兩個(gè)測(cè)試用例，為表達(dá)式輸入錯(cuò)誤的情況，在下

8、列兩個(gè)表達(dá)式中，有不合法的運(yùn)算符，比如表達(dá)式前面有運(yùn)算符或者表達(dá)式后面還有運(yùn)算符。2.所要計(jì)算的數(shù)據(jù)過大或過小的情況當(dāng)輸入的數(shù)據(jù)很大或者很小時(shí)，會(huì)致使結(jié)果很大或者很小，此時(shí)，若是結(jié)果的大小超過數(shù)據(jù)類型的表示范圍，那么就會(huì)產(chǎn)生錯(cuò)誤，并且顯示錯(cuò)誤信息。若是沒有超出數(shù)據(jù)的表示范圍，那么就會(huì)用浮點(diǎn)數(shù)來表示比較大或者比較小的數(shù)據(jù)。六.總結(jié)與思考七附源代碼#include<iostream> #include<cstring>#include<cmath> #include<sstream>#include<stack> /利用stack頭文件來

9、構(gòu)造兩個(gè)棧用來存儲(chǔ)數(shù)據(jù)和運(yùn)算符 using namespace std; bool IsOperator(string mystring)/判斷參數(shù)string是否是運(yùn)算符 是返回邏輯值true if(mystring="-"|mystring="+"|mystring="/"|mystring="*"|mystring="") return(true); else return(false); bool IsOperator(char ops)/重載 if(ops='+'|op

10、s='-'|ops='*'|ops='/'|ops=''|ops='('|ops=')') return(true); else return(false); bool IsOperand(char ch)/ 驗(yàn)證是否是數(shù) if(ch>='0')&&(ch<='9')|ch='.') return true; else return false; /以上三個(gè)是起判斷作用的函數(shù) class node_type/結(jié)點(diǎn)類 publ

11、ic: string data; /采用字符串形式存儲(chǔ)數(shù)據(jù) node_type *left_child; /左孩子指針 node_type *right_child; /右孩子指針 node_type(string k) /構(gòu)造函數(shù) data=k; left_child=NULL; right_child=NULL; ;/以上是二叉樹的結(jié)點(diǎn) 為二叉樹的基本結(jié)構(gòu) class binary_tree /二叉樹類 public:binary_tree(void)root=NULL; /構(gòu)造函數(shù) 建立根節(jié)點(diǎn) node_type *root; /根節(jié)點(diǎn)void evaluate(void) /對(duì)二叉樹的

12、根節(jié)點(diǎn)進(jìn)行運(yùn)算 evaluate(root); void evaluate(node_type *prt)/重載 當(dāng)參數(shù)為二叉樹的運(yùn)算符結(jié)點(diǎn)時(shí)/且左孩子和右孩子不是運(yùn)算符時(shí)對(duì)二叉樹進(jìn)行運(yùn)算 if(IsOperator(prt->data)&&!IsOperator(prt->left_child->data)&&!IsOperator(prt->right_child->data) float num=0; float num1=atof(prt->left_child->data.c_str();/將data轉(zhuǎn)換成ch

13、ar型數(shù)據(jù) 然后用atof將char轉(zhuǎn)換成浮點(diǎn)數(shù) float num2=atof(prt->right_child->data.c_str(); if(prt->data="+") num=num1+num2; else if(prt->data="-") num=num1-num2; else if(prt->data="*") num=num1*num2; else if(prt->data="/") num=num1/num2; else if(prt->data=&

14、quot;") num=pow(num1,num2); cout<<num<<'t'/對(duì)每個(gè)結(jié)點(diǎn)計(jì)算后的中間結(jié)果 stringstream bob;/定義一個(gè)流對(duì)象 bob<<num;/將數(shù)據(jù)存到bob對(duì)象里 string temp(bob.str(); /將bob里的數(shù)據(jù)轉(zhuǎn)換成string然后賦值給temp prt->data=temp;/將計(jì)算的結(jié)果賦值給當(dāng)前結(jié)點(diǎn) prt->left_child=NULL; /然后刪除左右孩子結(jié)點(diǎn) prt->right_child=NULL; else if(prt->l

15、eft_child=NULL&&prt->right_child=NULL);/如果左后孩子都為空則不作操作 else evaluate(prt->left_child); evaluate(prt->right_child); evaluate(prt);/如果不滿足上面的條件 則先運(yùn)算左孩子 再運(yùn)算右孩子 再運(yùn)算本身 /上述函數(shù)為一個(gè)遞歸調(diào)用 即后序遍歷 /從根節(jié)點(diǎn)開始計(jì)算 如果子樹中不為空且不為數(shù)據(jù)則先遍歷左子樹然后遍歷右子樹然后計(jì)算根節(jié)點(diǎn) ;/以上為二叉樹類以及其中包含的功能函數(shù) node_type *build_node(string x) /建立結(jié)

16、點(diǎn)函數(shù)并將x存入結(jié)點(diǎn)的數(shù)據(jù)域里 node_type *new_node; new_node=new node_type(x); return(new_node); bool calculator1(char OperatorA,char OperatorB) /判斷運(yùn)算符A和B優(yōu)先級(jí)是否相等 if(OperatorA=OperatorB|(OperatorA='*'&&OperatorB='/')|(OperatorA='/'&&OperatorB='*')|(OperatorA='+

17、9;&&OperatorB='-')|(OperatorA='-'&&OperatorB='+') return true; else return false; bool calculator2(char OperatorA,char OperatorB) /判別符號(hào)的優(yōu)先級(jí)。A>B，返回為TRUE,A<=B返回false if(OperatorA='(') return false; else if(OperatorB='(') return false; else

18、if(OperatorB=')') return true; else if(calculator1(OperatorA,OperatorB) return false; else if(OperatorA='') return true; else if(OperatorB='') return false; else if(OperatorA='*')|(OperatorA='/') return true; else if(OperatorB='*')|(OperatorB='/

19、9;) return false; else if(OperatorA='+')|(OperatorA='-') return true; else return false; /采用了中序遍歷的算法來將二叉樹r1拷貝到r2 bool isok(string infix)/此函數(shù)驗(yàn)證式子是否正確，即是否符合運(yùn)算規(guī)則。 char temp;/臨時(shí)字符變量 int error=0;/錯(cuò)誤標(biāo)記 int lb=0; /左括號(hào)的個(gè)數(shù) int rb=0;/右括號(hào)的個(gè)數(shù) if(infix.size()=1 && infix0!='-')/式子的

20、長(zhǎng)度為1且第一個(gè)為負(fù)號(hào) return false;else if(IsOperator(infix0)&& infix0!='-' |/如果第一個(gè)是運(yùn)算符且不為左括號(hào)則表達(dá)式錯(cuò)誤 IsOperator( infixinfix.size()-1)&&infix0!='('&&infixinfix.size()-1!=')')/如果最后一個(gè)字符是運(yùn)算符且第一個(gè)和最后一個(gè)不是括號(hào)則表達(dá)式錯(cuò)誤 return false; for(int m=0;m<infix.size();m+) temp=infi

21、xm; if(m=0 && temp='-' && (isdigit(infix1)!=0 | infix1='(' ) )temp=infix+m;/如果是負(fù)數(shù) if(IsOperand(temp); /如果是數(shù)字則不進(jìn)行操作 else if(IsOperator(temp) if(temp=')') rb+; if(IsOperator(infixm+1)&&(infixm+1='+'|infixm+1='-'|infixm+1='*'|infix

22、m+1='/'|infixm+1=''|infixm+1=')') m+; if(infixm=')') rb+; else if(IsOperator(infixm+1) error+; else if(temp='(') lb+; if(infixm+1='(') m+; lb+; else if(IsOperator(infixm+1)&&infixm+1!='-') error+; else if(IsOperator(infixm+1)&&i

23、nfixm+1='(') m+; lb+; else if(IsOperator(infixm+1) error+; else error+; if(error=0&&lb=rb) /如果沒有錯(cuò)誤且左右括號(hào)匹配則返回邏輯真 return(true); else return(false); int main()binary_tree tree; stack<binary_tree> NodeStack;/運(yùn)算數(shù)棧 stack<char> OpStack;/運(yùn)算符棧 string infix;char choice='y's

24、ystem("cls");char c;while(choice='y'|choice='Y') cout<<"n請(qǐng)輸入表達(dá)式:n" cin>>infix; cout<<"-"<<'n' cout<<"表達(dá)式為: "<<infix<<'n' if(isok(infix) for(int i=0;i<infix.size();i+) c=infixi;if(i=0

25、&& c='-') /若開始為負(fù)，則把零壓入運(yùn)算數(shù)棧，把'-'壓入運(yùn)算符棧binary_tree temp; temp.root=build_node("0"); NodeStack.push(temp);/將運(yùn)算數(shù)壓入數(shù)棧 OpStack.push('-');/將運(yùn)算符壓入符棧 elseif(IsOperand(c) string tempstring; tempstring=c; while(i+1<infix.size()&&IsOperand(infixi+1) tempstrin

26、g+=infix+i; binary_tree temp; temp.root=build_node(tempstring); NodeStack.push(temp); else if(c='+'|c='-'|c='*'|c='/'|c='') if(OpStack.empty() OpStack.push(c); else if(OpStack.top()='(') OpStack.push(c); else if(calculator2(c,OpStack.top() OpStack.push

27、(c); else while(!OpStack.empty()&&(calculator2(OpStack.top(),c)|calculator1(OpStack.top(),c) string temp; temp=OpStack.top(); OpStack.pop();tree.root=build_node(temp);tree.root->right_child=NodeStack.top().root;NodeStack.pop();tree.root->left_child=NodeStack.top().root; NodeStack.pop()

28、; NodeStack.push(tree); tree.root=NULL; OpStack.push(c); else if(c='(') /若中間遇到括號(hào)，則判斷下一位是否為'-'OpStack.push(c); if(infixi+1='-')binary_tree temp;temp.root=build_node("0"); NodeStack.push(temp);OpStack.push('-');+i; else if(c=')') while(OpStack.top()!='(') string temp; temp=OpStack.top(); OpStack.pop();/將棧頂內(nèi)容取出然后作出棧操作 tree.root=build_node(temp);tree.root->right_child=NodeStack.top().root;NodeStack.pop(); tree.root->left_child=NodeStack.top().ro