题解 | 表达式求值

class Solution {
public:
    unordered_map<char, int> mp={  //设定优先级，用于判断
        {'+', 1},
        {'-', 1},
        {'*', 2}
    };
  
    //使用两个栈，一个放数字，一个放操作字符，一个操作字符对应两个数字，在字符栈中只允许后一个操作符高于前一个操作符存在
    int solve(string s) {  
        s.erase(remove(s.begin(), s.end(), ' '), s.end());  //去掉空格；
 
        int size = s.length();
        stack<int> nums;
        stack<char> ops;

        for(int i=0; i<size; i++){   //每位处理
            char c = s[i];
            if(c == '('){    //左括号时，记录
                ops.push(c);
            }else if(c == ')'){  //右括号，处理与左括号之间的操作
                while(ops.top() != '('){
                    cal(nums, ops);  //处理函数
                }
                if(!ops.empty())ops.pop();  //弹出左括号；
            }else{
                if(isdigit(c)){  //当时数字时，多位数字的字符进行合并
                    int u=0, j = i;  //u是总和，是要得到的数
                    while(j < size && isdigit(s[j])){
                        u = u*10 + (s[j++] - '0'); //对之前的u进行加和
                    }
                    nums.push(u);
                    i = j-1;
                }else{
                    if(i>0 && (s[i-1] == '-' || s[i-1] == '+' || s[i-1] == '(') ){  //对存在+-4的情况，转变成+0-4
                        nums.push(0);
                    }
                    while(!ops.empty() && ops.top() != '(' && mp[ops.top()] >= mp[c]){
                        cal(nums, ops);  //当遇到-或+的前面是*或+或-，*遇到*，都对之前的操作符进行处理，也就是后面遇到优先级低或者相等的情况；
                    }
                    ops.push(c);
                }
            }
        }

        while(!ops.empty()){  //处理剩余
            cal(nums, ops);
        }
        return nums.top();
    }

    void cal(stack<int>& nums, stack<char>& ops){
        if(nums.size()<2 || ops.empty())return;

        int b = nums.top();nums.pop();
        int a = nums.top();nums.pop();
        char op = ops.top();ops.pop(); //一个操作符配两个操作数

        int res = 0;
        if(op == '+')res = a+b;
        else if(op == '-')res = a-b;
        else if(op == '*')res = a*b; //直接判断匹配
 
        nums.push(res); //加入总和数
    }
};