LeetCode 题解工作台
Lisp 语法解析
给你一个类似 Lisp 语句的字符串表达式 expression ，求出其计算结果。 表达式语法如下所示: 表达式可以为整数， let 表达式， add 表达式， mult 表达式，或赋值的变量。表达式的结果总是一个整数。 (整数可以是正整数、负整数、0) let 表达式采用 "(let v 1 e…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
时间复杂度 。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个类似 Lisp 语句的字符串表达式 expression，求出其计算结果。
表达式语法如下所示:
- 表达式可以为整数，let 表达式，add 表达式，mult 表达式，或赋值的变量。表达式的结果总是一个整数。
- (整数可以是正整数、负整数、0)
- let 表达式采用
"(let v1 e1 v2 e2 ... vn en expr)"的形式，其中let总是以字符串"let"来表示，接下来会跟随一对或多对交替的变量和表达式，也就是说，第一个变量v1被分配为表达式e1的值，第二个变量v2被分配为表达式e2的值，依次类推；最终let表达式的值为expr表达式的值。 - add 表达式表示为
"(add e1 e2)"，其中add总是以字符串"add"来表示，该表达式总是包含两个表达式e1、e2，最终结果是e1表达式的值与e2表达式的值之 和 。 - mult 表达式表示为
"(mult e1 e2)"，其中mult总是以字符串"mult"表示，该表达式总是包含两个表达式e1、e2，最终结果是e1表达式的值与e2表达式的值之 积 。 - 在该题目中，变量名以小写字符开始，之后跟随 0 个或多个小写字符或数字。为了方便，
"add"，"let"，"mult"会被定义为 "关键字" ，不会用作变量名。 - 最后，要说一下作用域的概念。计算变量名所对应的表达式时，在计算上下文中，首先检查最内层作用域（按括号计），然后按顺序依次检查外部作用域。测试用例中每一个表达式都是合法的。有关作用域的更多详细信息，请参阅示例。
示例 1：
输入：expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))" 输出：14 解释： 计算表达式 (add x y), 在检查变量 x 值时， 在变量的上下文中由最内层作用域依次向外检查。 首先找到 x = 3, 所以此处的 x 值是 3 。
示例 2：
输入：expression = "(let x 3 x 2 x)" 输出：2 解释：let 语句中的赋值运算按顺序处理即可。
示例 3：
输入：expression = "(let x 1 y 2 x (add x y) (add x y))" 输出：5 解释： 第一个 (add x y) 计算结果是 3，并且将此值赋给了 x 。 第二个 (add x y) 计算结果是 3 + 2 = 5 。
提示：
1 <= expression.length <= 2000exprssion中不含前导和尾随空格expressoin中的不同部分（token）之间用单个空格进行分隔- 答案和所有中间计算结果都符合 32-bit 整数范围
- 测试用例中的表达式均为合法的且最终结果为整数
解题思路
方法一：递归
时间复杂度 。
class Solution:
def evaluate(self, expression: str) -> int:
def parseVar():
nonlocal i
j = i
while i < n and expression[i] not in " )":
i += 1
return expression[j:i]
def parseInt():
nonlocal i
sign, v = 1, 0
if expression[i] == "-":
sign = -1
i += 1
while i < n and expression[i].isdigit():
v = v * 10 + int(expression[i])
i += 1
return sign * v
def eval():
nonlocal i
if expression[i] != "(":
return scope[parseVar()][-1] if expression[i].islower() else parseInt()
i += 1
if expression[i] == "l":
i += 4
vars = []
while 1:
var = parseVar()
if expression[i] == ")":
ans = scope[var][-1]
break
vars.append(var)
i += 1
scope[var].append(eval())
i += 1
if not expression[i].islower():
ans = eval()
break
for v in vars:
scope[v].pop()
else:
add = expression[i] == "a"
i += 4 if add else 5
a = eval()
i += 1
b = eval()
ans = a + b if add else a * b
i += 1
return ans
i, n = 0, len(expression)
scope = defaultdict(list)
return eval()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate explain the trade-offs between recursion and iterative solutions in evaluating expressions?
- question_mark
Does the candidate handle nested scopes correctly with the stack and hash table?
- question_mark
How well does the candidate optimize for time and space complexity in managing the stack?
常见陷阱
外企场景- error
Failing to correctly manage nested variable scopes can lead to incorrect results.
- error
Not utilizing a stack efficiently to track the current variable context can cause scoping issues.
- error
Misunderstanding the recursion depth and stack size, leading to performance issues on large expressions.
进阶变体
外企场景- arrow_right_alt
Modify the problem to evaluate a broader range of operations beyond just 'add' and 'mult'.
- arrow_right_alt
Change the expression format to handle different types of scopes or operations like 'if' or 'define'.
- arrow_right_alt
Optimize the solution to handle larger expressions by implementing iterative evaluation instead of recursion.