第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0227. 基本计算器 II

题目地址(227. 基本计算器 II)

题目描述

1
实现一个基本的计算器来计算一个简单的字符串表达式的值。
2
3
字符串表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格 。 整数除法仅保留整数部分。
4
5
示例 1:
6
7
输入: "3+2*2"
8
输出: 7
9
示例 2:
10
11
输入: " 3/2 "
12
输出: 1
13
示例 3:
14
15
输入: " 3+5 / 2 "
16
输出: 5
17
说明:
18
19
你可以假设所给定的表达式都是有效的。
20
请不要使用内置的库函数 eval。
21
22
来源:力扣(LeetCode)
23
链接:https://leetcode-cn.com/problems/basic-calculator-ii
24
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Copied!

前置知识

公司

  • 暂无

一个栈

思路

计算器的题目基本都和栈有关,这道题也不例外。
由题目信息可知,s 中一共包含以下几种数据:
  • 空格
  • 数字
  • 操作符。这里有 + - * /
而对于操作符来说又可以进一步细分:
  • 一元操作符 + -
  • 二元操作符 * /
对于一元操作符来说,我们只需要知道一个操作数即可。这个操作数就是操作符右边的数字。为了达到这个效果,我们需要一点小小的 trick。
1
1 + 2
Copied!
我们可以在前面补充一个 + 号,变成:
1
+ 1 + 2
2
# 可看成
3
(+1)(+2)
Copied!
再比如:
1
(-1)(+2)(+3)(-4)
Copied!
括号只是逻辑分组,实际并不存在。下同,不再赘述。
而对于二元操作符来说,我们需要知道两个操作数,这两个操作数分别是操作符两侧的两个数字。
1
(5) / (2)
Copied!
再比如
1
(3) * (4)
Copied!
简单来说就是,一元操作符绑定一个操作数。而二元操作符绑定两个操作数。
算法:
  • 从左到右遍历 s
  • 如果是数字,则更新数字
  • 如果是空格,则跳过
  • 如果是运算符,则按照运算符规则计算,并将计算结果重新入栈,具体见代码。最后更新 pre_flag 即可。
为了简化判断, 我使用了两个哨兵。一个是 s 末尾的 $,另一个是最开始的 pre_flag。

关键点解析

  • 区分一目和二目运算符,并使用栈来简化操作
  • 记录 pre_flag,即上一次出现的操作符
  • 使用哨兵简化操作。一个是 s 的 $ ,另一个是 pre_flag 的 +

代码

代码支持:Python。
Python Code:
1
class Solution:
2
def calculate(self, s: str) -> int:
3
stack = []
4
s += '#x27;
5
pre_flag = '+'
6
num = 0
7
8
for c in s:
9
if c.isdigit():
10
num = num * 10 + int(c)
11
elif c == ' ': continue
12
else:
13
if pre_flag == '+':
14
stack.append(num)
15
elif pre_flag == '-':
16
stack.append(-num)
17
elif pre_flag == '*':
18
stack.append(stack.pop() * num)
19
elif pre_flag == '/':
20
stack.append(int(stack.pop() / num))
21
pre_flag = c
22
num = 0
23
return sum(stack)
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

两个栈

思路

使用两个栈适用范围更广, 能解决 + - * / ^ % ( ) 等表达式问题,是一种经典的做法。比如 1896. 反转表达式值的最少操作次数 就可以使用双栈来解决。
这里的两个栈分别用于存储操作数和非操作数,不妨:
  • 用 nums 存储操作数
  • 用 ops 存储非操作数
整体的思路也是类似的,我们一起来看下。

代码

代码支持:Python
Python Code:
1
class Solution:
2
def calculate(self, s: str) -> int:
3
s = '(' + s + ')'
4
n = len(s)
5
i = 0
6
stack_ops = [] # 存储字符串的栈
7
stack_nums = [] # 存储数字的栈
8
while i < n:
9
if s[i] in ' ':
10
i += 1
11
continue
12
elif '0' <= s[i] <= '9':
13
# 是数字
14
num = ''
15
while i < n and s[i].isdigit():
16
num += s[i]
17
i += 1
18
i -= 1
19
stack_nums.append(int(num))
20
if not stack_ops:
21
i += 1
22
continue
23
op = stack_ops.pop()
24
num = stack_nums.pop()
25
if op == "+":
26
num *= 1
27
elif op == "-":
28
num *= -1
29
elif op == "*":
30
num = stack_nums.pop() * num
31
elif op == "/":
32
if num ^ stack_nums[-1] > 0: num = stack_nums.pop() // num
33
else: num = (stack_nums.pop() + num - 1) // num
34
stack_nums.append(num)
35
else:
36
stack_ops.append(s[i])
37
i += 1
38
return sum(stack_nums)
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

扩展

  1. 1.
    基本计算器 和这道题差不多,官方难度困难。就是多了个括号而已。所以基本上可以看做是这道题的扩展。题目描述:
1
实现一个基本的计算器来计算一个简单的字符串表达式的值。
2
3
字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格 。
4
5
示例 1:
6
7
输入: "1 + 1"
8
输出: 2
9
示例 2:
10
11
输入: " 2-1 + 2 "
12
输出: 3
13
示例 3:
14
15
输入: "(1+(4+5+2)-3)+(6+8)"
16
输出: 23
17
说明:
18
19
你可以假设所给定的表达式都是有效的。
20
请不要使用内置的库函数 eval。
Copied!
拿题目中最难的例子来说 "(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 代码:
1
class Solution:
2
def calculate(self, s: str) -> int:
3
def dfs(s, start):
4
stack = []
5
pre_flag = '+'
6
num = 0
7
i = start
8
while i < len(s):
9
c = s[i]
10
if c == ' ':
11
i += 1
12
continue
13
elif c == '(':
14
i, num = dfs(s, i+1)
15
elif c.isdigit():
16
num = num * 10 + int(c)
17
else:
18
if pre_flag == '+':
19
stack.append(num)
20
elif pre_flag == '-':
21
stack.append(-num)
22
if c == ')': break
23
pre_flag = c
24
num = 0
25
i += 1
26
return i, sum(stack)
27
s += '#x27;
28
return dfs(s, 0)[1]
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$
补充:一些同学反映:思路和我的一样,代码也类似,为什么执行不正确?这里我强调一点:
  • 注意语句 if c == ')': break 的位置。如果放在其他位置,需要在其前手动增加语句,代码类似:
1
if c == ')':
2
if pre_flag == '+':
3
stack.append(num)
4
elif pre_flag == '-':
5
stack.append(-num)
6
break
Copied!
以 "(1+(4+5+2)-3)+(6+8)" 来说,(4+5+2) 加起来就是 11,如果 break 前不执行上面的语句就会漏掉 2 变成 了 9,而不是 11。
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 38K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。