1 /*  2         参考大神nb的代码，感觉思路不错！终于搞明白了！一开始不明白在计算表达式的时候，利用栈到底做了什么！现在感觉我们利用栈就是模拟我们书面上计算表达式，  3        将优先级高的运算先计算出来，然后放进栈中，等待下一次的计算  4 */  5 #include<iostream>   6 #include<string>   7 #include<stack>  8 #include<cstdio>  9 using namespace std; 10  11 class node 12 { 13 public: 14      double ret; 15      string prefix, suffix;//前缀表达式和后缀表达式  16      node() 17      { 18          ret=0; 19          prefix=suffix="";  20      }  21 }; 22  23 stack<node>optd;//操作数栈 24 stack<char>optr;//操作符栈 25  26 char formula[1000];//表达式以"=" 结束  27  28 int cmp(char ch)//定义符号的优先级 29 { 30    switch(ch) 31    { 32       case ‘#‘: return -2; 33       case ‘=‘: return -1; 34       case ‘+‘: 35       case ‘-‘: return 1; 36       case ‘*‘: 37       case ‘/‘: return 2; 38       case ‘(‘: return 3; 39       case ‘)‘: return 0; 40    } 41    return -2; 42 } 43  44 double deal(double x, char ch, double y) 45 { 46    switch(ch) 47    { 48        case ‘+‘: return x+y; 49        case ‘-‘: return x-y; 50        case ‘*‘: return x*y; 51        case ‘/‘: return x/y; 52    } 53    return 0.0; 54 } 55  56 void cal() 57 { 58    int i=0, n; 59    node num, aTmp, bTmp; 60    while(optr.top()!=‘=‘) 61    { 62       if(formula[i]>=‘0‘ && formula[i]<=‘9‘) 63       { 64            sscanf(formula+i, "%lf%n", &num.ret, &n); 65            num.prefix.assign(formula+i, n); 66            num.suffix.assign(formula+i, n); 67            i+=n; 68            optd.push(num); 69       } 70       else 71       { 72            if(optr.top()==‘(‘ && formula[i]==‘)‘)//消除一对括弧  73            { 74          optr.pop(); 75          ++i; 76          } 77            if(cmp(formula[i]) > cmp(optr.top()) || optr.top()==‘(‘)//当前运算符大于栈顶运算符直接进栈 78      { 79          optr.push(formula[i]); 80          ++i; 81      } 82      else 83      { 84         char ch=optr.top(), preTmp[]={ch, ‘ ‘, ‘\0‘}, sufTmp[]={‘ ‘, ch, ‘\0‘} ; 85         optr.pop();//弹出一个栈顶操作符  86         bTmp=optd.top(); optd.pop();//得到第二个操作数  87         aTmp=optd.top(); optd.pop();//得到第一个操作数  88         aTmp.ret=deal(aTmp.ret, ch, bTmp.ret); 89          90         aTmp.suffix+=" " + bTmp.suffix + sufTmp;//得到运算后的后缀式子 91         aTmp.prefix=preTmp + aTmp.prefix + " " + bTmp.prefix;//得到运算前的后缀式子 92         optd.push(aTmp);//不要忘记将计算的结果放入栈中  93      } 94       } 95    } 96    optr.pop();//别忘记弹出栈顶上的‘=‘  97 } 98  99 int main()100 {101    optr.push(‘#‘);//初始化栈顶操作符是‘#’ 102    while(cin>>formula)103    {104        cal();105        node ans=optd.top(); optd.pop();106        cout<<"表达式结果："<<ans.ret<<endl<<"前缀试："<<ans.prefix+‘=‘<<endl<<"后缀试："<<ans.suffix+‘=‘<<endl; 107    }108    return 0;109 }