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

2、其他的結點為操作符。a建立表達式樹。二叉樹的存儲采用了鏈式存儲。當要創建二叉樹時，先從表達式尾部向前搜索，找到第一個優先級最低的運算符，建立以這個運算符為數據元素的根結點。注意到表達式中此運算符的左邊部分對應的二叉绔為根結點的左子樹，右邊部分對應的是二叉绔為根結點的右子樹，根據地這一點，可用遞歸調用自己來完成對左右子樹的構造。b求表達式的值。求值時同樣可以采用遞歸的思想，對表達式進行后序遍歷。先遞歸調用自己計算左子樹所代表的表達式的值，再遞歸調用自己計算右子樹代表的表達式的值，最后讀取根結點中的運算符，以剛才得到的左右子樹的結果作為操作數加以計算，得到最終結果。四設計與實現為了使用二叉樹實現表

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

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

5、9;n' 2.進行簡單的四則運算對輸入的表達式首先判斷正誤，然后按照運算的優先級分別進行運行，并且分別輸出每步運算的結果。先進行乘方，然后乘除，最后再計算加減，先算括號內后算括號外，正確度一目了然。（1）對于負數也可以進行相應的加減乘除以及乘方的運算。對于負數的運算，也和正數一樣，先算括號內的后算括號外的，其次算乘方，再算乘除，最后進行加減的運算。負數的加減乘除：負數的乘方運算：（1） 正指數冪運算：（2） 負指數冪運算： 可以進行小數的計算，對于小數采用浮點數的存儲方式和輸出方式，計算精度可以取到小數點后五位。小數的加減乘除：小數的運算，依然按照先乘除后加減，先算括號內后算括號外的順

6、序運算。小數的乘方和開方：（1） 正小數冪次方：（2） 負小數冪次方：（3） 開正小數次方：（4） 開負小數次方：五測試與結論 此報告在C-Free5.0環境下進行測試。C-Free是一款C/C+集成開發環境（IDE）。C-Free中集成了C/C+代碼解析器，能夠實時解析代碼，并且在編寫的過程中給出智能的提示。C-Free提供了對目前業界主流C/C+編譯器的支持，可以在C-Free中輕松切換編譯器。可定制的快捷鍵、外部工具以及外部幫助文檔，使在編寫代碼時得心應手。完善的工程/工程組管理使你能夠方便的管理自己的代碼。以下是各種測試用例。注：較為簡單和常規的測試用例在上一部分“算法的實現”中已經給

7、出，下面只給出一些具有代表性的測試用例。1.表達式錯誤的情況在表達式錯誤的情況下，程序能夠運行，但是不能夠正常運算，而是給出錯誤的提示信息，提醒重新輸入正確的表達式。下圖表示以0作為除數時程序所給的提示信息“Infinity”下圖為計算表達式0（-3）時候的輸出，由于表達式沒有數學意義，所以也就沒有正確的結果，因而程序運行后得到的結果是“Infinity”.下圖顯示的是輸入的表達式不符合數學規律時的錯誤提示信息。下圖表示輸入表達式中含有不合法的字符，例如字母時候，程序運行時所給的提示信息。下圖所示為表達式錯誤的另外一種情形，即輸入的括號多余的情形。下面兩個測試用例，為表達式輸入錯誤的情況，在下

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

9、構造兩個棧用來存儲數據和運算符 using namespace std; bool IsOperator(string mystring)/判斷參數string是否是運算符 是返回邏輯值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)/ 驗證是否是數 if(ch>='0')&&(ch<='9')|ch='.') return true; else return false; /以上三個是起判斷作用的函數 class node_type/結點類 publ

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

12、根節點進行運算 evaluate(root); void evaluate(node_type *prt)/重載 當參數為二叉樹的運算符結點時/且左孩子和右孩子不是運算符時對二叉樹進行運算 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轉換成ch

13、ar型數據 然后用atof將char轉換成浮點數 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'/對每個結點計算后的中間結果 stringstream bob;/定義一個流對象 bob<<num;/將數據存到bob對象里 string temp(bob.str(); /將bob里的數據轉換成string然后賦值給temp prt->data=temp;/將計算的結果賦值給當前結點 prt->left_child=NULL; /然后刪除左右孩子結點 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);/如果不滿足上面的條件 則先運算左孩子 再運算右孩子 再運算本身 /上述函數為一個遞歸調用 即后序遍歷 /從根節點開始計算 如果子樹中不為空且不為數據則先遍歷左子樹然后遍歷右子樹然后計算根節點 ;/以上為二叉樹類以及其中包含的功能函數 node_type *build_node(string x) /建立結

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

17、9;&&OperatorB='-')|(OperatorA='-'&&OperatorB='+') return true; else return false; bool calculator2(char OperatorA,char OperatorB) /判別符號的優先級。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)/此函數驗證式子是否正確，即是否符合運算規則。 char temp;/臨時字符變量 int error=0;/錯誤標記 int lb=0; /左括號的個數 int rb=0;/右括號的個數 if(infix.size()=1 && infix0!='-')/式子的

20、長度為1且第一個為負號 return false;else if(IsOperator(infix0)&& infix0!='-' |/如果第一個是運算符且不為左括號則表達式錯誤 IsOperator( infixinfix.size()-1)&&infix0!='('&&infixinfix.size()-1!=')')/如果最后一個字符是運算符且第一個和最后一個不是括號則表達式錯誤 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;/如果是負數 if(IsOperand(temp); /如果是數字則不進行操作 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) /如果沒有錯誤且左右括號匹配則返回邏輯真 return(true); else return(false); int main()binary_tree tree; stack<binary_tree> NodeStack;/運算數棧 stack<char> OpStack;/運算符棧 string infix;char choice='y's

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

25、&& c='-') /若開始為負，則把零壓入運算數棧，把'-'壓入運算符棧binary_tree temp; temp.root=build_node("0"); NodeStack.push(temp);/將運算數壓入數棧 OpStack.push('-');/將運算符壓入符棧 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='(') /若中間遇到括號，則判斷下一位是否為'-'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();/將棧頂內容取出然后作出棧操作 tree.root=build_node(temp);tree.root->right_child=NodeStack.top().root;NodeStack.pop(); tree.root->left_child=NodeStack.top().ro