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 }
?
)
)
