1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string t[100];
 4 int tot=0;
 5 int to_num(string &s)
 6 {
 7     int x=0,f=1;
 8     for(auto &p:s)
 9     {
10         if(p=='-')f=-1;
11         else x=x*10+(p^48);
12     }
13     return x*f;
14 }
15 int main()
16 {
17     unordered_map<char,int>mp;
18     mp['*']=2;
19     mp['/']=2;//如果是给除号自己替换 
20     mp['+']=1;
21     mp['-']=1;
22     string s="16+2*30/4"; //2+(3+4)*5  16+2*30/4
23     stack<char>st;
24     int x=0,ok=0;            
25     for(int i=0;i<s.size();i++)
26     {
27         
28         if(s[i]>='0'&&s[i]<='9')
29         {
30             x=x*10+s[i]-'0';
31             ok=1;
32         }
33         else
34         {
35             if(ok)
36             {
37                 t[tot++]=to_string(x);
38                 x=0;
39                 ok=0;//记录数字
40             }
41             if(s[i]=='(')st.push('(');
42             else if(s[i]==')')
43             {
44                 while(st.top()!='(')//如果是右括号就把运算符加入字符串后面，直到遇到左括号
45                 {
46                     t[tot++]=st.top();
47                     st.pop();
48                 }
49                 st.pop();//把左括号出栈
50             }
51             else 
52             {
53                 if(!st.size()||st.top()=='(')st.push(s[i]);//左括号或者是空栈直接入栈
54                 else
55                 {
56                     while(st.size()&&mp[st.top()]>=mp[s[i]])//如果是运算符，考虑栈顶元素与当前元素的优先级，要保证栈内优先级严格递增
57                     {
58                         t[tot++]=st.top();
59                         st.pop();
60                     }
61                     st.push(s[i]);
62                 }
63             }
64         }
65     }
66     if(x)t[tot++]=to_string(x);
67     while(st.size())
68     {
69         t[tot++]=st.top();
70         st.pop();
71     }
72     //for(int i=0;i<tot;i++)cout<<t[i]<<" "；
　　　　//这里开始后缀表达式的计算
73     stack<int>myst;
74     for(int i=0;i<tot;i++)
75     {
76         if(t[i]=="+"||t[i]=="-"||t[i]=="*"||t[i]=="/")
77         {
78             int x1=0,x2=0;
79             x2=myst.top();
80             myst.pop();
81             x1=myst.top();
82             myst.pop();
83             if(t[i]=="+")myst.push(x1+x2);
84             else if(t[i]=="-")myst.push(x1-x2);
85             else if(t[i]=="*")myst.push(x1*x2);
86             else if(t[i]=="/")myst.push(x1/x2);    
87         }
88         else myst.push(to_num(t[i]));
89     }
90     int ans=myst.top();
91     cout<<ans<<endl;
92     return 0;
93 }