当初在刷题平台上刷到第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在x3这个绑定生效之前就已经被绑定为外层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, MapString, Integer env)函数表达expr是当前要处理的字符串env是当前可见的所有变量。函数内部先看第一个字符原子直接求值左括号则解析操作符、切分参数、处理子表达式。每遇到一个左括号就进入一层新的递归每进入一个let就创建一个新环境。递归返回时新环境自然销毁不需要显式恢复。这套思路最贴近语言的递归结构代码量小出错点集中。3.3 环境Env的两种实现拷贝 vs 栈式作用域环境管理有两种主流写法我在本地都试过。第一种是每层递归拷贝一份 HashMap。进入let时new HashMap(parentEnv)然后在新 map 上做put并把新 map 传给子表达式。实现最直观但时间和空间开销都是 O(N)。第二种是作用域链栈。全局维护一个ListMapString, 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, MapString, 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); // 当前作用域继承父环境 MapString, Integer env new HashMap(parentEnv); // 按括号平衡切分参数 ListString 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 ListString splitTokens(String body) { ListString 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改用DequeMapString, 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 题不算难但很值得反复打磨——它是理解解释器 解析 求值 环境三者关系的一个极佳入口。