棧的應用有很多，我們最熟悉的函數調用與遞歸等對編譯器來說都是用棧的工作原理來實現的。還有我們的浏覽器中有一個向後退選項，這就是一個棧的應用了（這個是<大話數據結構>中的舉例）。還有就是本篇要講的表達式求值了。 我們知道C/C++是基於表達式的程序設計語言，可見表達式對於語言的重要性了。至於什麼是表達式等話題這裡就不討論了，直接說表達式的三種類型，他們分別是：前綴表達式，中綴表達式，後綴表達式。在這裡只講對於雙目運算符的情況，單目與三目等不作討論。 中綴表示形式：<操作數><操作符><操作數>，例如A+B 前綴表示形式：<操作符><操作數><操作數>，例如+AB 後綴表示形式：<操作數><操作數><操作數>，例如AB+ 利用中綴形式求表達式的值，在各種程序設計語言和計算器中也經常使用，需要使用兩個棧，一個存放操作數，一個存放操作符。在這裡我們只講述如何利用後綴形式求表達式的值。 利用後綴形式求表達式的值只需要一個棧即可，且操作方便，但由中綴形式的表達式轉換為後綴形式就需要一個算法與過程了。 先給出一個中綴形式的表達式：A + B * (C - D) - E / F，其後綴形式為：ABCD- * + EF / -。如何將其轉換為一個後綴形式的表達式呢？這需要一個算法實現，在展開算法之前要考慮幾個問題，一個是怎麼將操作符的優先級表現在其後綴形式的順序中，一個是括號怎麼處理。 針對第一個問題，我們將各個常見的二目運算符進行一個優先級的排序 操作符 ch # ( *,/,% +,- ) isp 0 1 6 3 6 icp 0 6 4 2 1 因為要先壓棧一個符號作為標志，所以定義#為0，意思是所有的操作符都比他的優先級高。isp與icp是操作符在棧內棧外的優先級是不同的，isp(in stack prioroty) ，icp(in coming priority)。 現在問題都解決了，就是一個算法的實現了，下面請看算法： <1> 操作符棧初始化，將結束符'#'壓入棧。然後讀入中綴表達式的首字符ch。 <2> 重復執行以下步驟，直到ch = '#'同時棧頂的操作符也是'#'時，停止循環。 a:若ch是操作符直接輸出，讀入下一個字符ch。 b:若是操作符，判斷ch的優先級icp值域位於棧頂的操作符op的優先級isp值: @若icp(ch) > isp(op)，另ch進棧，讀入下一個字符。 @若icp(ch) < isp(op)，退出棧頂操作符並輸出該字符，注意這裡沒有讀入下一個字符而是繼續循環比較棧中的元素。這一步專門為了括號考慮的。 @若icp(ch) == isp(op)，退棧但不輸出，若退出的是'('號，讀入下一個字符ch。 <3> 算法結束，輸出序列即為所需要的後綴表達式。 下面就貼代碼了： [cpp] #pragma once #include<iostream> //#include<stack>//STL中的棧 自己的棧也可以達到這個效果 #include"S_stack.h" #include<vector> #include<string> using namespace std; class Calculator { private: string expression_str;//用於用戶輸入的表達式承接的字符串 vector<char> char_elem;//中綴轉換成後綴後的字符容器 動態增長 Stack<float> stk_float;//用於後綴計算表達式的浮點數棧 核心變量 void Do_Operator(char opt_ch);//根據操作符 去棧中去取兩個元素計算 bool Get_operands(float &left_optnum,float &right_optnum);//從棧中取出左和右操作數 用於計算 bool is_numelem(char ch);//判斷是否為操作數 float exchange_num(char num_ch);//數值型字符轉換成數字 void exchange_exp();//中綴轉換為後綴的表達式存放在字符數組中，便於後綴計算 int Get_isp(char opt_ch);//返回操作符的棧內優先級數 int Get_icp(char opt_ch);//返回即將進棧操作符的優先級數 void Show_result();//返回計算結果 public: Calculator(string str);//計算器接受一個字符串型表達式 ~Calculator(); void Running();//對外計算接口 }; [cpp] #include"Calculator.h" #include<iostream> using namespace std; //初始化 一些數據 用於後期計算 Calculator::Calculator(string str) { expression_str = str; } Calculator::~Calculator() { } //返回操作符的棧內優先級數 int Calculator::Get_isp(char opt_ch) { switch(opt_ch) { case'#': return 0; break; case'(': return 1; break; case'*':case'/':case'%': return 5; break; case'+':case'-': return 3; break; case')': return 6; break; } } //返回即將進棧操作符的優先級數 int Calculator::Get_icp(char opt_ch) { switch(opt_ch) { case'#': return 0; break; case'(': return 6; break; case'*':case'/':case'%': return 4; break; case'+':case'-': return 2; break; case')': return 1; break; } } //判斷是否為操作數 bool Calculator::is_numelem(char ch) { if(48<=ch && ch<=57)//這裡的局限性是 只能判斷和後期計算10以內的四則運算 return true; else return false; } //中綴轉換為後綴的表達式存放在字符數組中，便於後綴計算 void Calculator::exchange_exp() { Stack<char> stk_char;//棧 用於存放操作符 並處理他們的優先級 stk_char.push('#');//先把 標准字符壓棧 char isp_ch;//棧內 字符臨時變量 string::size_type i=0; while((stk_char.isEmpty()==false) && (i<expression_str.length())) { if(is_numelem(expression_str[i]))//如果是操作數 輸出到字符容器中 { char_elem.push_back(expression_str[i]); i++; } else { isp_ch = stk_char.Get_topelem();//彈出棧頂操作符與待進棧的作比較 if(Get_icp(expression_str[i]) > Get_isp(isp_ch)) { stk_char.push(expression_str[i]);//如果待進棧的優先級高則入棧 i++; } else if(Get_icp(expression_str[i]) < Get_isp(isp_ch)) { char_elem.push_back(stk_char.pop()); } else { if(stk_char.pop() == '(') i++; } } } } //數值型字符轉換為數字 float Calculator::exchange_num(char num_ch) { switch(num_ch) { case'0': return 0; break; case'1': return 1; break; case'2': return 2; break; case'3': return 3; break; case'4': return 4; break; case'5': return 5; break; case'6': return 6; break; case'7': return 7; break; case'8': return 8; break; case'9': return 9; break; } } //運算函數 並輸出結果 void Calculator::Running() { exchange_exp();//轉換表達式 for(vector<char>::size_type i=0;i<char_elem.size();i++) { switch(char_elem[i]) {//當遇到操作符後作出判斷 case'+':case'-':case'*':case'/': { Do_Operator(char_elem[i]);//根據操作符並取棧頭兩個元素計算並把並把結果壓棧 continue; } //當不為操作符時 default: { if(is_numelem(char_elem[i]))//判斷是否為數字型字符 { stk_float.push(exchange_num(char_elem[i]));//轉換為數字後壓棧 continue; } else { //當運行到此說明有非法字符或是程序未定義的字符 導致運算無法繼續進行 cout<<"不合法的字符出現 導致運算出錯 建議清棧 重新輸入 並檢查表達式的合法性"<<endl; exit(1); } } }//開關語句後括號 }//for結構後括號 Show_result();//顯示結果 } //從棧中取出左和右操作數 用於計算 bool Calculator::Get_operands(float &left_optnum,float &right_optnum) { if(stk_float.isEmpty())//判棧空 { cout<<"缺少右操作數"<<endl; return false; } right_optnum = stk_float.pop();//取右操作數 if(stk_float.isEmpty())//取出一個右操作數後 再次作出判斷 { cout<<"缺少左操作數"<<endl; return false; } left_optnum = stk_float.pop();//取出左操作數 return true;//返回true } //根據操作符 去棧中去取兩個元素計算 void Calculator::Do_Operator(char opt_ch) { float left,right,value; if(Get_operands(left,right))//棧中取出頭兩個元素 { switch(opt_ch) { case'+': { value = left + right; stk_float.push(value);//相加後結果壓棧 break; } case'-': { value = left - right; stk_float.push(value);//相減 壓棧 break; } case'*': { value = left * right; stk_float.push(value);//相乘 壓棧 break; } case'/': if(right == 0) { cout<<"/ 操作符 右操作數為0"<<endl; exit(1); } else { value = left / right; stk_float.push(value);//相除 壓棧 } break; } } } www.2cto.com //保留並輸出最後結果 void Calculator::Show_result() { cout<<"表達式計算結果:"<<endl; cout<<expression_str<<" = "<<stk_float.Get_topelem();//計算結束後 棧頂元素為計算結果 }
