数据结构--表达式求值

 1 #include<iostream>
 2 #include<cstring>
 3 #include<string>
 4 #include<unordered_map>
 5 #include<stack>
 6 using namespace std;
 7 stack<int> num;
 8 stack<char> op;
 9 void eval(){
10     auto b=num.top(); num.pop();
11     auto a=num.top(); num.pop();
12     auto c=op.top(); op.pop();
13     int x;
14     if(c==‘+‘) x=a+b;
15     else if(c==‘-‘) x=a-b;
16     else if(c==‘*‘) x=a*b;
17     else if(c==‘/‘) x=a/b;
18     num.push(x);
19 }
20 int main(void){
21     unordered_map<char,int> pro{{‘+‘,1},{‘-‘,1},{‘*‘,2},{‘/‘,2}};
22     string str;
23     cin>>str;
24     for(int i=0;i<str.size();i++){
25         auto c=str[i];
26         if(isdigit(c)){
27             int x=0;
28             int j=i;
29             while(j<str.size()&&isdigit(str[j])){
30                 x=x*10+str[j]-‘0‘;
31                 j++;
32             }
33             i=j-1;
34             num.push(x);
35         }else if(c==‘(‘){
36             op.push(‘(‘);
37         }else if(c==‘)‘){
38             while(op.top()!=‘(‘) eval();
39             op.pop();
40         }else{
41             while(op.size()&&pro[op.top()]>=pro[c]) eval();
42             op.push(c);
43         }
44     }
45     while(op.size()) eval();
46     cout<<num.top()<<endl;
47     return 0;
48 }