题目

227. 基本计算器 II

思路

• 此代码 224. 基本计算器 和 227. 基本计算器 II 通用。
  

代码

// 此代码 [24. 基本计算器] 和 [227. 基本计算器 II] 通用。
// 遇到 1. 数字:push；2. 左括号:push；3. 右括号:while循环计算到前一个'('并pop掉'('；
// 遇到 4. 运算符: while循环计算 直到op栈中没有元素 或 直到遇到'(', 再push当前运算符
class Solution {
public:
    stack<int> num;
    stack<char> op; // 符号： '(', '+', '-', '*', '/', 不存 ')'，因为遇到')'后会计算'('之间内容，不会压入op栈

    void eval() { // 能先计算，就先计算，栈顶op优先级 >= 当前op优先级，就进行计算
        int b = num.top(); num.pop(); 
        int a = num.top(); num.pop(); // 这里中间是分号
        char c = op.top(); op.pop();
        int r;
        if (c == '+') r = a + b;
        else if (c == '-') r = a - b;
        else if (c == '*') r = a * b;
        else r = a / b;
        num.push(r);
    }

    int calculate(string s) {
        unordered_map<char, int> pr; // 定义 运算符 优先级
        pr['+'] = pr['-'] = 1, pr['*'] = pr['/'] = 2; // 数字越大，优先级越高
        for (int i = 0; i < s.size(); i ++ ) {
            auto c = s[i];
            if (c == ' ') continue;
            if (isdigit(c)) { // 1. 判断 是否是 数字，是则压入栈中 num.push(x)
                int x = 0, j = i;
                while (j < s.size() && isdigit(s[j])) x = x * 10 + (s[j ++ ] - '0'); // 加( )防止溢出
                num.push(x);
                i = j - 1; // 因为 for 每次循环结束时 会 i ++ 
            }
            else if (c == '(') op.push(c); // 2. 判断 是否 是 左括号，是则压入栈中 op.push(c)
            else if (c == ')') { // 3. 判断是否为右括号，是则while循环计算与之匹配的左括号之间的内容，最后op.pop()把左括号弹出来
                while (op.top() != '(') eval();
                op.pop();
            } else { // 4. 遇到 运算符，如果遇到负数，先num.push(0)，再while循环进行计算，最后把 当前 运算符压入栈中
                if (!i || s[i - 1] == '(') num.push(0); // 负数 两种情况：算式开头 或者 左括号 右侧 可能存在负数 
                // 如果 op中存在元素，且栈顶运算符优先级 >= 当前运算符，则 while循环计算到 遇到'(' 或 op栈为空 为止
                while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval(); // 栈顶优先级 >= 当前优先级
                op.push(c);
            }
        }
        while (op.size()) eval(); // 5. for遍历完后如果没计算完毕, 则 while到计算完，举例:1+1,for遍历完后 op栈中还存在元素
        return num.top();
    }
};