题解 | 表达式求值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
     void calc(stack<int>& nums, stack<char>& ops){
        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);
    }//运算函数

    int priority(char op){
        if(op == '*') return 2;
        else if(op == '+' || op == '-') return 1;
        else return 0;
    }//定义优先级
    
    int solve(string s) {
        stack<int> nums;
        stack<char> ops;
        int n = s.length();
        stack<int> stk;
        for(int i = 0; i < n; i++){
            if(s[i] >= '0' && s[i] <= '9'){	//遇到数字时：完整读取后入栈
                int num = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9'){
                    num = num * 10 + (s[i] - '0');
                    i++;	//完整读取
                }
                i--;	//最后一次while循环时i仍会+1，故-1回到正确值
                nums.push(num);	//入栈
            }
            else if(s[i] == '('){
                ops.push(s[i]);
            }	//读入左括号直接入栈
            else if(s[i] == ')'){
                while(ops.top() != '('){
                    calc(nums, ops);
                }
                ops.pop();
            }	//读取右括号一直运算直到遇到左括号，然后删除左括号
            else{
                while(!ops.empty() && priority(ops.top()) >= priority(s[i])){
                    calc(nums, ops);
                }
                ops.push(s[i]);
            }	//遇到运算符时，先计算优先级高的，最后剩下同级的优先级
        }

        while(!ops.empty()){
            calc(nums, ops);
        }	//统计优先级可直接计算
        return nums.top();
    }
};

核心思路是在遍历字符串时，对不同情况做不同处理：

1. 遇到数字：完整读取（可能有很多位），压入数字栈
2. (:直接压入符号栈
3. ):不断计算，直到遇到(
4. +、-、*:当符号栈顶的符号优先级更大时，则应先计算掉符号的栈顶，然后再压入当前运算符