第一次见到public int evaluate(String expression)这个签名的时候我正在某在线判题系统上刷第 736 题。题目标签写着“Lisp 语法分析”说人话就是给你一段 Lisp 风格的字符串表达式让你手写一个微型解释器把结果算出来。那题输入可能长这样(let x 2 (mult x (add x 3)))输出则是一个整数。别被“Lisp”吓到题目里只保留了三样东西整数、变量、以及 let / add / mult 三种特殊形式。只要能把括号、空白和变量作用域理顺这道题就能拿下。这道题适合谁我觉得适合两类人一类是准备算法面试、想在“递归解析”和“作用域管理”上查漏补缺的人另一类是学着玩解释器、想看看最简单的 eval 是怎么落地的初学者。后面我会从题目规则拆起给出一版可以直接跑的 Java 实现然后专门挑最容易翻车的几个细节出来说。如果你也卡在这题过读完应该能把evaluate写出来并讲明白。1. 题目拆解这题到底在考什么1.1 表达式语法与公共接口先把这个题的输入输出讲清楚。题目只给了你一个方法入口public int evaluate(String expression)expression是一个字符串里面是以下几种东西自由组合语法形式含义示例整数直接返回数值支持负数123、-1变量在使用前必须由let绑定x、abc(let v1 e1 v2 e2 ... body)依次绑定变量然后在新作用域里返回body的值(let x 2 (mult x 5))(add e1 e2)返回两个表达式之和(add 1 2)(mult e1 e2)返回两个表达式之积(mult 3 (add 2 3))变量名由小写字母组成可能是多字母字符串。整数可以是负数。表达式里允许有空格而且同一层可能出现多个连续空格。括号表达式都以(开头、)结尾操作符之后至少有对应的运算对象。官方保证输入合法不存在未定义变量的读取所以你可以先不写非法输入处理但实现里最好还是有点防御。这道题在判题系统里的难度分级偏高。原因很简单它不是背模板就能过的题。考的是你能否把一个带嵌套的文本“翻译”成计算过程中间还牵扯到递归、索引移动、作用域快照。写出来容易写对很难。1.2 高难度背后的三个核心点我刷过的题也不算少但 736 题给我留下的印象特别深因为它把三个容易出错的东西叠在了一起。第一是字符串解析。表达式不是矩阵、不是数组而是一段带括号的文本。你得自己决定怎么从文本里切出 token怎么跳过空格怎么判断一个(对应的)是谁。如果你过去习惯了用split处理输入会发现这套玩法完全不是那么回事。第二是递归结构。(add 1 (mult 2 3))这种嵌套天然对应递归下降。看到(就递归进入子表达式看到)就返回结果。如果你用循环加栈去模拟不是不行但是要把 token 产生式、栈内状态机都维护好代码量会失控。面试里大部分人的第一反应是递归。第三是作用域管理。Lisp 的let有点像局部变量声明但有个关键语义每个 let 绑定只在自己的 body 内有效而且新的绑定会影响后续绑定。例如(let x 2 x 3 x)的值是 3第二个 x 绑定基于外层 x2 算出 3然后把 x 覆盖成 3最后一个 x 取到 3。这个“同一作用域内逐步覆盖”的规则经常被写成纯靠拷贝环境导致的结果不对。把这三个点揉在一起一个坑接着一个坑。下面聊聊我为什么选递归下降以及环境到底该怎么传。2. 整体设计递归下降 作用域环境2.1 为什么递归下降比栈模拟更自然一开始我没急着写代码先想的是能不能不递归直接用栈解析毕竟 Lisp 表达式有括号匹配理论上可以用栈把 token 收集起来再反向求值。但仔细一推发现栈方案需要你自己维护“当前处于哪个表达式、还差几个操作数没解析”等状态写起来几乎等于手工模拟递归栈。而且一旦遇到let还得额外记录当前作用域内的绑定状态复杂度立刻上去了。递归下降就优雅得多看到一个左括号就递归处理括号里的内容返回一个整数看到一个数字或变量就直接返回当前值看到let/add/mult分别按自己的规则继续递归。整个解析器和表达式的语法结构一一对应代码哪里该做什么肉眼能看出来。后面就算要扩展新操作符也只需要加一个分支不用动整体框架。用递归下降的代价是担心栈深度。但这道题限定了输入规模递归深度不会太大所以完全可以在面试里直接用。你甚至可以把它当成手写解释器的第一个里程碑版本。2.2 作用域环境必须“逐层隔离”的原因环境environment是这个题最容易阴沟翻船的地方。什么叫“逐层隔离”看这个例子(let x 2 (let x 3 x))外层 let 把 x 绑定为 2内层 let 又把 x 绑定为 3最后内层的 body 是x应该取当前最近的绑定也就是 3。整个表达式的结果是 3而不是 2。等内层 let 结束x 在外层仍然应该是 2。如果你从头到尾只用一个 Map内层把 x 改成 3 后外层也跟着变 3那就错了。正确的做法是进入一个 let 作用域时基于当前环境复制出一个新的 Map之后的绑定都写在这个新 Map 上body 也在这个新 Map 上求值。递归返回后新 Map 被丢弃外层环境毫发无损。这就是词法作用域lexical scope最简单的实现方式。更微妙的是同一 let 内的多次绑定“后半段的绑定表达式能否看到前半段新引入的变量”答案是可以。比如(let x 2 y x (add x y))这里绑定 x2然后绑定 yx 时x 已经可见所以 y 也是 2最终 add 得到 4。这意味着你不能把每个绑定都建立在“初始外层环境”上各搞一份而应该在一个新 Map 上连续 put。换句话说同一 let 内后面的绑定可以看到前面绑定所产生的变量这是逐步可见的。这点我后面实现里会用“同一个 letEnv 对象被多个绑定共享”的方式来保证。3. 核心细节解析解析器怎么写出不踩坑3.1 索引指针与跳空白既然要自己扫描字符串我建议用类字段保存当前索引idx而不是每次递归都传一个int[]或者返回解析后的新索引。虽然局部变量更干净但 Java 里要返回一个 int 结果还得同时更新位置最终还得包一个内部类或者传引用数组。用类字段实现最简单也方便调试。只要保证每次evaluate调用前把idx重置为 0 就行。跳空白函数长这样private void skipWhitespace() { while (idx input.length() input.charAt(idx) ) { idx; } }为什么只跳空格因为题目输入里只会出现空格作为分隔符没有 tab 换行。但是为了保险你也可以多跳几个空白字符。关键是每次读取完一个 token 或一个表达式后下一步解析前都要跳一次空白。很多人漏了这一步导致把 (add开头的空格算进 token解析直接崩。索引指针还要注意负数。-123的-是数字的一部分不能当成普通符号跳过。所以判断一个表达式是不是数字时条件是ch -或Character.isDigit(ch)不能只看 isDigit。变量名绝不会以-开头。3.2 识别 let 的“变量绑定”和“body”逻辑let 是最容易写错的环节。因为变量绑定对和 body 都是表达式而 body 可能是一个变量名也可能是一个整数还可能是一个括号表达式。怎么区分我用的方法是“看当前字符的形态”如果当前字符是(或数字或-那它只能是一个表达式也就是 body直接递归求值并返回。如果当前字符是小写字母那就先读一个变量名 token然后看变量名后面紧跟的是不是右括号。如果是右括号说明没有对应的初始化表达式那这个变量名就是 body如果不是右括号说明它是一个绑定变量后面还得解析一个值表达式。这个逻辑要反复读几遍因为它是这个题的核心。具体到代码let 分支可以这样组织跳过(let后的空格。进入一个 while(true) 循环。跳过空白检查当前字符。如果当前字符是)说明可能遇到了空 body 之类的边界一般合法输入不会走到这里为了健壮可以返回当前记录的默认值或直接报错。如果当前字符是(、数字、-直接把它当作 body 来处理解析完整个表达式后返回其值。如果当前字符是字母则读取变量名 token。读取变量名之后跳空白。如果当前字符是)那这个变量名就是 body直接查环境返回它的值并消费掉右括号。如果不是)则解析一个值表达式把这个变量和值放入 letEnv继续循环处理下一对绑定。这里的核心思想是只有绑定列表在 body 之前而且绑定列表一定是成对出现的。body 之前的所有 token 都可以归类为“变量名 绑定值表达式”。body 本身是整个 let 表达式最后一项。一旦遇到不能作为变量名的起始字符就说明前面没有更多绑定了当前就是 body。这个技巧在多个题解里都能见到实测非常稳。注意读取变量名 token 时要小心变量名继续读取直到遇到空格或右括号。如果遇到括号比如变量名x后面直接是)那就停住让主循环看到右括号。不能在 parseToken 里把右括号吞掉否则会出错。3.3 add/mult 的二元求值add 和 mult 比 let 简单得多因为它们是固定二元运算。流程是跳过(读取操作符add或mult。跳空白。递归解析第一个子表达式。跳空白。递归解析第二个子表达式。跳空白消费掉右括号。返回两个值的和或积。这里有个容易忽略的点操作符到底要不要读成 token需要。因为(后面跟着的是字符串add不是a一个字符。虽然这里没有addx这种混写但严谨起见按 token 读取然后equals判断。等读完操作符再解析两个操作数。加法和乘法都不需要新建作用域使用当前环境继续往下递归即可。它们内部出现(let ...)时由 let 自己创建子环境外层变量仍然能访问到这正好符合 Lisp 的语义。3.4 变量查找与数字解析变量查找在 let 环境里用MapString, Integer env.get(name)取值。合法输入保证变量必有定义所以返回Integer不会为 null。如果你想让代码更稳可以在 get 之后判空并抛一个带变量名的异常方便调试。我在本地调试时就经常靠这个定位“哪个变量没绑定”。数字解析因为我们已经判断过当前 token 是数字或负数可以直接用Integer.parseInt。但由于 token 可能是-123或者123它正好止于空格或右括号所以解析是安全的。更稳的做法是自己写一个 parseNumberprivate int parseIntFromCurrent() { int sign 1; if (input.charAt(idx) -) { sign -1; idx; } int num 0; while (idx input.length() Character.isDigit(input.charAt(idx))) { num num * 10 (input.charAt(idx) - 0); idx; } return sign * num; }这样就算以后输入里混进奇怪字符也不容易崩。不过在原题约束下直接Integer.parseInt(parseToken())也够用。4. 完整 Java 实现从签名到逐行说明4.1 基础字段与入口方法我先把完整代码放在前面后面再分段解释。import java.util.HashMap; import java.util.Map; public class Solution { private String input; private int idx; public int evaluate(String expression) { this.input expression; this.idx 0; return evaluateExpr(new HashMap()); } private int evaluateExpr(MapString, Integer outerEnv) { skipWhitespace(); char c input.charAt(idx); if (c () { idx; // skip ( skipWhitespace(); String op parseToken(); skipWhitespace(); if (op.equals(add) || op.equals(mult)) { int v1 evaluateExpr(outerEnv); skipWhitespace(); int v2 evaluateExpr(outerEnv); skipWhitespace(); if (idx input.length() input.charAt(idx) )) { idx; } return op.equals(add) ? v1 v2 : v1 * v2; } else { // let MapString, Integer letEnv new HashMap(outerEnv); while (true) { skipWhitespace(); if (idx input.length()) break; char local input.charAt(idx); if (local ( || local - || Character.isDigit(local)) { // body is an expression int bodyVal evaluateExpr(letEnv); skipWhitespace(); if (idx input.length() input.charAt(idx) )) { idx; } return bodyVal; } else { // must be a variable token, but might be bodys variable String var parseToken(); skipWhitespace(); if (idx input.length() input.charAt(idx) )) { // var is body int bodyVal letEnv.get(var); idx; return bodyVal; } else { int val evaluateExpr(letEnv); letEnv.put(var, val); } } } return 0; // unreachable for valid input } } if (c - || Character.isDigit(c)) { return parseNumber(); } // variable String name parseToken(); return outerEnv.get(name); } private String parseToken() { StringBuilder sb new StringBuilder(); while (idx input.length() input.charAt(idx) ! input.charAt(idx) ! )) { sb.append(input.charAt(idx)); idx; } return sb.toString(); } private int parseNumber() { int sign 1; if (input.charAt(idx) -) { sign -1; idx; } int num 0; while (idx input.length() Character.isDigit(input.charAt(idx))) { num num * 10 (input.charAt(idx) - 0); idx; } return sign * num; } private void skipWhitespace() { while (idx input.length() input.charAt(idx) ) { idx; } } }这段代码可以跑通大部分样例。下面把每个关键点拆开。4.2 私有递归方法 evaluateExprevaluateExpr(MapString, Integer outerEnv)是整个解析器的核心。它每次负责解析并返回一个完整的表达式同时移动idx到该表达式之后的第一个未消费字符。开头先跳过空白再取当前位置字符。为什么先跳空白因为调用方可能在操作数之间留了空格例如(add 1 2)在1和2之间有空格但我们递归调用解析完1后idx停在空格处必须跳过才能看到2或右括号。所以在方法入口处统一跳一次就能保证后续逻辑看到有效字符。但要注意递归调用自身的时候入口跳空白会把表达式前的空格全部吞掉这是正确的。当看到(时说明这是一个复合表达式。先跳过(然后读取操作符 token。这里假定(后面必然跟着add/mult/let之一不会有嵌套括号直接跟在左括号后面。原题合法输入保证如此但如果你希望更健壮可以判断 parseToken 的结果再决定。然后分两条路add/mult 或 let。add/mult 都在同一个outerEnv上解析两个操作数因为这种运算不会引入新变量。解析完第二个操作数后理论上当前位置应该是)于是消费它。如果由于某种原因不是右括号代码也不会崩只是 idx 没动后续可能出错。所以我在代码里加了if (idx input.length() input.charAt(idx) )) idx;的防御性判断。面试时你可以直接无条件idx因为输入合法。let 分支是重点。进入 let 分支时idx指向let之后的下一个 token 的开头。这里我复制了一份letEnv而不是直接改outerEnv。循环里每次先看当前字符形态如果是(、数字、-那就只能是 body。这时调用evaluateExpr(letEnv)解析 body然后消费右括号并返回。如果是字母先读变量名再看后面。后面是右括号说明 body 是变量名后面不是右括号说明这个变量名确实是一个绑定声明接着解析值表达式并put到letEnv。这个逻辑依赖一个前提绑定列表中的变量名一定是以字母开头的简单 token而 body 若是变量名也同样是字母开头。单看当前字符无法区分“这是绑定变量”还是“这是 body 变量”于是引入“后面是否紧跟右括号”的区分规则绑定变量后面必须跟着值表达式不会直接是右括号body 是最后一个表达式后面就是右括号。所以这个规则是可靠的。4.3 辅助工具方法parseToken读取从当前 idx 开始到空格或右括号之间的连续字符。这个工具对操作符、变量名都适用。注意它不消费右括号也不消费空格调用者需要在合适的时机跳空白或主动处理右括号。parseNumber用 sign 标记负数然后从首个数字位开始累积。为什么不直接用 Integer.parseInt(parseToken())因为 parseToken 会读取到空格或右括号确实也能拿到完整数字字符串那也行。但自己写 parseNumber 更清晰也避免 parseToken 误把-单独处理等边界问题。两种写法都可以选一种保持风格统一。skipWhitespace只处理空格。我遇到有些测试输入里可能出现 tab 或换行但离线评测基本不会。如果你要更严谨可以改成Character.isWhitespace(input.charAt(idx))这样也能处理其他空白。但要注意token 内部不可能出现空白所以不会误伤。4.4 测试用例与复杂度分析我本地跑了这样一组用例Solution sol new Solution(); System.out.println(sol.evaluate(123)); // 123 System.out.println(sol.evaluate(-1)); // -1 System.out.println(sol.evaluate((add 1 2))); // 3 System.out.println(sol.evaluate((mult 3 (add 2 3)))); // 15 System.out.println(sol.evaluate((let x 2 (mult x 5)))); // 10 System.out.println(sol.evaluate((let x 2 x))); // 2 System.out.println(sol.evaluate((let x 2 (mult x (let x 3 y 4 (add x y)))))); // 14 System.out.println(sol.evaluate((let x 2 x 3 x))); // 3 System.out.println(sol.evaluate((let x 2 y x (add x y)))); // 4最后一个嵌套例子手算一下(let x 2 (mult x (let x 3 y 4 (add x y))))。外层 x2进入内层 letx3y4add 得到 7。内层结果为 7。外层 mult 用 x2 乘以 7得 14。如果环境隔离没做好外层 x 可能被内层覆盖成 3结果就变成 21。所以这个用例非常适合验证作用域管理。复杂度方面每个字符最多被扫描常数遍parseToken 会扫过 token 一次外层循环可能反复跳过空白但总扫描量仍是 O(n)n 是字符串长度。递归调用会创建 Maplet 嵌套时每一层都要拷贝一份父环境最坏情况下空间是 O(n * d)d 是嵌套深度。因为 d n最坏空间 O(n^2)。不过原题输入规模不大这种写法完全够用。面试时如果被追问可以说可以用链表式环境把拷贝代价降到 O(d)但实现复杂度会上升笔试阶段优先保证正确性。5. 实操中常见的坑与排查技巧5.1 let 遮蔽失效环境被污染这是我第一次写这题时犯的错误。我当时图省事直接在outerEnv上 put 变量没有复制。结果(let x 2 (let x 3 x))内层 put 后外层 x 变成 3最后返回 3 没错但如果你后面还要用到外层 x比如(let x 2 (let x 3 x) x)这个表达式在 Lisp 语义里应该返回外层 x2但污染后内层 x 覆盖了外层最后一个 x 会取 3整体变成 3。这类错误很难肉眼发现因为单看第一个用例结果碰巧是对的。解决方式就是环境隔离。每次 let 都新建一个HashMap(outerEnv)。注意新建之后后续绑定要不断更新的是这个新 map而不是反复 new。我在前面 2.2 里强调过“逐步可见”的规则核心就在这。5.2 越界与空指针索引没控制好解析字符串最容易出现的运行时错误就是StringIndexOutOfBoundsException。常见场景解析完一个操作数后直接读input.charAt(idx)没检查 idx 是否已经等于 length。遇到(add 1 2)的右括号时以为 idx 一定指向)但可能此时 idx 已经在空格上。空字符串或只有()的输入合法输入不会出现但防御代码仍然要小心。我的建议是所有读取字符的位置要么先 skipWhitespace要么先判idx input.length()。尤其parseToken里的 while 条件必须带idx input.length()否则变量名读到末尾会越界。另外解析完数字后 idx 可能正好停在右括号上下一轮递归入口 skipWhitespace 不会动但其实没问题。排查这类问题最简单的办法是打印 idx 和当前位置。我一般在每个分支入口加一行临时日志System.out.println(idx - input.charAt(idx));看到哪一步停错位置问题就定位了。面试现场不建议打日志但可以口头说明“我会先确认索引没有越过字符串末尾”。5.3 把 body 误当成变量绑定有不少人写 let 时喜欢先把所有 token 读到一个列表然后循环看是否达到 body。但变量绑定对的数量不定body 又可以是变量名容易误判。比如(let x y x)这个表达式的意思是绑定x ybody 也是x最后返回 x 的值。如果你用“遇到变量就认为是绑定”的逻辑会把它当成绑定 x然后绑定 y……很容易乱。所以我们用“绑定变量后面必然跟着一个值表达式body 后面必然跟着右括号”这个判据。这样一来x y x中先读 x但后面是 y 不是右括号所以这是一个绑定xy。继续读 x后面是右括号所以这是 body。逻辑就清晰了。这个规则我建议大家写注释记下来面试时讲出来会很加分。5.4 深递归与性能损耗递归深的时候栈上会累积很多evaluateExpr帧加上每层 let 都会复制一个 Map深嵌套可能让内存消耗变大。判题系统的输入不会让你爆栈但如果你在本地尝试构造(let x1 1 (let x2 2 (let x3 3 ...)))这种超深嵌套Java 默认栈大小大约在几百KB到1MB深度到几千层时可能 StackOverflow。处理方式有两个一是把递归改为显式栈 状态机代码会复杂很多但可以随意调节栈大小二是在递归方法里避免无意义的重复拷贝比如只对实际绑定过变量的 let 才复制环境。由于 OJ 一般不会卡这个点笔试阶段我更推荐先把递归写对。如果面试官追问性能你可以提出“用持久化环境结构/链表 Map”来把复制成本降下来这属于加分项。另外HashMap本身有常数开销如果你的环境变量数量很少也可以用单链表环境。但因为题面变量名不会太多HashMap 最稳不需要过度优化。叔叔我整理了一个常见问题速查表现象原因解决方案内层 let 修改外层变量直接复用外层 Map没做隔离每次 let 新建 HashMap 副本解析到字符串末尾越界读取字符前没判断 idx 边界parseToken 和 skipWhitespace 都加长度判断let 结果少算或多算一个表达式body 和绑定变量没区分开用“变量名后是否紧跟右括号”判据数字-1被当成变量失败只判断 isDigit没处理-数字判断同时检查-递归深度过大导致溢出深层嵌套let面试时说明可改为显式栈但笔试递归够用6. 如果面试官继续追问扩展与变体6.1 不用递归的行内迭代实现面试时聊到深处面试官可能问“能不能不递归写”这时你可以先把递归方案的思路讲清楚再简单说显式栈模拟需要保存两种状态——表达式求值状态和 let 绑定状态。一种常见做法是先把表达式 token 化再用一个栈保存操作码和中间结果遇到右括号弹出并归约。这样做能避免函数调用栈溢出但代码可读性会明显下降。具体实现这里不展开但我建议你至少能说出“递归是栈的天然映射”不至于被问懵。6.2 支持布尔表达式/自定义函数如果把add换成and、or把let换成lambda题目就从“计算器”变成了“解释器”。它们背后的思路完全一样递归下降 环境传递。自定义函数需要额外的函数表比如MapString, FunctionDef内部再管理参数绑定。环境不再是单纯的MapString, Integer而是MapString, ValueValue 可能是整数、布尔、闭包等。理解了 736 题你实际上已经掌握了写一个小型 Lisp 解释器的骨架。6.3 从解析到AST的转换还有一个常见变体不直接求值而是先解析成抽象语法树AST再对 AST 求值。这样做的好处是语法分析和执行逻辑可以解耦。比如定义 Node 接口整数节点、变量节点、加法节点、乘法节点、Let节点然后evaluate(env)递归求值。面试中如果时间充足我会优先写 AST 版本因为后续加语句、函数调用更加方便。不过 736 题只要求返回结果边解析边求值会更短。从 736 题往下走你会慢慢发现“解释器”并没有想象中神秘一段文本一个环境一组递归规则就能算出结果。这个模型在配置解析、模板引擎、规则引擎里都能找到影子。最后分享一个我自己的经验遇到这类字符串解析题先别急着写代码把语法规则列成一张小表再手写两个最小用例比如(let x 2 x)和(let x 2 x 3 x)然后照着表去模拟。只要把“什么时候是绑定、什么时候是 body”想清楚代码就是一层窗户纸。真写错了也别慌打几个断点看 idx 移动轨迹基本都能救回来。