题解 | #表达式求值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
   unordered_map<char, int> pri = {
        {'-',1},{'+',1},{'*',2}
    };
    int solve(string s) {
        // write code here
        //双栈
        stack<char> ops;
        stack<int> nums;
        nums.push(0);
        int n = s.size();
        for(int i = 0;i < n;i ++) {
            if(isdigit(s[i])) {
                int j = i;
                while(j < n&&isdigit(s[j])) j ++;
                int num = stoi(s.substr(i,j-i));
                nums.push(num);
                i = j - 1;
            } else if (s[i] == '(') {
                ops.push(s[i]);
            } else if (s[i] == ')') {
                while(!ops.empty()&&ops.top()!='(') {
                    calc(nums,ops);
                }
                ops.pop();
            } else {
                //新操作
                while(!ops.empty()&&ops.top() != '(') {
                    if(pri[ops.top()] >= pri[s[i]]) {
                        calc(nums,ops);
                    }else {
                        break;
                    }
                }
                ops.push(s[i]);
            }
        }
        while(!ops.empty()&&ops.top() != '(') calc(nums,ops);
        return nums.top();
        
    }
    
    void calc(stack<int>& nums, stack<char>& ops) {
        char op = ops.top();
        ops.pop();
        int b = nums.top();
        nums.pop();
        int a = nums.top();
        nums.pop();
        int ans = 0;
        switch (op) {
            case '+':
                ans = a +b;
                break;
            case '-':
                ans = a-b;
                break;
            case'*':
                ans = a*b;
                break;
            default:
                break;
                
        }
        nums.push(ans);
    }
};