大家好!今天帶來的是自己實現的用C++實現的10以內整數的科學計算器,其中涉及中綴表達式到尾碼表達式(逆波蘭表示法),尾碼表達式的求值,涉及棧這一數據結構的壓棧,彈棧,存取棧頂元素和判斷棧是否為空等操作. 計算器在生活中應用廣泛.眾所周知,我們往計算器中輸入的是由數字,運算符組成的表達式,這個表達式 ...
大家好!今天帶來的是自己實現的用C++實現的10以內整數的科學計算器,其中涉及中綴表達式到尾碼表達式(逆波蘭表示法),尾碼表達式的求值,涉及棧這一數據結構的壓棧,彈棧,存取棧頂元素和判斷棧是否為空等操作.
計算器在生活中應用廣泛.眾所周知,我們往計算器中輸入的是由數字,運算符組成的表達式,這個表達式被稱為中綴表達式,因其運算符寫在數的中間,如(1+2)*3.而用棧實現的計算器所處理的是尾碼表達式,即運算符在數字的後面,這涉及到中綴表達式轉尾碼表達式的演算法.如(1+2)*3的尾碼表達式是12+3*.尾碼表達式也成為逆波蘭表示法,因其是一種由波蘭數學家揚·武卡謝維奇在1920年引入的數學表達式方式.
整個工程涉及兩個編譯單元,即main.cpp主函數文件和caculatefuncs.h自定義頭文件.main.cpp的代碼十分簡單,就是讀入中綴表達式,然後調用toPostFix函數,轉變為尾碼表達式,再調用toDouble函數將尾碼表達式求值.代碼如下:
#include <iostream> #include"caculatefuncs.h" using namespace std; int main(){ string infix; cout<<"輸入中綴表達式:"<<endl; cin>>infix; string postfix = toPostFix(infix); cout<<"對應的尾碼表達式(逆波蘭表示法)為"<<postfix<<endl; cout<<"表達式的值為:"<<toDouble(postfix)<<endl; return 0; }
caculatefuncs.h中包含兩個函數toPostFix和toDouble的實現.中綴轉尾碼的演算法有一點複雜,規則如下:
toPostFix函數的實現:
1 string toPostFix(string infix){ //中綴表達式轉尾碼表達式函數 2 3 const int n = infix.length(); 4 const char PRI1 = '2'; 5 const char PRI2 = '1'; //優先順序定義 6 const char UN = '0'; 7 string postfix( n, ' '); //預留尾碼表達式字元串 8 string priority( n, ' '); //預留優先順序字元串 9 int i = 0; // infix序數 10 int j = 0; //priority序數 11 int k = 0; //postfix序數 12 13 for( ; i < n; i++){ 14 if(infix.at(i) >= '0' && infix.at(i) <= '9') 15 postfix.at(k++) = infix.at(i); //數字直接存入 16 17 else{ 18 19 switch(infix.at(i)){ 20 case '+': priority.at(j++) = PRI2; 21 break; 22 case '-': priority.at(j++) = PRI2; 23 break; 24 case '*': priority.at(j++) = PRI1; 25 break; 26 case '/': priority.at(j++) = PRI1; 27 break; 28 case '(': priority.at(j++) = UN; 29 break; 30 case ')': while(charStack.top() != '('){ 31 postfix.at(k++) = charStack.top(); 32 charStack.pop(); 33 j--; 34 } 35 charStack.pop(); 36 j--; 37 break; 38 default: cout<<"運算符錯誤,程式退出"<<endl; 39 exit(0); //優先順序字元串中存放代表優先順序的字元常量 40 } 41 if( j > 1 && priority.at(j-1) < priority.at(j-2) && priority.at(j-1) != UN && priority.at(j-2) != UN){ //當前運算符優先順序比棧頂運算符低,則待高優先順序運算符彈棧後入棧 42 postfix.at(k++) = charStack.top(); 43 charStack.pop(); 44 charStack.push(infix.at(i)); 45 priority.at(j-2) = priority.at(j-1); 46 j--; 47 } 48 else if( infix.at(i) != ')') 49 charStack.push(infix.at(i)); 50 if( j > 1){ 51 for( int m = j-2; (m >=0)&&(priority.at(m) > priority.at(j-1)); m--){//優先順序比較,高於當前運算符優先順序的彈棧 52 if(priority.at(m) != UN && priority.at(j-1) != UN ){ 53 postfix.at(k++) = charStack.top(); 54 charStack.pop(); 55 j--; 56 } 57 } 58 } 59 } 60 } 61 while( !charStack.empty()){ //棧中字元全部彈出 62 postfix.at(k++) = charStack.top(); 63 charStack.pop(); 64 } 65 postfix = postfix.substr(0, k); 66 return postfix; 67 }
至於尾碼表達式求值的演算法,我們都比較熟悉了.遍歷尾碼表達式,若是操作數,則壓入棧;若為運算符,則從棧中彈出兩個操作數,進行計算,然後將計算結果壓棧.直至遍歷完成時,棧為空.
toDouble函數的實現:
1 double toDouble(string postfix){ //逆波蘭表示法轉換為整數函數 2 3 const int n = postfix.length(); 4 double a = 0; //第一個操作數 5 double b = 0; //第二個操作數 6 7 for(int i = 0; i < n; i++){ 8 char temp = postfix.at(i); 9 if(temp >= '0' && temp <= '9') //是數字則壓棧 10 doubleStack.push( temp- '0'); 11 else{ //運算符分情況討論 12 switch(temp){ 13 case '+': b = doubleStack.top(); 14 doubleStack.pop(); 15 a = doubleStack.top(); 16 doubleStack.pop(); 17 doubleStack.push(a + b); //運算結果壓棧 18 break; 19 case '-': b = doubleStack.top(); 20 doubleStack.pop(); 21 a = doubleStack.top(); 22 doubleStack.pop(); 23 doubleStack.push(a - b); 24 break; 25 case '*': b = doubleStack.top(); 26 doubleStack.pop(); 27 a = doubleStack.top(); 28 doubleStack.pop(); 29 doubleStack.push(a * b); 30 break; 31 case '/': b = doubleStack.top(); 32 if(b == 0){ 33 cout<<"除零異常,程式退出"<<endl; 34 exit(0); 35 } 36 doubleStack.pop(); 37 a = doubleStack.top(); 38 doubleStack.pop(); 39 doubleStack.push(a / b); 40 break; 41 default: cout<<"運算符錯誤,程式退出"<<endl; 42 exit(0); 43 } 44 } 45 } 46 return doubleStack.top(); //最終結果彈棧 47 }
這個簡單計算器實現只能處理10以內的整數,但結果可以為浮點數.可以處理括弧,考慮運算符優先順序.棧的是運用了C++的模板類Stack,類聲明被包含在頭文件stack中.本程式使用的兩個棧定義如下:
stack<char> charStack; //存放字元的棧 stack<double> doubleStack; //存放整數的棧
謝謝大家!轉載請註明出處,謝謝合作!