题解 | 表达式求值

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        stack<char> op;
        stack<int> n;
        map<char, int> h{ {'(', 3}, {'+', 1}, {'-', 1}, {'*', 2}, {')', 0}};

        for (int i = 0; i < s.length(); ) {
            if (isdigit(s[i])) {
                int num = 0;
                while (i < s.length() && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                n.push(num);
            } else {
                while (!op.empty() && h[op.top()] >= h[s[i]] && op.top()!= '(') {
                    int num1 = n.top();
                    n.pop();
                    int num2 = n.top();
                    n.pop();
                    char oper = op.top();
                    op.pop();
                    if (oper == '+') n.push(num2 + num1);
                    else if (oper == '-') n.push(num2 - num1);
                    else if (oper == '*') n.push(num2 * num1);
                }
                if (s[i] == ')'&&op.top()=='('&&!op.empty()) {
                    op.pop(); // 弹出 '('
                } else {
                    op.push(s[i]);
                }
                i++;
            }
        }

        // 处理剩余操作符
        while (!op.empty()) {
            int num1 = n.top();
            n.pop();
            int num2 = n.top();
            n.pop();
            char oper = op.top();
            op.pop();

            if (oper == '+') n.push(num2 + num1);
            else if (oper == '-') n.push(num2 - num1);
            else if (oper == '*') n.push(num2 * num1);
        }
        return n.top();
    }
};