题解 | #表达式求值# 双栈法

这个题绝对属于较难这个级别了吧？谁把他分到简单里了。

难点一个是括号优先级的处理，还有个就是负号的处理，我觉得还是挺难调试的。

#include <cctype>
#include <iostream>
#include <stack>
#include <map>
using namespace std;
map<char,int> mp;
int nextnum(const string &in,int &len,int i){
    string num;
    num.clear();
    len=0;
    while(isdigit(in[i])&&i<in.length()){
        num+=in[i];
        ++i;
        ++len;
    }
    return stoi(num);
}
bool bigger(char a,char b){
    return mp[a]>mp[b];
}
bool smaller(char a,char b){
    return mp[a]<mp[b];
}
int cal(int a,char b,int c){
    switch (b) {
        case '+':
            return a+c;
        case '-':
            return a-c;
        case '*':
            return a*c;
        case '/':
            return a/c;
        default:
            break;
    }
    return 0;
}
int main() {
    string in;
    mp['+']=1;
    mp['-']=1;
    mp['*']=2;
    mp['/']=2;
    mp['(']=0;
    mp[')']=0;
    while (cin >> in) { // 注意 while 处理多个 case
        stack<int> numStack;
        stack<char> charStack;
        int num,num1,num2,len;
        string tem='('+in+')';
        in=tem;
        for(int i=0;i<in.length();++i){
            switch(in[i]){
                case '+':
                case '-':
                    if(in[i-1]=='('){
                        if(isdigit(in[i+1])){
                            num=nextnum(in,len,i+1);
                            numStack.push(-num);
                            i+=len;
                        }
                        break;
                    }
                case '*':
                case '/':
                    if(charStack.empty()){
                        charStack.push(in[i]);
                        break;
                    }
                    if(bigger(in[i],charStack.top())){
                        charStack.push(in[i]);
                    }
                    else{
                        while(!bigger(in[i],charStack.top())){
                            num1=numStack.top(); numStack.pop();
                            num2=numStack.top(); numStack.pop();
                            num = cal(num2, charStack.top(), num1);
                            charStack.pop();
                            numStack.push(num);
                            if(charStack.empty()){break;}
                        }
                        charStack.push(in[i]);
                    }
                    break;
                case '(':
                    charStack.push(in[i]);
                    break;
                case ')':
                    while(!charStack.empty()){
                        if(charStack.top()=='('){
                            charStack.pop();
                            break;
                        }
                        num1=numStack.top(); numStack.pop();
                        num2=numStack.top(); numStack.pop();
                        num = cal(num2, charStack.top(), num1);
                        charStack.pop();
                        numStack.push(num);
                    }
                    break;
                default:
                    if(isdigit(in[i])){
                        num=nextnum(in,len,i);
                        numStack.push(num);
                        i+=len; --i;
                    }
                    break;
            }
        }
        cout<<numStack.top()<<endl;
    }
}
// 64 位输出请用 printf("%lld")