LeetCode 题解工作台
基本计算器
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。 示例 1： 输入： s = "1 + 1" 输出： 2 示例 2： 输入： s = " 2-1 + 2 " 输出： 3 示例 3： 输入： s =…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
我们用一个栈 来保存当前的计算结果和操作符，用一个变量 保存当前的符号，变量 保存最终的计算结果。 接下来，我们遍历字符串 的每一个字符：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "1 + 1" 输出：2
示例 2：
输入：s = " 2-1 + 2 " 输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)" 输出：23
提示：
1 <= s.length <= 3 * 105s由数字、'+'、'-'、'('、')'、和' '组成s表示一个有效的表达式'+'不能用作一元运算(例如，"+1"和"+(2 + 3)"无效)'-'可以用作一元运算(即"-1"和"-(2 + 3)"是有效的)- 输入中不存在两个连续的操作符
- 每个数字和运行的计算将适合于一个有符号的 32位 整数
解题思路
方法一：栈
我们用一个栈 来保存当前的计算结果和操作符，用一个变量 保存当前的符号，变量 保存最终的计算结果。
接下来，我们遍历字符串 的每一个字符：
- 如果当前字符是数字，那么我们用一个循环将后面的连续数字都读进来，然后用当前的符号将其加或者减到 中。
- 如果当前字符是
'+'，我们修改变量 为正号。 - 如果当前字符是
'-'，我们修改变量 为负号。 - 如果当前字符是
'('，我们把当前的 和 入栈，并分别置空置 1，重新开始计算新的 和 。 - 如果当前字符是
')'，我们弹出栈顶的两个元素，一个是操作符，一个是括号前计算好的数字，我们将当前的数字乘上操作符，再加上之前的数字，作为新的 。
遍历完字符串 之后，我们返回 。
时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
class Solution:
def calculate(self, s: str) -> int:
stk = []
ans, sign = 0, 1
i, n = 0, len(s)
while i < n:
if s[i].isdigit():
x = 0
j = i
while j < n and s[j].isdigit():
x = x * 10 + int(s[j])
j += 1
ans += sign * x
i = j - 1
elif s[i] == "+":
sign = 1
elif s[i] == "-":
sign = -1
elif s[i] == "(":
stk.append(ans)
stk.append(sign)
ans, sign = 0, 1
elif s[i] == ")":
ans = stk.pop() * ans + stk.pop()
i += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate can implement a stack to maintain operator precedence and operands.
- question_mark
Candidate can handle both unary and binary operators effectively.
- question_mark
Candidate handles parentheses and ensures nested expressions are evaluated correctly.
常见陷阱
外企场景- error
Misunderstanding how to handle unary minus operators (e.g., '-1' or '-(2+3)').
- error
Not properly managing operator precedence when parentheses are involved.
- error
Failing to correctly manage the stack when multiple levels of parentheses are nested.
进阶变体
外企场景- arrow_right_alt
Modify the solution to handle division and multiplication operators in addition to addition and subtraction.
- arrow_right_alt
Implement a more memory-efficient solution where only necessary state is maintained at each step.
- arrow_right_alt
Optimize the solution for handling expressions with significantly larger input sizes.