难度: Medium
给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2" 输出: 7
示例 2:
输入: " 3/2 " 输出: 1
示例 3:
输入: " 3+5 / 2 " 输出: 5
说明：
- 你可以假设所给定的表达式都是有效的。
- 请不要使用内置的库函数
eval。
Submission
运行时间: 54 ms
内存: 17.9 MB
class Solution:
def calculate(self, s: str) -> int:
numStack = []
num = 0
sign = '+'
for i, c in enumerate(s):
if c.isdigit():
num = num * 10 + int(c)
if c in "+-*/" or i == len(s) - 1:
if sign == '+':
numStack.append(num)
elif sign == '-':
numStack.append(-num)
elif sign == '*':
numStack[-1] *= num
elif sign == '/':
numStack[-1] = int(numStack[-1] / num)
num = 0
sign = c
return sum(numStack)
Explain
此题解采用了一个栈来处理没有括号的四则运算表达式。每次遇到运算符或者字符串的末尾时，根据前一个运算符来决定如何处理当前累积的数字。如果是加号或减号，将数字直接压入栈（减号则压入其负值）。对于乘号或除号，先从栈中弹出顶部数字，执行乘法或除法操作，然后将结果再压回栈中。最后，将栈中所有数字求和得到最终结果。这种方法有效地利用栈来处理运算符的优先级，避免了使用递归或额外的数据结构。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def calculate(self, s: str) -> int:
numStack = [] # 栈用来保存中间计算结果
num = 0 # 当前解析的数字
sign = '+' # 当前数字前的操作符，默认为加号
for i, c in enumerate(s): # 遍历字符串
if c.isdigit():
num = num * 10 + int(c) # 组合数字
if c in '+-*/' or i == len(s) - 1: # 遇到运算符或字符串末尾
if sign == '+':
numStack.append(num) # 加号：压入数字
elif sign == '-':
numStack.append(-num) # 减号：压入负数
elif sign == '*':
numStack[-1] *= num # 乘号：栈顶数字乘以当前数字
elif sign == '/':
numStack[-1] = int(numStack[-1] / num) # 除号：栈顶数字除以当前数字
num = 0 # 重置数字
sign = c # 更新操作符
return sum(numStack) # 返回栈中所有数的和
Explore
在表达式处理过程中，数字可能由多个字符组成，所以需要一直读取字符直到遇到非数字字符（即运算符）或字符串结束，才能确定整个数字的值。此时，已经可以知道前一个运算符和当前完整的数字，便可以根据前一个运算符来正确处理这个数字（如直接压栈或与栈顶元素进行运算）。这种处理方式确保了在读取到运算符之前，数字的累积是完整且正确的。
在这个算法中，每次遇到乘除运算符时，从栈中弹出一个数字进行操作是因为乘法和除法具有左结合性，即它们会先与前一个数字（即栈顶元素）结合进行计算。这样处理可以立即解决当前运算符与前一个数字的运算问题，而不需要额外的逻辑来处理连续的乘除运算。连续的乘除操作会在遍历到各自的运算符时依次处理，因为每次处理都会将结果压回栈中，为下一个乘除运算做好准备。
在Python中，整数除法`/`会得到浮点结果，而使用`int()`函数可以将浮点数向下取整到最接近的整数。特别是在涉及负数的除法时，Python的`int()`函数会将结果向零方向取整，这与一些其他语言中的行为不同。因此，在实现中，使用`int()`确保了即使在负数除法的情况下也能正确地向下取整。例如，`int(-3 / 2)`会得到`-1`，符合预期的结果。