224. 基本计算器

224. 基本计算器

题目

实现一个基本的计算器来计算一个简单的字符串表达式 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. 数字可能>10
2. 会出现负数

接下来就是纯粹用栈来模拟 ```python class Solution: def calculate(self, s: str) -> int: s = s.replace(‘ ‘, ‘’) L = [] idx = -1 n = len(s) move = True while idx < n-1 or move == False: if move == True: idx += 1 i = s[idx] move = False

        # print("{:^3s}".format(str(i)), L)
        if (type(i) == int) or ('0' <= i <= '9'):
            i = int(i)
            if L != [] and type(L[-1]) == int:
                i = L.pop()*10+i
            elif L == [] or L[-1] == '(' or (idx+1 < n and ('0' <= s[idx+1] <= '9')):
                L.append(i)
                move = True
            elif L.pop() == '+':
                i = L.pop()+i
            else:
                i = L.pop()-i
        elif i == ')':
            i = L.pop()
            L.pop()
        elif i == '-' and (L == [] or L[-1] == '('):
            L.append(0)
        else:
            L.append(i)
            move = True
    return L[0]

对于 `1-(-11+3)-8` 的运算过程如下：
```python
>>> x = Solution()
>>> s = "1-(-11+3)-8"
>>> x.calculate(s)

 1  []
 -  [1]
 (  [1, '-']
 -  [1, '-', '(']
 -  [1, '-', '(', 0]
 1  [1, '-', '(', 0, '-']
 1  [1, '-', '(', 0, '-', 1]
11  [1, '-', '(', 0, '-']
-11 [1, '-', '(']
 +  [1, '-', '(', -11]
 3  [1, '-', '(', -11, '+']
-8  [1, '-', '(']
 )  [1, '-', '(', -8]
-8  [1, '-']
 9  []
 -  [9]
 8  [9, '-']
 1  []
1

最后虽然通过了，但结果是惨烈的。。。

其他解法

官方解

官方的思路是先将括号展开，用opt储存每个括号前的正负性。
将1+2+(3-(4+5)) 转化为 1+2+3+[-4]+[-5]，然后进行计算。

int calculate(char* s) {
    int n = strlen(s);
    int ops[n], top = 0;
    int sign = 1;
    ops[top++] = sign;

    int ret = 0;
    int i = 0;
    while (i < n) {
        if (s[i] == ' ') {
            i++;
        } else if (s[i] == '+') {
            sign = ops[top - 1];
            i++;
        } else if (s[i] == '-') {
            sign = -ops[top - 1];
            i++;
        } else if (s[i] == '(') {
            ops[top++] = sign;
            i++;
        } else if (s[i] == ')') {
            top--;
            i++;
        } else {
            long num = 0;
            while (i < n && s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + s[i] - '0';
                i++;
            }
            ret += sign * num;
        }
    }
    return ret;
}

解法2

我看到这个解法——如何想到用「栈」？思路来自于递归，更觉惊艳。

class Solution(object):
    def calculate(self, s):
        res, num, sign = 0, 0, 1
        stack = []
        for c in s:
            if c.isdigit():
                num = 10 * num + int(c)
            elif c == "+" or c == "-":
                res += sign * num
                num = 0
                sign = 1 if c == "+" else -1
            elif c == "(":
                stack.append(res)
                stack.append(sign)
                res = 0
                sign = 1
            elif c == ")":
                res += sign * num
                num = 0
                res *= stack.pop()
                res += stack.pop()
        res += sign * num
        return res