当初在刷题平台上刷到第736题的时候，我差点把它当成一道"只要递归就能过"的简单题。题目要求实现public int evaluate(String expression)，输入是一段 Lisp 风格表达式，输出是一个整数。等你真动手写，才会发现它把"递归下降解析""作用域管理"和"顺序求值"三个独立考点塞进了同一道题里，任何一个环节没想透，都会在某个隐蔽用例上翻车。这篇文章我就把我踩过的坑、测试过的边界和最终稳定通过的实现思路完整记录下来，给同样卡在这道题上的朋友做个参考。
1. 这道题表面考递归，实际考的是三件事
1.1 题目到底在求什么
先回顾一下题目要求。输入字符串 expression 是三种形式之一：
- 整数：比如
1、-2，可以直接解析成 int； - 变量：比如
x、y，以字母开头，需要到当前环境中查值； - 表达式：三种形式，分别是
(let v1 e1 v2 e2 ... expr)、(add e1 e2)、(mult e1 e2)。
抬头一看，"这不就是一个带括号的递归求值吗"，但题目埋了一个关键设定：let表达式允许定义局部变量，并且局部变量会遮蔽外层同名变量。也就是说，这道题不是单纯解析括号，而是要在递归过程中维护一个可以随时新增、覆盖、回收的作用域集合。
我当时先踩了一个坑：想用全局 HashMap 存变量，结果(let x 2 (let x 3 x))这种用例输出永远是 2。原因很简单，如果只在全局环境里put("x", 3)，内层求值结束后没有把 x 恢复成 2，那外层再引用 x 时就错乱了。这就是作用域没有隔离造成的典型问题。
1.2 三个考点对应的三个难点
把这道题拆开看，真正的考点有三个。
第一是语法解析：必须能正确识别一个完整子表达式。简单用空格切分是不够的，因为(add 1 (mult 2 3))中第二个参数本身又是一个含括号的表达式，普通 split 会把(mult、2、3))拆成三个 token。
第二是作用域管理：每次进入let都要新建一个作用域，退出后销毁。变量查找遵循"就近原则"，内层作用域能访问外层变量，但同名变量以内层为准。
第三是顺序求值：let的绑定是逐个生效的。例如(let x 2 (let y x x))，内层绑定y等于x时，x已经绑定为 2，所以y的值是 2。这个顺序性写代码时很容易搞反——如果先把所有绑定表达式都求值再统一写入环境，结果就会不一样。
为了便于对比，我整理了一张小表：
| 考点 | 容易犯的错误 | 正确做法 |
|---|---|---|
| 子表达式切分 | 用空格直接 split | 按括号平衡切分 |
| 作用域隔离 | 全程使用同一个全局 Map | 每层 let 拷贝或压栈新环境 |
| let 顺序绑定 | 先算完所有表达式再统一绑定 | 每绑定一个变量就立即写入环境 |
1.3 一个容易被忽略的信息：let 的顺序绑定
很多题解提到"新建一个 Map，然后把键值对放进去"，但没有强调顺序。其实这正是let和普通"同时绑定"语义最大的区别。
举个例子：(let x 2 (let x 3 x))，新手可能会认为两个x绑定互不影响，最后一个x应该取内层绑定 3，这个理解是对的。但如果换成(let x 2 (let y x (let x 3 y)))，就需要看清楚：y在x=3这个绑定生效之前就已经被绑定为外层x的值，也就是 2。绑定是依次执行的，不是把所有变量名预先占好坑。
这个认知直接决定了代码里let分支的循环方式：必须"绑定一个、求值一个、写入环境一个"，然后进行下一个绑定。否则看起来很合理的"先收集表达式，再一起求值"方案，会在复杂用例上全军覆没。
2. 先别急着写代码，把 Lisp 表达式的语法结构拆清楚
2.1 表达式只有三类原子与三类组合
Lisp 的这份子集语法其实非常简洁。原子表达式只有整数和变量两种，组合表达式只有let、add、mult三种。写代码时不需要实现一个完整的词法分析器，只需要在需要时区分的几个节点做分支。
关键分支是看字符串第一个字符：
- 如果是数字或负号，说明是整数；
- 如果是字母，说明是变量；
- 如果是左括号，说明是复合表达式。
复合表达式的第一个 token 一定是操作符，剩下内容根据操作符类型决定怎么处理。add和mult后面固定跟两个子表达式，let后面则是偶数个参数：若干对"变量名 + 绑定表达式"，最后再跟一个最终求值表达式。
2.2 let 的"变量绑定优先于最终表达式求值"
(let v1 e1 v2 e2 ... expr)的语义是：依次求值e1，将v1绑定为其结果；依次求值e2，将v2绑定为其结果；最后在所有绑定都生效的环境里求值expr。
这么说可能有点抽象，我拆一个具体例子。给定(let x 2 (add x 1))，执行顺序是：
- 进入 let，创建新作用域；
- 求值
2，绑定x = 2； - 求值
(add x 1)，此时x已经有值 2，结果是 3； - 返回 3，离开作用域。
注意第二步和第三步的先后顺序不能反。如果把整个绑定过程看作"先建立环境，再求值最终表达式"，那绑定阶段就要按顺序执行。我在实现时直接在循环里同步更新当前环境，而不是把表达式收集完再求值，就是这个原因。
2.3 作用域与变量遮蔽的判定规则
变量遮蔽的行为可以类比日常写代码时的局部变量覆盖全局变量。内层let定义的变量，会遮蔽外层同名变量，直到内层作用域结束。作用域结束之后，外层同名变量恢复可见。
举个例子：
(let x 10 (let x 20 x) )最内层x查到的是 20，而不是外层的 10。如果求值结束后又回到外层环境继续使用x，比如写成(let x 10 (add (let x 20 x) x))，那么第二个x又恢复成 10，整体结果是 30。
这要求实现时每个递归层级必须持有独立的环境视图，同时还要能往上追溯到更外层的作用域。
3. 解法选型：递归下降为主，为什么不是纯栈
3.1 常规栈解法的问题
很多括号类题目可以用栈解决，比如计算器系列。但这道题有一个特殊点：同一个括号片段，内部既包含要执行的绑定操作，又包含要返回的最终表达式，只靠一个栈很难表达"当前处在哪个 let 的哪个参数位"。
我之前尝试过用状态机加栈模拟，结果代码越写越长。原因在于：let的绑定动作依赖当前环境，而环境本身又随着递归深度变化；用栈保存环境快照虽然可行，但状态转移非常容易漏。相比之下，递归下降解析天然拥有"当前调用栈即作用域链"的性质。
3.2 递归下降在这里天然匹配语法
递归下降的核心思路是：用一个函数处理一个语法单元，如果遇到子表达式就递归调用自身。这个题目里的语法单元恰好可以用一个统一的eval(String expr, Map<String, Integer> env)函数表达：
expr是当前要处理的字符串；env是当前可见的所有变量。
函数内部先看第一个字符：原子直接求值，左括号则解析操作符、切分参数、处理子表达式。每遇到一个左括号就进入一层新的递归，每进入一个let就创建一个新环境。递归返回时，新环境自然销毁，不需要显式恢复。
这套思路最贴近语言的递归结构，代码量小，出错点集中。
3.3 环境（Env）的两种实现：拷贝 vs 栈式作用域
环境管理有两种主流写法，我在本地都试过。
第一种是每层递归拷贝一份 HashMap。进入let时new HashMap<>(parentEnv)，然后在新 map 上做put，并把新 map 传给子表达式。实现最直观，但时间和空间开销都是 O(N)。
第二种是作用域链栈。全局维护一个List<Map<String, Integer>>，进入let时 push 一个新空 map，查找变量时从栈顶往下找，退出let时 pop。省去了整表拷贝，但查找变量时需要遍历整个栈。
| 方案 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 拷贝 Map | 代码直观、无状态残留 | 每次递归复制一张表 | 题目输入规模较小，足够用 |
| 作用域链栈 | 节省拷贝开销，语义更贴近真实解释器 | 查找变量多一层遍历 | 输入很长、追求更优复杂度时 |
这道题虽然要求写一个"解释器"，但输入规模并不是很大，用 HashMap 拷贝方案完全够用，而且不容易写错。我第一次提交就是拷贝方案，一次通过。
4. Java实现：核心代码逐段拆解
4.1 入口与原子表达式处理
先给出整体框架：
public int evaluate(String expression) { return eval(expression, new HashMap<>()); } private int eval(String expr, Map<String, Integer> parentEnv) { char first = expr.charAt(0); // 不是左括号，说明是整数或变量 if (first != '(') { if (Character.isDigit(first) || first == '-') { return Integer.parseInt(expr); } return parentEnv.get(expr); } // 去掉最外层括号 String inner = expr.substring(1, expr.length() - 1); // 取操作符，到第一个空格为止 int spaceIdx = inner.indexOf(' '); String op = inner.substring(0, spaceIdx); String body = inner.substring(spaceIdx + 1); // 当前作用域继承父环境 Map<String, Integer> env = new HashMap<>(parentEnv); // 按括号平衡切分参数 List<String> tokens = splitTokens(body); if ("let".equals(op)) { // 后面是 var expr var expr ... finalExpr for (int i = 0; i < tokens.size() - 1; i += 2) { String var = tokens.get(i); int val = eval(tokens.get(i + 1), env); env.put(var, val); } return eval(tokens.get(tokens.size() - 1), env); } else { int left = eval(tokens.get(0), env); int right = eval(tokens.get(1), env); return "add".equals(op) ? left + right : left * right; } }入口方法的高层逻辑很明确：先对完整的 expression 调用eval，初始环境为空。eval本身复用同一套逻辑处理所有子表达式。
注意这里有个细节：parentEnv.get(expr)返回值类型是Integer，如果变量确实不在环境中，会返回null并在自动拆箱时抛 NullPointerException。题目保证输入合法，所以正常测试不会出问题，但如果你要写得更健壮，可以在查不到变量时主动抛一个带变量名的异常，方便调试。
4.2 按括号平衡切分参数：splitTokens 的实现意图
add、mult、let后面的参数个数和写法不同，但都需要先把 body 切成独立的 token。比如(add 1 (mult 2 3))，去掉外层括号后得到的是add 1 (mult 2 3)，body 是1 (mult 2 3)。
如果直接body.split(" ")，会得到"1"、"(mult"、"2"、"3))"这种错误结果。正确做法是维护一个括号深度计数器，只有深度为 0 时的空格才是 token 分隔符：
private List<String> splitTokens(String body) { List<String> res = new ArrayList<>(); int start = 0; int balance = 0; for (int i = 0; i < body.length(); i++) { char c = body.charAt(i); if (c == '(') { balance++; } else if (c == ')') { balance--; } else if (c == ' ' && balance == 0) { res.add(body.substring(start, i)); start = i + 1; } } res.add(body.substring(start)); return res; }这里的核心是balance == 0才认为空格是分隔点。遇到左括号 balance 加一，遇到右括号减一，只有回到最外层时空格才表示一个完整参数结束。
4.3 let 分支的逐对绑定逻辑
let分支是所有逻辑里最需要小心的地方。tokens 的最后一个元素是最终求值表达式，前面的元素成对出现：偶数位置是变量名，奇数位置是绑定表达式。
循环里我直接在当前env上边求值边写入：
for (int i = 0; i < tokens.size() - 1; i += 2) { String var = tokens.get(i); int val = eval(tokens.get(i + 1), env); env.put(var, val); } return eval(tokens.get(tokens.size() - 1), env);这个循环的一个细节是：绑定表达式tokens.get(i + 1)的求值环境是env，而env在上一次循环中可能已经被放入了新的变量。这就是"顺序绑定"的正确实现。
如果把这段改成先收集所有(var, expr)对，再统一求值，遇到(let x 2 (let y x x))就会算错，因为计算y的绑定表达式x时，环境里可能还没有内层x的值。边写边求值看起来只是代码顺序问题，实际是语义问题。
4.4 add/mult 分支的对称处理
加法和乘法在语法结构上完全对称，都是两个子表达式，区别只在最后一步的运算符。
int left = eval(tokens.get(0), env); int right = eval(tokens.get(1), env); return "add".equals(op) ? left + right : left * right;这里tokens.get(0)和tokens.get(1)可能是整数，可能是变量，也可能是嵌套表达式，统一交给eval处理即可。因为splitTokens已经保证了两个完整子表达式被正确切分，所以这里能非常简洁地处理任意嵌套。
我自己在实现时也想过是否要把add、mult单独抽个函数，后来发现没有必要。两个分支逻辑太像了，抽出来反而增加跳转，可读性并不会更好。
5. 提交之后才遇到的边界问题与隐蔽坑
5.1 负数解析：一个字符判断的遗漏
我第一次写原子判断时只判断了Character.isDigit(first)，没有包含first == '-'，结果遇到(-2)这种输入直接当成变量去查环境，返回 null 然后抛异常。
负数在这个题目里是合法输入，Integer.parseInt("-2")可以直接解析，不需要手动处理符号位。关键是入口判断不能漏掉负号。
if (Character.isDigit(first) || first == '-') { return Integer.parseInt(expr); }5.2 变量遮蔽引发的心智负担
变量遮蔽是这道题最"烧脑"的部分，尤其是多层嵌套时。看这个用例：
(let x 2 (add (let x 3 (mult x 2)) 5))内层(let x 3 (mult x 2))中x绑定为 3，所以结果是 6。最终外层加法是6 + 5 = 11。注意这里内层绑定没有破坏外层x = 2，因为new HashMap<>(parentEnv)已经把环境隔离开了。
如果我用的是全局变量而不是局部拷贝，这个用例绝对会挂。这也是为什么我一直强调"每层 let 都要有独立环境"。
5.3 嵌套表达式切分中的 balance 计数细节
splitTokens方法看起来简单，但我在写的时候忽略了一个边界：body 末尾不能出现多余的空格，否则最后一次res.add(body.substring(start))会加入一个空字符串。好在题目输入格式固定，不会有多余空格。
另一个需要留意的点是：括号深度计算必须处理嵌套里的原子表达式和大括号内空格。例如 body 是x (add 1 2) (mult x 3)，空格出现在x和(add之间时 balance 为 0，所以能切成三个 token；而add和1之间的空格在 balance 为 1 的情况下不会切开，这样保证了(add 1 2)作为一个整体被保留。
5.4 输入规模与效率冗余
这道题如果用 HashMap 拷贝方案，每次递归都要复制一张表，最坏情况下时间复杂度接近 O(N²)，空间也是 O(N²)。但题目给定的表达式长度有限，实测完全可以通过。
如果你出于性能考虑，可以改成作用域链栈。不过说实话，这道题的练习重点不在常数优化，而在理解递归与作用域的耦合方式。我提交通过后也尝试过栈式作用域版本，代码多了十几行，效果差不多，但对理解"环境是动态作用域还是静态作用域"很有帮助。
6. 把736题放进"解析器"系列里横向看
6.1 与基本计算器系列的共同底层能力
刷题多了会发现，凡是"计算器"类型的题目，底层能力都绕不开三个：切分 token、递归下降、处理优先级。736 题没有加减乘除优先级问题，因为add和mult是用显式括号区分优先级的，优先级不需要额外判断。
但它的复杂之处在于引入了变量绑定。变量绑定意味着求值不再是纯粹"自底向上的树形归约"，而是"一边构建环境、一边求值"。这一点和带函数调用的解释器更接近，比单纯的计算器前进了一步。
6.2 从这道题延伸到真正的解释器设计
如果你打算继续深入，可以试着在 736 的基础上扩展几个特性：
- 支持函数定义与函数调用：
(define (f x) (add x 1))，调用时需要一个函数环境； - 支持条件分支：
(if (> x 0) x (- x))，需要把布尔值和比较运算符引入； - 支持 begin 表达式：按顺序执行多条语句，取最后一个表达式的值。
这些扩展其实都在强化同一个核心能力：在递归求值过程中正确管理环境。736 题相当于一个迷你解释器的最小内核。
6.3 两个可以继续尝试的变体
如果你已经把标准解法写通了，我建议再试两个变体。
变体一：不拷贝 HashMap，改用Deque<Map<String, Integer>>模拟调用栈，并实现变量查找的逐层回溯。这个练习能帮你理解真实解释器的作用域链结构。
变体二：把splitTokens改成基于指针的单次扫描，不产生临时子字符串。也就是在eval内部直接通过start、end下标定位子表达式，减少substring的开销。这个练习可以加深你对字符串切片成本的理解。
最后分享一个我实际测试时常用的用例清单，覆盖了主要的边界场景：
(add 1 2) // 3 (mult 3 (add 2 3)) // 15 (let x 2 (mult x 5)) // 10 (let x 2 (let x 3 x)) // 3 (let x 2 (add (let x 3 x) x)) // 5 (let x 2 (let y x (let x 3 y))) // 2 (let x 10 (add (let x 20 x) x)) // 30每次改完代码，把这组用例跑一遍，基本上能覆盖多数隐蔽问题。736 题不算难，但很值得反复打磨——它是理解"解释器 = 解析 + 求值 + 环境"三者关系的一个极佳入口。
