题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

样例1

输入: s = "1 + 1"
输出: 2

样例2

输入: s = " 2-1 + 2 "
输出: 3

样例3

输入: s = "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式
• '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
• '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

算法1

(栈模拟) $O(n)$

同样是利用栈，由于运算符在两个操作数中间，我们可以在遇到一个运算符时计算上一个运算符，并且我们把减号看成是数字前面的符号，即 $1-2 = +(1) +(-2)$。我们用两个变量res和sign来分别记录到目前为止表达式计算的结果和上一个遇到的运算符，当我们遇到一个左括号时，相当于遇到了一个新的表达式，我们需要将这两个变量压入栈中，并重新给这两个变量赋初值，这类似于函数递归调用的思路，在递归前先保存本地变量，递归返回后再恢复现场。而当我们遇到右括号时说明子表达式已经结束，我们需要将该子表达式计算得到结果累加到遇到该子表达式之前的结果res。

C++ 代码

class Solution {
public:
    int calculate(string s) {
        int sign = 1, res = 0;
        int num = 0;
        stack<int> stk;

        for (int i = 0; i < s.size(); i ++ ) {
            if (isspace(s[i])) continue;
            if (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            } else if (s[i] == '+' || s[i] == '-') {
                res += sign * num;
                num = 0;
                sign = s[i] == '+' ? 1 : -1;
            } else if (s[i] == '(') {
                stk.push(res);
                stk.push(sign);
                sign = 1;
                res = 0;
            } else if (s[i] == ')') {
                res += sign * num;
                res *= stk.top();
                stk.pop();
                res += stk.top();
                stk.pop();

                num = 0;
            }
        }
        return res + sign * num;
    }
};

算法2

(栈模拟) $O(n)$

这里可以直接用 AcWing 3302. 表达式求值 的模板。由于输入中不存在两个连续的操作符，则负号只有可能出现在表达式开头或者左括号后，所以对于负号 - 作为一元运算符的情况我们可以特判成 0 - [表达式]的形式。

并且因为输入中可能含有空格符号，我们需要先将输入中的空格符号全部去掉来让空格不能影响 “负号出现在表达式开头或者左括号后” 的判断。

C++ 代码

class Solution {
public:
    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;

        num.push(x);
    }

    int calculate(string str) {
        unordered_map<char, int> pr{{'(', 0}, {'+', 1}, {'-', 1}};

        string s;
        // 去掉空格
        for (int i = 0; i < str.size(); i++) {
            if (str[i] != ' ') {
                s += str[i];
            }
        }
        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 == '-' && (!i || s[i - 1] == '(')) {
                    num.push(0);
                }
                while (op.size() && pr[op.top()] >= pr[c]) eval();
                op.push(c);
            }
        }
        while (op.size()) eval();
        return num.top();
    }
};