题解 | 表达式求值

#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

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

    int solve(string s) {
        string str;
        for (char c : s) {
            if (c != ' ') str += c;
        }
        int n = str.size();

        stack<long long> nums;
        stack<char> ops;
        nums.push(0);

        for (int i = 0; i < n; ++i) {
            char c = str[i];
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (!ops.empty() && ops.top() != '(') {
                    calc(nums, ops);
                }
                ops.pop();
            } else if (isdigit(c)) {
                long long num = 0;
                int j = i;
                while (j < n && isdigit(str[j])) {
                    num = num * 10 + (str[j] - '0');
                    j++;
                }
                nums.push(num);
                i = j - 1;
            } else {
                if (i > 0 && (str[i - 1] == '(' || str[i - 1] == '+' || str[i - 1] == '-')) {
                    nums.push(0);
                }
                while (!ops.empty() && ops.top() != '(') {
                    if (prio[ops.top()] >= prio[c]) {
                        calc(nums, ops);
                    } else {
                        break;
                    }
                }
                ops.push(c);
            }
        }

        while (!ops.empty()) {
            calc(nums, ops);
        }

        return (int)nums.top();
    }

  private:
    void calc(stack<long long>& nums, stack<char>& ops) {
        if (nums.size() < 2 || ops.empty()) return;

        long long b = nums.top();
        nums.pop();
        long long a = nums.top();
        nums.pop();
        char op = ops.top();
        ops.pop();

        long long res = 0;
        if (op == '+') res = a + b;
        else if (op == '-') res = a - b;
        else if (op == '*') res = a * b;

        nums.push(res);
    }
};