# \[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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/zhan/224-ji-ben-ji-suan-qi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.