经典栈问题

对于表达式求值这类问题，我们维护两个栈，一个栈存储数字，另外一个栈存储运算符。

原则：只要能算就算，即前面的运算能算就算

将运算符分为两类，一类是括号，另外一类是+-*/^

• 遇到数字，压栈
• 左括号，压栈
• 右括号，则将左括号之前的都要算完
• +-*/^等，定义每个运算符的优先级。
• 当前运算符的优先级 <= 栈顶优先级，则计算栈顶并压入，循环到 <为止
• 当前运算符的优先级 > 栈顶优先级，则直接入栈

时间复杂度O(N),空间复杂度O(N)

代码:

class Solution {
public:
    stack<int> nums;
    stack<char> op;

    void eval() {
        char c = op.top(); op.pop();
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        int res = 0;
        if (c == '+') res = a + b;
        else if (c == '-') res = a - b;
        else if (c == '*') res = a * b;
        else res = a / b;
        nums.push(res);
    }


    int calculate(string str) {
        string s;
        for (auto c : str)
            if (c != ' ')
                s += c;
        int n = s.size();
        unordered_map<char,int> mp = {
            {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2},{'(', 0}
        };
        for (int i = 0 ; i < n ; i ++) {
            if (s[i] == ' ') continue;
            if (s[i] >= '0' && s[i] <= '9') {//数字
                int j = i;
                while (j < n && s[j] != ' ' && s[j] >= '0' && s[j] <= '9') j ++;
                int num = stoi(s.substr(i, j - i));
                nums.push(num);
                i = j - 1;
            } else if (s[i] == '(') { //左括号
                op.push(s[i]);
            } else if (s[i] == ')') { //右括号
                while (op.top() != '(') eval();
                op.pop();
            } else { //其他
                if (!i || s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-') // 特殊处理符号和正号
                    nums.push(0);
                while (op.size() && mp[op.top()] >= mp[s[i]]) eval();
                op.push(s[i]);
            }
        }
        while (op.size()) eval();
        return nums.top();
    }
};