企业官网建设流程全解析

第一次见到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是一个字符串，里面是以下几种东西自由组合：

变量名由小写字母组成，可能是多字母字符串。整数可以是负数。表达式里允许有空格，而且同一层可能出现多个连续空格。括号表达式都以(开头、)结尾，操作符之后至少有对应的运算对象。官方保证输入合法，不存在未定义变量的读取，所以你可以先不写非法输入处理，但实现里最好还是有点防御。

这道题在判题系统里的难度分级偏高。原因很简单：它不是背模板就能过的题。考的是你能否把一个带嵌套的文本“翻译”成计算过程，中间还牵扯到递归、索引移动、作用域快照。写出来容易，写对很难。

1.2 高难度背后的三个核心点

我刷过的题也不算少，但 736 题给我留下的印象特别深，因为它把三个容易出错的东西叠在了一起。

第一是字符串解析。表达式不是矩阵、不是数组，而是一段带括号的文本。你得自己决定怎么从文本里切出 token，怎么跳过空格，怎么判断一个(对应的)是谁。如果你过去习惯了用split处理输入，会发现这套玩法完全不是那么回事。

第二是递归结构。(add 1 (mult 2 3))这种嵌套，天然对应递归下降。看到(就递归进入子表达式，看到)就返回结果。如果你用循环加栈去模拟，不是不行，但是要把 token 产生式、栈内状态机都维护好，代码量会失控。面试里，大部分人的第一反应是递归。

第三是作用域管理。Lisp 的let有点像局部变量声明，但有个关键语义：每个 let 绑定只在自己的 body 内有效，而且新的绑定会影响后续绑定。例如(let x 2 x 3 x)的值是 3：第二个 x 绑定基于外层 x=2 算出 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))

这里绑定 x=2，然后绑定 y=x 时，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 分支可以这样组织：

1. 跳过(let后的空格。
2. 进入一个 while(true) 循环。
3. 跳过空白，检查当前字符。
4. 如果当前字符是)，说明可能遇到了空 body 之类的边界，一般合法输入不会走到这里；为了健壮可以返回当前记录的默认值或直接报错。
5. 如果当前字符是(、数字、-，直接把它当作 body 来处理，解析完整个表达式后返回其值。
6. 如果当前字符是字母，则读取变量名 token。
7. 读取变量名之后，跳空白。如果当前字符是)，那这个变量名就是 body，直接查环境返回它的值，并消费掉右括号。如果不是)，则解析一个值表达式，把这个变量和值放入 letEnv，继续循环处理下一对绑定。

这里的核心思想是：只有绑定列表在 body 之前，而且绑定列表一定是成对出现的。body 之前的所有 token 都可以归类为“变量名 + 绑定值表达式”。body 本身是整个 let 表达式最后一项。一旦遇到不能作为变量名的起始字符，就说明前面没有更多绑定了，当前就是 body。这个技巧在多个题解里都能见到，实测非常稳。

注意，读取变量名 token 时要小心：变量名继续读取直到遇到空格或右括号。如果遇到括号，比如变量名x后面直接是)，那就停住，让主循环看到右括号。不能在 parseToken 里把右括号吞掉，否则会出错。

3.3 add/mult 的二元求值

add 和 mult 比 let 简单得多，因为它们是固定二元运算。流程是：

1. 跳过(，读取操作符add或mult。
2. 跳空白。
3. 递归解析第一个子表达式。
4. 跳空白。
5. 递归解析第二个子表达式。
6. 跳空白，消费掉右括号。
7. 返回两个值的和或积。

这里有个容易忽略的点：操作符到底要不要读成 token？需要。因为(后面跟着的是字符串add，不是'a'一个字符。虽然这里没有addx这种混写，但严谨起见按 token 读取，然后equals判断。等读完操作符，再解析两个操作数。

加法和乘法都不需要新建作用域，使用当前环境继续往下递归即可。它们内部出现(let ...)时，由 let 自己创建子环境，外层变量仍然能访问到，这正好符合 Lisp 的语义。

3.4 变量查找与数字解析

变量查找：在 let 环境里，用Map<String, Integer> env.get(name)取值。合法输入保证变量必有定义，所以返回Integer不会为 null。如果你想让代码更稳，可以在 get 之后判空并抛一个带变量名的异常，方便调试。我在本地调试时就经常靠这个定位“哪个变量没绑定”。

数字解析：因为我们已经判断过当前 token 是数字或负数，可以直接用Integer.parseInt。但由于 token 可能是-123或者123，它正好止于空格或右括号，所以解析是安全的。更稳的做法是自己写一个 parseNumber：

private 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(Map<String, 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 Map<String, 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 body's 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 私有递归方法 evaluateExpr

evaluateExpr(Map<String, 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))))。外层 x=2，进入内层 let：x=3，y=4，add 得到 7。内层结果为 7。外层 mult 用 x=2 乘以 7，得 14。如果环境隔离没做好，外层 x 可能被内层覆盖成 3，结果就变成 21。所以这个用例非常适合验证作用域管理。

复杂度方面，每个字符最多被扫描常数遍：parseToken 会扫过 token 一次，外层循环可能反复跳过空白，但总扫描量仍是 O(n)，n 是字符串长度。递归调用会创建 Map，let 嵌套时每一层都要拷贝一份父环境，最坏情况下空间是 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 语义里应该返回外层 x=2，但污染后内层 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 = y，body 也是x，最后返回 x 的值。如果你用“遇到变量就认为是绑定”的逻辑，会把它当成：绑定 x=？然后绑定 y=？……很容易乱。

所以我们用“绑定变量后面必然跟着一个值表达式，body 后面必然跟着右括号”这个判据。这样一来，x y x中，先读 x，但后面是 y 不是右括号，所以这是一个绑定：x=y。继续读 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 最稳，不需要过度优化。

叔叔我整理了一个常见问题速查表：

6. 如果面试官继续追问：扩展与变体

6.1 不用递归的行内迭代实现

面试时聊到深处，面试官可能问“能不能不递归写？”这时你可以先把递归方案的思路讲清楚，再简单说：显式栈模拟需要保存两种状态——表达式求值状态和 let 绑定状态。一种常见做法是先把表达式 token 化，再用一个栈保存操作码和中间结果，遇到右括号弹出并归约。这样做能避免函数调用栈溢出，但代码可读性会明显下降。具体实现这里不展开，但我建议你至少能说出“递归是栈的天然映射”，不至于被问懵。

6.2 支持布尔表达式/自定义函数

如果把add换成and、or，把let换成lambda，题目就从“计算器”变成了“解释器”。它们背后的思路完全一样：递归下降 + 环境传递。自定义函数需要额外的函数表，比如Map<String, FunctionDef>，内部再管理参数绑定。环境不再是单纯的Map<String, Integer>，而是Map<String, Value>，Value 可能是整数、布尔、闭包等。理解了 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 移动轨迹，基本都能救回来。