中綴試轉字尾試及字首試并計算其結果

/*

        參考大神nb的代碼，感覺思路不錯！終于搞明白了！一開始不明白在計算表達式的時候，利用棧到底做了什麼！現在感覺我們利用棧就是模拟我們書面上計算表達式，

       将優先級高的運算先計算出來，然後放進棧中，等待下一次的計算

*/

#include<iostream> 

#include<string> 

#include<stack>

#include<cstdio>

using namespace std;

class node

{

public:

     double ret;

     string prefix, suffix;//字首表達式和字尾表達式 

     node()

     {

         ret=0;

         prefix=suffix=""; 

     } 

};

stack<node>optd;//操作數棧

stack<char>optr;//操作符棧

char formula[1000];//表達式以"=" 結束 

int cmp(char ch)//定義符号的優先級

   switch(ch)

   {

      case '#': return -2;

      case '=': return -1;

      case '+':

      case '-': return 1;

      case '*':

      case '/': return 2;

      case '(': return 3;

      case ')': return 0;

   }

   return -2;

}

double deal(double x, char ch, double y)

       case '+': return x+y;

       case '-': return x-y;

       case '*': return x*y;

       case '/': return x/y;

   return 0.0;

void cal()

   int i=0, n;

   node num, aTmp, bTmp;

   while(optr.top()!='=')

      if(formula[i]>='0' && formula[i]<='9')

      {

           sscanf(formula+i, "%lf%n", &num.ret, &n);

           num.prefix.assign(formula+i, n);

           num.suffix.assign(formula+i, n);

           i+=n;

           optd.push(num);

      }

      else

           if(optr.top()=='(' && formula[i]==')')//消除一對括弧 

           {

         optr.pop();

         ++i;

         }

           if(cmp(formula[i]) > cmp(optr.top()) || optr.top()=='(')//目前運算符大于棧頂運算符直接進棧

         optr.push(formula[i]);

     }

     else

        char ch=optr.top(), preTmp[]={ch, ' ', '\0'}, sufTmp[]={' ', ch, '\0'} ;

        optr.pop();//彈出一個棧頂操作符 

        bTmp=optd.top(); optd.pop();//得到第二個操作數 

        aTmp=optd.top(); optd.pop();//得到第一個操作數 

        aTmp.ret=deal(aTmp.ret, ch, bTmp.ret);

        aTmp.suffix+=" " + bTmp.suffix + sufTmp;//得到運算後的字尾式子

        aTmp.prefix=preTmp + aTmp.prefix + " " + bTmp.prefix;//得到運算前的字尾式子

        optd.push(aTmp);//不要忘記将計算的結果放入棧中 

   optr.pop();//别忘記彈出棧頂上的'=' 

int main()

   optr.push('#');//初始化棧頂操作符是‘#’ 

   while(cin>>formula)

       cal();

       node ans=optd.top(); optd.pop();

       cout<<"表達式結果："<<ans.ret<<endl<<"字首試："<<ans.prefix+'='<<endl<<"字尾試："<<ans.suffix+'='<<endl; 

   return 0;

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/p/3785647.html，如需轉載請自行聯系原作者