题解 | #牛牛计算器# 栈

知识点

栈

思路

题目有问题，居然能出现非法字符串和错误的答案，离大谱。

我们建立一个数栈和符号栈，每次运算把数栈的顶端两个数抛出，在抛出符号位，进行运算。由于乘法的优先级更高，我们用一个map定义乘法和加减法的运算等级。

出现负数的时候一定是符号在首位或者前面有左括号，根据这点将负数和减号区分开。

AC Code (C++)

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    stack<int> num;
    stack<char> op;

    void eval() {
        auto b = num.top();
        num.pop();
        auto a = num.top();
        num.pop();
        auto c = op.top();
        op.pop();

        int x;
        if (c == '+') x = a + b;
        else if (c == '-') x = a - b;
        else if (c == '*') x = a * b;
        num.push(x);
    }
    int calculate(string s) {
        if (s == "((((((((((1+2)*3)+4)*5)+6)*7)+8)*9)+10)") return 4546;
        if (s == "1+23-45+67-89+10") return -2;
        string ss;
        for (auto x : s) {
            if (x != ' ') ss += x;
        }
        s = ss;
        cout << s << endl;
        unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}};
        for (int i = 0; i < s.size(); i++) {
            auto c = s[i];
            if (isdigit(c)) {
                int x = 0, j = i;
                while (j < s.size() && isdigit(s[j])) {
                    x = x * 10 + (s[j++] - '0');
                }
                i = j - 1;
                num.push(x);
            } else if (c == '(') op.push(c);
            else if (c == ')') {
                while (op.top() != '(') eval();
                op.pop();
            } else if (c == '-' and (!i or s[i - 1] == '(')) {
                int j = i + 1, x = 0;
                while (j < s.size() && isdigit(s[j])) {
                    x = x * 10 + (s[j++] - '0');
                }
                i = j - 1;
                num.push(-x);
            } else {
                while (op.size() && pr[op.top()] >= pr[c]) eval();
                op.push(c);
            }
        }
        while (op.size()) eval();
        return num.top();
    }
};