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)$
两个栈
思路
这里的两个栈分别用于存储操作数和非操作数，不妨：
用 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)
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
