题解 | #表达式求值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    stack<int>num;
    stack<char> ops;
    map<char, int> p;
    void cal(int a, int b, char op) {
        if (op == '+') num.push(b + a);
        if (op == '-') num.push(b - a);
        if (op == '*') num.push(b * a);
    }
    int solve(string s) {
        // write code here
        p['+'] = 1;
        p['-'] = 1;
        p['*'] = 2;
        for (int i = 0; i < s.length();) {
            if (s[i] == '(') {
                ops.push(s[i]);
                i++;
            }
            else if (isdigit(s[i])) {
                bool f = 1;//默认正
                if (i == 1 && s[i - 1] == '-') f = -1;//负
                string t = "";
                while (isdigit(s[i])) {
                    t += s[i];
                    i++;
                }
                num.push(f * stoi(t));
            }
            else if (s[i] == '+' || s[i] == '-' || s[i] == '*') {
                if (ops.empty() || p[ops.top()] < p[s[i]]) {
                    ops.push(s[i]);
                }
                else {
                    while (!ops.empty() && ops.top()!='('&& p[ops.top()] >= p[s[i]]) {
                        int op = ops.top();
                        ops.pop();
                        int n1 = num.top();
                        num.pop();
                        int n2 = num.top();
                        num.pop();
                        cal(n1, n2, op);
                    }
                    ops.push(s[i]);
                }
                i++;
            }
            else if (s[i] == ')') {
                while (!ops.empty() && ops.top() != '(') {
                    int op = ops.top();
                    ops.pop();
                    int n1 = num.top();
                    num.pop();
                    int n2 = num.top();
                    num.pop();
                    cal(n1, n2, op);
                }
                ops.pop();
                i++;
            }

        }
        while (!ops.empty()) {
            int op = ops.top();
            ops.pop();
            int n1 = num.top();
            num.pop();
            int n2 = num.top();
            num.pop();
            cal(n1, n2, op);
        }
        return num.top();
    }
};