题解 | 表达式求值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    stack<int> nums;
    stack<char> ops;
    // 辅助函数：计算栈顶的两个数
    void eval() {
        if(nums.size() < 2 || ops.empty()) return;
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char c = ops.top(); ops.pop();
        
        int res = 0;
        if (c == '+') res = a + b;
        else if (c == '-') res = a - b;
        else if (c == '*') res = a * b;
        nums.push(res);
    }

    // 定义优先级
    int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*') return 2;
        return 0;
    }

    int solve(string s) {
        // 清空栈（如果类被复用）
        while(!nums.empty()) nums.pop();
        while(!ops.empty()) ops.pop();

        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            // 1. 处理数字
            if (isdigit(c)) {
                int num = 0;
                // 向后读取直到非数字
                while (i < s.size() && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                nums.push(num);
                i--; // 因为for循环还会i++，这里需要回退一格
            }
            // 2. 处理左括号
            else if (c == '(') {
                ops.push(c);
            }
            // 3. 处理右括号
            else if (c == ')') {
                // 计算直到遇到左括号
                while (!ops.empty() && ops.top() != '(') {
                    eval();
                }
                if(!ops.empty()) ops.pop(); // 弹出 '('
            }
            // 4. 处理运算符 (+ - *)
            else {
                // 核心逻辑：当 栈顶优先级 >= 当前优先级，先计算栈顶
                // 例如：栈里是 *，当前是 +，必须先算 *
                while (!ops.empty() && ops.top() != '(' && precedence(ops.top()) >= precedence(c)) {
                    eval();
                }
                ops.push(c);
            }
        }

        // 5. 处理剩余的运算符
        while (!ops.empty()) {
            eval();
        }

        return  nums.top();
    }
};