难度: Hard
Submission
运行时间: 26 ms
内存: 16.0 MB
class Solution:
def calculate(self, s: str) -> int:
num, op, stack = 0, "+", []
def helper(op, num):
if op == "+":
stack.append(num)
elif op == "-":
stack.append(-num)
elif op == "*":
stack.append(stack.pop() * num)
elif op == "/":
stack.append(int(stack.pop() / num))
for e in s:
if e.isdigit():
num = num * 10 + int(e)
elif e == "(":
stack.append(op)
num = 0
op = "+"
elif e in "+-*/)":
helper(op, num)
if e == ")":
num = 0
while isinstance(stack[-1], int):
num += stack.pop()
op = stack.pop()
helper(op, num)
num = 0
op = e
helper(op, num)
return sum(stack)
Explain
该题解使用栈来模拟计算过程。从左到右遍历字符串，遇到数字时更新当前数字，遇到左括号时将当前的运算符入栈并重置当前数字和运算符，遇到运算符时根据之前的运算符进行相应的计算并更新当前运算符，遇到右括号时计算括号内的结果并将结果作为数字进行进一步计算。最后将栈中所有数字求和得到最终结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def calculate(self, s: str) -> int:
num, op, stack = 0, "+", []
def helper(op, num):
if op == "+":
stack.append(num)
elif op == "-":
stack.append(-num)
elif op == "*":
stack.append(stack.pop() * num)
elif op == "/":
stack.append(int(stack.pop() / num))
for e in s:
if e.isdigit():
num = num * 10 + int(e) # 更新当前数字
elif e == "(":
stack.append(op) # 将当前运算符入栈
num = 0 # 重置当前数字
op = "+" # 重置当前运算符
elif e in "+-*/)":
helper(op, num) # 根据之前运算符进行相应计算
if e == ")":
num = 0
while isinstance(stack[-1], int):
num += stack.pop() # 计算括号内结果
op = stack.pop() # 弹出左括号前的运算符
helper(op, num) # 将括号内结果作为数字进一步计算
num = 0 # 重置当前数字
op = e # 更新当前运算符
helper(op, num) # 计算最后一个数字
return sum(stack) # 栈中所有数字求和得到最终结果
Explore
在算法中，遇到左括号`(`时将当前运算符入栈并重置数字和运算符的目的是为了处理嵌套的表达式。当解析器遇到左括号时，意味着将开始一个新的表达式的解析，这个新的表达式在逻辑上是独立的，并且其结果将作为整个包含它的更大表达式的一部分。通过入栈当前运算符，我们可以在遇到对应的右括号时，恢复之前的计算环境，确保括号内的表达式计算完成后能够正确地与外部表达式整合。
处理完括号内的表达式后，需要将括号前的运算符从栈中弹出并用这个运算符继续计算，因为这个运算符表示了括号表达式与其前一个数字或表达式之间的关系。括号内的表达式被视为一个整体（一个数值），一旦计算得到这个值，就需要使用它与之前的值根据保存的运算符进行合并计算。这样做可以确保表达式的运算顺序和数学逻辑的正确性。
在实现除法时，使用`int(stack.pop() / num)`而不是直接`stack.pop() / num`是为了确保结果是整数。在许多编程语言中，整数除法的结果需要是整数类型。由于题目或环境可能要求或假定整数运算，使用`int()`可以确保不论输入的正负，结果都符合整数的预期（例如，Python中的整数除法会向下取整）。这样处理可以防止结果中出现浮点数，从而满足特定的题目要求或实现细节。
该题解在处理运算符时有部分考虑运算符的优先级，主要通过立即计算乘法和除法来实现，而加法和减法则通过将数字推入栈中延后处理。这种实现方式在处理没有括号的基本表达式时能够正确处理运算符优先级。然而，这种方法可能在更复杂的情况下遇到问题，尤其是当多个不同优先级的运算符在没有明确括号的情况下连续出现时，这种实现可能会导致运算顺序错误，从而影响最终结果的正确性。