题解 | 表达式求值

class Solution {
  public:
    int solve(string s) {
        int n = s.size();
        stack<int> a;
        stack<char> b;

        for (int i = 0; i < n; i++) {
            if (isdigit(s[i])) {
                int c = 0;
                while (i < n && isdigit(s[i])) {
                    c = c * 10 + (s[i] - '0');
                    i++;
                }
                i--;
                a.push(c);
            } else {
                if (b.empty()) {
                    b.push(s[i]);
                } else {
                    if (s[i] == '+' || s[i] == '-') {
                        if (b.top() == '+') {
                            int d = a.top();
                            a.pop();
                            int e = a.top();
                            a.pop();
                            b.pop();
                            a.push(e + d);
                            b.push(s[i]);
                        } else if (b.top() == '-') {
                            int d = a.top();
                            a.pop();
                            int e = a.top();
                            a.pop();
                            b.pop();
                            a.push(e - d);
                            b.push(s[i]);
                        } else if (b.top() == '*') {
                            int d = a.top();
                            a.pop();
                            int e = a.top();
                            a.pop();
                            b.pop();
                            a.push(e * d);
                            b.push(s[i]);
                        } else if (b.top() == '(') {
                            b.push(s[i]);
                        }
                    }

                    if (s[i] == '*') {
                        if (!b.empty() && b.top() == '*') {
                            int d = a.top();
                            a.pop();
                            int e = a.top();
                            a.pop();
                            b.pop();
                            a.push(e * d);
                            b.push(s[i]);
                        } else {
                            b.push(s[i]);
                        }
                    }

                    if (s[i] == '(') {
                        b.push(s[i]);
                    }

                    if (s[i] == ')') {
                        // 关键修改：循环计算直到遇到 '('
                        while (!b.empty() && b.top() != '(') {
                            char op = b.top();
                            b.pop();
                            int d = a.top();
                            a.pop();
                            int e = a.top();
                            a.pop();

                            if (op == '+') a.push(e + d);
                            else if (op == '-') a.push(e - d);
                            else if (op == '*') a.push(e * d);
                        }
                        // 弹出 '('
                        if (!b.empty() && b.top() == '(') {
                            b.pop();
                        }
                    }
                }
            }
        }

        // 计算剩余运算符
        while (!b.empty()) {
            char op = b.top();
            b.pop();
            int d = a.top();
            a.pop();
            int e = a.top();
            a.pop();

            if (op == '+') a.push(e + d);
            else if (op == '-') a.push(e - d);
            else if (op == '*') a.push(e * d);
        }

        return a.top();
    }
};