逆波兰式

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 int jdgCode(char flag)//定于操作符运算
 4 {
 5     if(flag == '+')
 6         return 1;
 7     if(flag == '-')
 8         return 2;
 9     if(flag == '*')
10         return 3;
11     if(flag == '/')
12         return 4;
13 }
14 double Compute(string cpu)
15 {
16     stack <double> ans;
17     for(auto iter = cpu.begin();iter != cpu.end();iter++){
18         if(*iter >= '0' && *iter <= '9')
19             ans.push(*iter - '0');
20         else {
21             double r1,r2;
22             r1 = ans.top();
23             ans.pop();
24             r2 = ans.top();
25             ans.pop();
26             switch(jdgCode(*iter)){
27                 case 1: ans.push(r2 + r1);break;
28                 case 2: ans.push(r2 - r1);break;
29                 case 3: ans.push(r2 * r1);break;
30                 case 4: ans.push(r2 / r1);break;
31             }
32         }
33     }
34     return ans.top();
35 }
36 int prio(char a)
37 {
38     if(a == '*' || a == '/')
39         return 2;
40     else if(a == '+' || a == '-')
41         return 1;
42     else 
43         return 0;//左括号优先级
44 }
45 void Dispose(string& ms,string& as)//处理成后缀表达式
46 {
47     stack <char> ct;//定义一个ct容器存储运算符
48     for(auto iter = ms.begin();iter != ms.end();iter++){
49         if(*iter >= '0' && *iter <= '9')//如果是数字，直接入栈
50             as += *iter;
51         else{
52             if(ct.empty() || *iter == '(')//如果是空栈，或者是左括号，直接入栈
53                 ct.push(*iter);
54             else if(*iter == ')'){
55                 while(ct.top() != '('){//把左括号和右括号里面的操作符出栈
56                     as += ct.top();
57                     ct.pop();
58                 }
59                 ct.pop();//弹出左括号
60             }
61             else{
62                 while(!ct.empty() && prio(*iter) <= prio(ct.top())){//把优先级低于当前操作符的操作符出栈
63                     as += ct.top();
64                     ct.pop();
65                 }
66                 ct.push(*iter);//把当前操作符入栈
67             }
68         }
69     }
70     while(!ct.empty()){//如果栈区还有操作符
71         as += ct.top();
72         ct.pop();
73     }
74 }
75 int main()
76 {
77     string ms;//中缀表达式
78     string as;//后缀表达式
79     cin >> ms;
80     Dispose(ms,as);//将中缀表达式处理为后缀表达式
81     cout << as << endl;//输出处理后的后缀表达式
82     cout << "Result:" << Compute(as) << endl;//输出后缀表达式计算结果
83     return 0;
84 }