0227. 基本计算器 II
题目地址(227. 基本计算器 II)
https://leetcode-cn.com/problems/basic-calculator-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。
1 + 2我们可以在前面补充一个 + 号，变成：
+ 1 + 2# 可看成(+1)(+2)再比如:
(-1)(+2)(+3)(-4)括号只是逻辑分组，实际并不存在。下同，不再赘述。
而对于二元操作符来说，我们需要知道两个操作数，这两个操作数分别是操作符两侧的两个数字。
(5) / (2)再比如
(3) * (4)简单来说就是，一元操作符绑定一个操作数。而二元操作符绑定两个操作数。
算法：
从左到右遍历 s
如果是数字，则更新数字
如果是空格，则跳过
如果是运算符，则按照运算符规则计算，并将计算结果重新入栈，具体见代码。最后更新 pre_flag 即可。
为了简化判断， 我使用了两个哨兵。一个是 s 末尾的 $，另一个是最开始的 pre_flag。
关键点解析
区分一目和二目运算符，并使用栈来简化操作
记录 pre_flag，即上一次出现的操作符
使用哨兵简化操作。一个是 s 的 $ ，另一个是 pre_flag 的 +
代码
代码支持：Python。
Python Code：
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. 反转表达式值的最少操作次数 就可以使用双栈来解决。
这里的两个栈分别用于存储操作数和非操作数，不妨：
用 nums 存储操作数
用 ops 存储非操作数
整体的思路也是类似的，我们一起来看下。
代码
代码支持：Python
Python Code：
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"输出: 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 代码：
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的位置。如果放在其他位置，需要在其前手动增加语句，代码类似：
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 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 38K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最后更新于
这有帮助吗？