# 0227. 基本计算器 II
### 题目地址(227. 基本计算器 II)
### 题目描述
```
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```
### 前置知识
* 栈
### 公司
* 暂无
### 一个栈
#### 思路
计算器的题目基本都和栈有关，这道题也不例外。
由题目信息可知，s 中一共包含以下几种数据：
* 空格
* 数字
* 操作符。这里有 + - \* /
而对于操作符来说又可以进一步细分：
* 一元操作符 + -
* 二元操作符 \* /
对于一元操作符来说，我们只需要知道一个操作数即可。这个操作数就是操作符右边的数字。为了达到这个效果，我们需要一点小小的 trick。
```py
1 + 2
```
我们可以在前面补充一个 + 号，变成：
```py
+ 1 + 2
# 可看成
(+1)(+2)
```
再比如:
```py
(-1)(+2)(+3)(-4)
```
> 括号只是逻辑分组，实际并不存在。下同，不再赘述。
而对于二元操作符来说，我们需要知道两个操作数，这两个操作数分别是操作符两侧的两个数字。
```py
(5) / (2)
```
再比如
```py
(3) * (4)
```
简单来说就是，一元操作符绑定一个操作数。而二元操作符绑定两个操作数。
算法：
* 从左到右遍历 s
* 如果是数字，则更新数字
* 如果是空格，则跳过
* 如果是运算符，则按照运算符规则计算，并将计算结果重新入栈，具体见代码。最后更新 pre\_flag 即可。
为了简化判断， 我使用了两个哨兵。一个是 s 末尾的 $，另一个是最开始的 pre\_flag。
#### 关键点解析
* 区分一目和二目运算符，并使用栈来简化操作
* 记录 pre\_flag，即上一次出现的操作符
* 使用哨兵简化操作。一个是 s 的 $ ，另一个是 pre\_flag 的 +
#### 代码
代码支持：Python。
Python Code：
```py
class Solution:
def calculate(self, s: str) -> int:
stack = []
s += '$'
pre_flag = '+'
num = 0
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c == ' ': continue
else:
if pre_flag == '+':
stack.append(num)
elif pre_flag == '-':
stack.append(-num)
elif pre_flag == '*':
stack.append(stack.pop() * num)
elif pre_flag == '/':
stack.append(int(stack.pop() / num))
pre_flag = c
num = 0
return sum(stack)
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$
### 两个栈
#### 思路
使用两个栈适用范围更广， 能解决 + - \* / ^ % ( ) 等表达式问题，是一种经典的做法。比如 [1896. 反转表达式值的最少操作次数](https://leetcode-cn.com/problems/minimum-cost-to-change-the-final-value-of-expression/) 就可以使用双栈来解决。
这里的两个栈分别用于存储操作数和非操作数，不妨：
* 用 nums 存储操作数
* 用 ops 存储非操作数
整体的思路也是类似的，我们一起来看下。
#### 代码
代码支持：Python
Python Code：
```py
class Solution:
def calculate(self, s: str) -> int:
s = '(' + s + ')'
n = len(s)
i = 0
stack_ops = [] # 存储字符串的栈
stack_nums = [] # 存储数字的栈
while i < n:
if s[i] in ' ':
i += 1
continue
elif '0' <= s[i] <= '9':
# 是数字
num = ''
while i < n and s[i].isdigit():
num += s[i]
i += 1
i -= 1
stack_nums.append(int(num))
if not stack_ops:
i += 1
continue
op = stack_ops.pop()
num = stack_nums.pop()
if op == "+":
num *= 1
elif op == "-":
num *= -1
elif op == "*":
num = stack_nums.pop() * num
elif op == "/":
if num ^ stack_nums[-1] > 0: num = stack_nums.pop() // num
else: num = (stack_nums.pop() + num - 1) // num
stack_nums.append(num)
else:
stack_ops.append(s[i])
i += 1
return sum(stack_nums)
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$
### 扩展
1. 基本计算器 和这道题差不多，官方难度困难。就是多了个括号而已。所以基本上可以看做是这道题的扩展。题目描述：
```
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。
示例 1:
输入: "1 + 1"
输出: 2
示例 2:
输入: " 2-1 + 2 "
输出: 3
示例 3:
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
```
拿题目中最难的例子来说 "(1+(4+5+2)-3)+(6+8)"。我们可以将其拆分为：
* 6+8 (= 14)
* 4 + 5 + 2 (=11)
* (11) - 3 (=8)
* 1 + (8) (=9)
* 9 + (14) (=23)
简单来说就是将括号里面的内容提取出来，提取出来就是上面的问题了。用上面的方法计算出结果，然后将结果作为一个数字替换原来的表达式。
比如我们先按照上面的算法计算出 6 + 8 的结果是 14，然后将 14 替换原来的 (6+8)，那么原问题就转化为了`(1+(4+5+2)-3)+14` 。这样一步一步就可以得到答案。
因此我们可以使用递归，每次遇到 `(` 则开启一轮新的递归，遇到 `)`则退出一层递归即可。
Python 代码：
```py
class Solution:
def calculate(self, s: str) -> int:
def dfs(s, start):
stack = []
pre_flag = '+'
num = 0
i = start
while i < len(s):
c = s[i]
if c == ' ':
i += 1
continue
elif c == '(':
i, num = dfs(s, i+1)
elif c.isdigit():
num = num * 10 + int(c)
else:
if pre_flag == '+':
stack.append(num)
elif pre_flag == '-':
stack.append(-num)
if c == ')': break
pre_flag = c
num = 0
i += 1
return i, sum(stack)
s += '$'
return dfs(s, 0)[1]
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$
补充：一些同学反映：思路和我的一样，代码也类似，为什么执行不正确？这里我强调一点：
* 注意语句 `if c == ')': break` 的位置。如果放在其他位置，需要在其前手动增加语句，代码类似：
```py
if c == ')':
if pre_flag == '+':
stack.append(num)
elif pre_flag == '-':
stack.append(-num)
break
```
以 "(1+(4+5+2)-3)+(6+8)" 来说，(4+5+2) 加起来就是 11，如果 break 前不执行上面的语句就会漏掉 2 变成 了 9，而不是 11。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 38K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/227.basic-calculator-ii.md?ask=
```
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.