1.题目基本信息
1.1.题目描述
给你一个类似 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.2.题目地址
https://leetcode.cn/problems/parse-lisp-expression/description/
2.解题方法
2.1.解题思路
递归
2.2.解题步骤
第一步，构建维护变量。指针i进行全局遍历表达式；使用scope维护各个域的变量值，使用"变量名->变量值的栈"的哈希表结构进行存储
第二步，设计递归函数。递归函数calc的定义：计算从i开始的当前域的值，并返回；实现：对指针i遍历到的每种情况进行分类讨论
-
2.1.情况1：没有遇到"("，而是小写字母，则匹配变量名varName，并返回当前域中变量varName的值（注意这里的varName是表达式中的varName，包括直接返回的和参与计算的，对于键值对形式的变量名会在l开头的域中进行匹配）
-
2.2.情况2：没有遇到"("，而是数字或者"-"，则直接匹配数值，并返回数值
-
2.3.情况3：遇到"("，后面跟着let。分为"变量名 变量值"、"变量名 变量表达式"、"变量名形式的expr表达式"、"(add/mult a b)形式的expr表达式"
-
2.4.情况4：遇到"("，后面跟着add，递归计算后面的表达式，并进行相加返回
-
2.5.情况5：遇到"("，后面跟着mult，递归计算后面的表达式，并相乘返回
-
2.6.善后处理，跳过当前"("对应的")"，并返回计算结果
3.解题代码
python3代码
from collections import defaultdict
class Solution:
def evaluate(self, expression: str) -> int:
# 思路：递归 O(n)
n = len(expression)
# 第一步，构建维护变量。指针i进行全局遍历表达式；使用scope维护各个域的变量值，使用"变量名->变量值的栈"的哈希表结构进行存储
i = 0
scope = defaultdict(list)
# 第二步，设计递归函数。递归函数calc的定义：计算从i开始的当前域的值，并返回；实现：对指针i遍历到的每种情况进行分类讨论
def calc():
nonlocal i
if expression[i] != "(":
if expression[i].islower():
# 2.1.情况1：没有遇到"("，而是小写字母，则匹配变量名varName，并返回当前域中变量varName的值（注意这里的varName是表达式中的varName，包括直接返回的和参与计算的，对于键值对形式的变量名会在l开头的域中进行匹配）
varName = ""
while i < n and expression[i] != " " and expression[i] != ")":
varName += expression[i]
i += 1
return scope[varName][-1]
else:
# 2.2.情况2：没有遇到"("，而是数字或者"-"，则直接匹配数值，并返回数值
flag = 1
if expression[i] == "-":
flag = -1
i += 1
num = 0
while expression[i].isdigit():
num = num * 10 + int(expression[i])
i += 1
return num * flag
else:
i += 1 # 跳过括号
result = 0
# 2.3.情况3：遇到"("，后面跟着let。分为"变量名 变量值"、"变量名 变量表达式"、"变量名形式的expr表达式"、"(add/mult a b)形式的expr表达式"
if expression[i] == "l":
i += 4 # 跳过"let "
varNames = [] # 存储当前域变量名，为了后续当前域计算完成后恢复scope
while True:
# 循环匹配变量和表达式
if not expression[i].islower():
# 非变量名情况，即表达式，包括()表达式和数字表达式两种
result = calc()
break
else:
varName = ""
while expression[i] != " " and expression[i] != ")":
varName += expression[i]
i += 1
# 第3种表达式情况，匹配完成情况，即")"情况，由于发生在varName匹配后，所以这是个变量形式的返回表达式进行返回
if expression[i] == ")":
result = scope[varName][-1]
break
i += 1 # 跳过变量名后的空格
varValue = calc() # 匹配数字或者递归计算表达式
scope[varName].append(varValue) # 将匹配到变量压入栈中
i += 1 # 跳过变量数值或者表达式后的空格
varNames.append(varName)
# 在该以let开头的域计算完成后，释放该域中的局部变量
for varName in varNames:
scope[varName].pop()
# 2.4.情况4：遇到"("，后面跟着add，递归计算后面的表达式，并进行相加返回
elif expression[i] == "a":
i += 4 # 跳过"add "
val1 = calc()
i += 1 # 跳过空格
val2 = calc()
result = val1 + val2
# 2.5.情况5：遇到"("，后面跟着mult，递归计算后面的表达式，并相乘返回
elif expression[i] == "m":
i += 5
val1 = calc()
i += 1
val2 = calc()
result = val1 * val2
# 2.6.善后处理，跳过当前"("对应的")"，并返回计算结果
i += 1 # 跳过")"
return result
return calc()4.执行结果
