Stack AcWing 3302. Expression evaluation

Original link

AcWing 3302. Expression evaluation

Algorithm tags

Stack Expression evaluation

Ideas

Excerpt from the solution

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 10005;
stack<int> num;
stack<int> op;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void eval(){
    int b=num.top();
    num.pop();
    int a=num.top();
    num.pop();
    char 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);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //  Define operator priority 
    unordered_map<char, int> ump={
   {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string s;
    cin>>s;
    rep(i, 0, s.size()){
    	//  Extract the number in the string  
        if(isdigit(s[i])){
            int j=i, x=0;
            while(j<s.size()&&isdigit(s[j])){
                x=x*10+s[j++]-'0';
            }
            i=j-1;
            num.push(x);
        }else if(s[i]=='('){ // (  Push 
            op.push(s[i]);
        }else if(s[i]==')'){ // )  And  (  Between numbers 
            while(op.top()!='('){
                eval();
            }
            // )  Out of the stack 
            op.pop();
        }else{ // + - * /  operation    The operator to be stacked has low priority , Then calculate first   Then put the calculation results on the stack 
            while(op.size()&&op.top()!='('&&ump[op.top()]>=ump[s[i]]){
                eval();
            }
            //  otherwise   First in stack   Post calculation 
            op.push(s[i]);
        }
    }
    //  Put all non operational operators   Front to back operation 
    while(op.size()){
        eval();
    }
    printf("%lld", num.top());
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support