本文目录
1 中文题目
给定一个字符串表达式 s ，请实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
可以假设给定的表达式总是有效的。所有中间结果将在 [ − 2 31 , 2 31 − 1 ] [-2^{31}, 2^{31} - 1] [−231,231−1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例：
输入：s = "3+2*2"
输出：7
输入：s = " 3/2 "
输出：1
输入：s = " 3+5 / 2 "
输出：5
提示：
- 1 ≤ s . l e n g t h ≤ 3 ∗ 1 0 5 1 \leq s.length \leq 3 * 10^5 1≤s.length≤3∗105
s由整数和算符 (‘+’, ‘-’, ‘*’, ‘/’) 组成，中间由一些空格隔开s表示一个 有效表达式- 表达式中的所有整数都是非负整数，且在范围 [ 0 , 2 31 − 1 ] [0, 2^{31} - 1] [0,231−1] 内
- 题目数据保证答案是一个
32-bit整数
2 Python求解
2.1 求解思路
通过一个栈保存中间结果，处理四种运算符的优先级问题。对于加减法操作，将当前数字直接（或取相反数）压入栈；对于乘除法操作，弹出栈顶元素与当前数字计算后再压入栈。这样的处理方式确保了乘除法优先于加减法。最后，将栈中所有元素相加得到最终结果。
2.2 涉及方法
- 栈（Stack）：用栈存储中间结果，解决加减法和乘除法的优先级问题。
- 模拟运算解析：通过一次遍历逐步解析字符串中的数字和操作符，动态计算中间结果。
- 整数除法向零取整：使用 Python 的 int() 强制截断实现对负数的向零取整（如 -3 / 2 = -1 而不是 -2）。
2.3 求解示例
输入：s = "3+2*2"
初始化：
stack = [], num = 0, sign = '+'
遍历字符 s[0] = '3'：
是数字，num = 3.
遍历字符 s[1] = '+'：
是操作符，根据当前的 sign = '+'，将 num = 3 压入栈：
stack = [3]
更新 sign = '+', 重置 num = 0.
遍历字符 s[2] = '2'：
是数字，num = 2.
遍历字符 s[3] = '*'：
是操作符，根据当前的 sign = '+'，将 num = 2 压入栈：
stack = [3, 2]
更新 sign = '*', 重置 num = 0.
遍历字符 s[4] = '2'：
是数字，num = 2.
遍历结束（i = len(s) - 1）：
根据当前的 sign = '*'，弹出栈顶 2，与 num = 2 相乘后压入栈：
stack = [3, 4]
计算结果：
栈中所有元素求和：3 + 4 = 7.
2.4 Python代码
class Solution:
def calculate(self, s: str) -> int:
"""
计算一个只包含非负整数、加法、减法、乘法和除法的字符串表达式的值。
:param s: 包含数字、'+', '-', '*', '/', 和空格的字符串
:return: 表达式的计算结果
"""
# 初始化栈，用于存储操作数
stack = []
# 当前数字
num = 0
# 当前操作符，初始为加号
sign = '+'
# 遍历字符串
for i, char in enumerate(s):
if char.isdigit():
# 如果当前字符是数字，逐位更新当前数字
num = num * 10 + int(char)
# 如果遇到操作符，或者是最后一个字符，处理前面的数字
if char in "+-*/" or i == len(s) - 1:
if sign == '+':
# 加号操作，将当前数字压入栈
stack.append(num)
elif sign == '-':
# 减号操作，将当前数字的相反数压入栈
stack.append(-num)
elif sign == '*':
# 乘法操作，将栈顶元素与当前数字相乘，并更新栈顶
stack.append(stack.pop() * num)
elif sign == '/':
# 除法操作，将栈顶元素与当前数字相除，并更新栈顶
# 注意：Python 中负数除法向零取整需要使用 int() 强制截断
stack.append(int(stack.pop() / num))
# 更新操作符为当前字符，重置当前数字
sign = char
num = 0
# 栈中所有元素求和即为最终结果
return sum(stack)
2.5 复杂度分析
- 时间复杂度：
该算法的时间复杂度为 O(n)，其中 n 是字符串的长度。每个字符只被遍历一次，且栈的操作（入栈、出栈）均为 O(1)。 - 空间复杂度：
该算法的空间复杂度为 O(n)，在最坏情况下（如所有运算符都是加减法）需要将所有数字压入栈，栈的空间需求与输入字符串的长度成正比。
3 题目总结
题目难度：中等
数据类型：字符串
数据结构：栈
应用算法：栈的特性