LeetCode 题解工作台
基本计算器 II
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 整数除法仅保留整数部分。 你可以假设给定的表达式总是有效的。所有中间结果将在 [-2 31 , 2 31 - 1] 的范围内。 注意： 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。 示例 1： 输入…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
遍历字符串 ，并用变量 `sign` 记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据 `sign` 来决定计算方式： - 加号：将数字压入栈；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "3+2*2" 输出：7
示例 2：
输入：s = " 3/2 " 输出：1
示例 3：
输入：s = " 3+5 / 2 " 输出：5
提示：
1 <= s.length <= 3 * 105s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开s表示一个 有效表达式- 表达式中的所有整数都是非负整数，且在范围
[0, 231 - 1]内 - 题目数据保证答案是一个 32-bit 整数
解题思路
方法一：栈
遍历字符串 ，并用变量 sign 记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据 sign 来决定计算方式：
- 加号：将数字压入栈；
- 减号：将数字的相反数压入栈；
- 乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。
遍历结束后，将栈中元素求和即为答案。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def calculate(self, s: str) -> int:
v, n = 0, len(s)
sign = '+'
stk = []
for i, c in enumerate(s):
if c.isdigit():
v = v * 10 + int(c)
if i == n - 1 or c in '+-*/':
match sign:
case '+':
stk.append(v)
case '-':
stk.append(-v)
case '*':
stk.append(stk.pop() * v)
case '/':
stk.append(int(stk.pop() / v))
sign = c
v = 0
return sum(stk)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | \mathcal{O}(n) |
| 空间 | \mathcal{O}(1) |
面试官常问的追问
外企场景- question_mark
Test the candidate's understanding of operator precedence and state management using a stack.
- question_mark
Evaluate how the candidate handles parsing and tokenizing the string efficiently.
- question_mark
Check how well the candidate handles edge cases such as division by zero or handling spaces.
常见陷阱
外企场景- error
Incorrect handling of operator precedence, especially when mixing addition, subtraction, multiplication, and division.
- error
Failing to update the stack correctly during multiplication and division.
- error
Not properly handling negative numbers or white spaces.
进阶变体
外企场景- arrow_right_alt
Modify the problem to include parentheses and evaluate the expression accordingly.
- arrow_right_alt
Handle floating point numbers instead of integers in the expression.
- arrow_right_alt
Add additional operators like modulo or exponentiation.