每日一题春季系列 （六） AcWing 3302. 表达式求值 （ 四则运算带括号 三分钟模板建议背下来）

#include<bits/stdc++.h>
using namespace std;
unordered_map<char,int>p{{'+',1},{'-',1},{'*',2},{'/',2}};
stack<int>num;
stack<char>op;
void eval(){
    auto b=num.top();num.pop();
    auto a=num.top();num.pop();
    auto c=op.top();op.pop();
    int x;
    if(c=='-'){
        x=a-b;
    }
    else if(c=='+')x=a+b;
    else if(c=='*')x=a*b;
    else x=a/b;
    num.push(x);
}
string s;
int main(){
    cin>>s;
    for(int i=0;s[i];i++){
        char c=s[i];
        if(isdigit(c)){
            int j=i,sum=0;
            while(j<s.size()&&isdigit(s[j])){
                sum=sum*10+s[j++]-'0';
            }
            i=j-1;
            num.push(sum);
        }
        else if(c=='('){
            op.push(c);
        }
        else if(c==')'){
            while(op.top()!='(')eval();
            op.pop();
        }
        else{
            while(!op.empty()&&p[op.top()]>=p[c])eval();
            op.push(c);
        }
        
    }while(!op.empty())eval();
    cout<<num.top()<<endl;
}