這是經典的用堆棧先將 infix expression 轉成 postfix expression,接著還是用堆棧來求算結果的算法。很多教科書都省略了例子程序。有的雖然提供了例子程序,卻相當冗長。 這裏分享的是兩個短小精悍的示例,可以分別獨立玩味。 這是將 infix expression 轉成 postfix expression 的程序: #include<iostream> #include<map> using namespace std; class S{ private: int t=0; char a[50]; public: void pu(char c){a[t++]=c;} char po(){return a[--t];} char pe(){return a[t-1];} bool em(){return t==0;} }; int main(){ map<char,int>m={{'+',10},{'-',10},{'*',20},{'/',20}}; S s; char c; string x,y=""; while(cin>>x){ if(x=="(")s.pu(x[0]); else if(x==")")while((c=s.po())!='(')y=y+c+' '; else if(m.find(x[0])!=m.end()){ while(!s.em()&&m[s.pe()]>=m[x[0]])y=y+s.po()+' '; s.pu(x[0]); }else y+=x+' '; } while(!s.em())y=y+s.po()+' '; cout<<y<<endl; return 0; } 執行程序,輸入的時候用空格分隔每個字符和數。 $ g++ -std=c++11 -Wall gt.cpp && ./a.out 2 + 3 * ( 4 - 5 ) * ( 6 - ( 7 - 8 ) ) + 9 2 3 4 5 - * 6 7 8 - - * + 9 + 下麵是計算 postfix expression 的程序。要注意如 “3 4 -” 的出棧順序,當咱們想要 3 - 4 時別一不小心變成了 4 - 3 。除法也有類似的順序問題。我在這被咬了一口 :D #include<iostream> using namespace std; class S{ private: int t=0; int a[50]; public: void pu(int s){a[t++]=s;} int po(){return a[--t];} }; int main(){ S s; string x; while(cin>>x){ if(x=="+")s.pu(s.po()+s.po()); else if(x=="-")s.pu(-s.po()+s.po()); else if(x=="*")s.pu(s.po()*s.po()); else if(x=="/"){int x=s.po();s.pu(s.po()/x);} else s.pu(stoi(x)); } cout<<s.po()<<endl; return 0; } $ g++ -std=c++11 -Wall gt.cpp && ./a.out 2 3 4 5 - * 6 7 8 - - * + 9 + -10 |