> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/zhan/224-ji-ben-ji-suan-qi.md).

# \[224]\[困难]\[栈] 基本计算器

## 题目描述

[224. 基本计算器](https://leetcode-cn.com/problems/basic-calculator/)

给你一个字符串表达式 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 表示一个有效的表达式

## 解题思路

只有加减号的运算, 不需要考虑运算符的优先级, 只需要从左到右逐个计算就可以.

在遇到括号时, 需要优先计算括号中的表达式, 因此需要将前面计算的结果和符号缓存起来, 计算得到括号内子表达式的值之后, 再与之前结果和符号计算得到新结果.

由于括号是可以嵌套的, 应对这种情况需要使用递归的方式处理, 因此使用栈的方式缓存之前计算的结果和符号.

计算器题目的一个关键点是在何时触发计算. 计算都是在将一个完整的数字获取到之后, 才能与之前和数字和计算符号一起计算. 因此问题就转变成了如何判断数字结束. 本题中有以下几种情况:

* 遇到了`+`, `-`计算符
* 遇到右括号`)`
* 遇到字符串结束

遇到这些情况就要发生计算, 并维护好计算后的重置. 遇到其他符号无需计算, 只需要更新当前数字, 或者压栈.

首先设定:

* res: 表示左边表达式除去栈内保存元素的计算结果
* pre\_sign: 表示当前数字之前的运算符
* num 表示当前遇到的数字
* 用栈保存遇到左括号时前面计算好了的结果和运算符

过程为:

* 如果当前是数字，那么更新计算当前数字
* 如果当前是操作符+或者-，那么需要更新计算当前计算的结果 res，并把当前数字 num 设为 0，pre\_sign 设为正负，重新开始
* 如果当前是 `(` ，那么说明遇到了右边的表达式，而后面的小括号里的内容需要优先计算，所以要把 res, pre\_sign 进栈，更新 res 和 pre\_sign 为新的开始
* 如果当前是 `)` ，那么说明右边的表达式结束，即当前括号里的内容已经计算完毕，所以要把之前的结果出栈，然后计算整个式子的结果
* 最后，当所有数字结束的时候，需要把最后的一个 num 也更新到 res 中

```python
class Solution:
    def calculate(self, s: str) -> int:
        res = 0
        num, pre_sign = 0, 1
        stack = []

        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c in ('+', '-'):
                res += pre_sign * num
                num, pre_sign = 0, 1 if c == '+' else -1
            elif c == '(':
                stack.append(res)
                stack.append(pre_sign)
                res, pre_sign = 0, 1
            elif c == ')':
                res += pre_sign * num
                res *= stack.pop()
                res += stack.pop()
                num = 0
        res += pre_sign * num
        return res
```

## 参考资料

* [如何想到用「栈」？思路来自于递归](https://leetcode-cn.com/problems/basic-calculator/solution/ru-he-xiang-dao-yong-zhan-si-lu-lai-zi-y-gpca/)