小c++程序示例，解析並計算算術表達式如 2 + 3 * ( 4 - 5 ) * ( 6 - ( 7 - 8 ) ) + 9

這是經典的用堆棧先將 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