题解 | #表达式计算4#

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl '\n'

ll fastpow(ll a,ll b){//快速幂
    ll ans=1;
    while(b){
        if(b&1)ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}

unordered_map<char,int>pr={{'+',1},{'-',1},{'*',2},{'/',2},{'^',3}};//优先级


stack<int>num;//数字栈
stack<char>op;//运算符栈
int cnt1=0;//当前左括号的数量
void calc(){//一次计算
    if(num.size()<2||op.empty())return;
    int b=num.top();num.pop();
    int a=num.top();num.pop();
    char c=op.top();op.pop();
    int ans=0;
    switch(c){
        case '+':ans=a+b;break;
        case '-':ans=a-b;break;
        case '*':ans=a*b;break;
        case '/':ans=a/b;break;
        case '^':ans=fastpow(a,b);break;
        default:ans=1;
    }
    num.push(ans);
}

void solve()
{
    string s;cin>>s;
    for(int i=0;i<s.length();i++){
        char c=s[i];
        if(c==' ')continue;//跳过空格
        if(c>='0'&&c<='9'){
            int j=i;
            int nu=0;
            while(j<s.length()&&s[j]>='0'&&s[j]<='9')nu=nu*10+s[j++]-'0';
            num.push(nu);
            i=j-1;
        }
        else if(c=='('){
            op.push('(');
            cnt1++;
        }
        else if(c==')'){
            if(!cnt1)continue;//很重要，跳过多余的)
            while(!op.empty()&&op.top()!='(')calc();
            if(!op.empty())op.pop();
            cnt1--;
        }
        else{
            if(c=='-'&&(i==0||s[i-1]=='('))num.push(0);
            while(!op.empty()&&op.top()!='('){
                if(pr[op.top()]>pr[c])calc();
                else if(pr[op.top()]==pr[c]&&c!='^')calc();
                else break;
                
            }
            op.push(c);
        }
    }
    while(!op.empty()){
        if(op.top()=='('){//跳过多余的(
            op.pop();
            continue;
        }
        calc();
    }
    cout<<num.top()<<endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t=1;//cin>>t;
    
    while(t--)solve();
     
    return 0;
}