LeetCode 736. Lisp 语法解析
目录
题目描述
题意分析
给一个用类 Lisp 语法写成的表达式字符串，求它的整数值。表达式有三类形态：整数字面量（可带负号）、变量名（小写字母开头，后面可跟字母和数字），以及三种带括号的调用——
(add e1 e2)求两个子表达式之和，(mult e1 e2)求积，(let v1 e1 v2 e2 ... expr)依次把变量绑定到子表达式的值，最后返回expr的值。语法信号非常明确：表达式是自嵌套的——
add和mult的操作数本身可以是任意表达式，let的绑定值和返回体也可以是任意表达式。凡是「结构可以无限嵌套且用括号界定边界」的输入，一律要按照语法规则逐层展开来处理，而不是用一个扁平的栈去凑。第二个关键信号来自
let的语义细节。题面强调：绑定是顺序生效的，后面的表达式能看见前面刚绑定的变量（如(let x 2 y x z 3 x)中的y取到 $2$）；而且内层的同名变量会遮蔽外层，内层作用域一结束，外层的绑定必须原样恢复（如(let x 2 (let x 3 x) x)的答案是 $2$ 而不是 $3$）。这两条合起来说明：变量环境不是一张全局的表，而是一叠有生命周期的作用域，进入let时压入一层，离开时弹出一层，查找时从内向外逐层找。约束方面：表达式长度不超过 $2000$，保证语法合法、变量在使用前一定已被绑定、所有中间结果和最终结果都落在 $32$ 位有符号整数范围内。这些保证很重要——它们意味着不需要做错误处理、不需要判断未定义变量、也不用担心溢出，可以把全部精力放在语法结构的正确翻译上。
边界上要覆盖：单个数字或单个负数（如
"-12"）；let一个绑定都没有只有返回体（如(let x 5 x)是最小形式，但(let a1 3 b2 (add a1 1) b2)才体现顺序依赖）；let的返回体是一个数字而不是变量（如(let x 3 x 4 x)里最后的x是返回体，而不是新一轮绑定的变量名）；变量名含数字（如x2）；嵌套遮蔽。其中最难缠的是如何判断let参数列表里当前读到的 token 是「又一个绑定的变量名」还是「最后的返回体」，这是整道题的核心歧义点。
解法：递归下降解析
核心思路
先排除两条走不通的路。第一条是用正则或字符串切分预处理成 token 数组再处理——括号嵌套无法用正则匹配，切分之后还是要重建树结构，白做一遍。第二条是用单个显式栈做「遇到
)就归约」的经典计算器写法——它对add/mult尚可，但let的作用域需要在进入括号时就建立环境，而栈式归约只在离开括号时才动手，时机对不上，会让变量遮蔽极难实现。瓶颈在于：这道题的语法是递归定义的，而作用域的生命周期恰好与递归调用的生命周期重合。既然如此，最自然的做法就是让函数调用栈直接充当语法树——这就是递归下降。
于是设计一个带游标的解析器，把状态定死为三样东西：待解析的字符串
s、当前读到的位置idx、以及一叠作用域scopes（每层是一张变量名 -> 值的哈希表）。核心函数eval()的语义是：从idx开始读出一个完整的表达式，返回它的值，并把idx推进到这个表达式结束的下一个位置。这条语义就是整个解法的不变量。它有两个半边，缺一不可：「返回正确的值」和「游标恰好停在该表达式之后」。所有子函数（
parseAtom、parseToken、skipSpaces）都必须遵守同样的契约——只消费自己该消费的字符，一个不多一个不少。一旦某个分支多吃或少吃一个字符（尤其是右括号），后续解析全部错位，且错误往往在很远的地方才暴露出来，这是本题最难调试的部分。
eval()的分支结构由第一个非空格字符决定：不是'('就说明是原子（数字或变量），交给parseAtom；是'('就吃掉左括号，读出操作符 token，再分三路：
add/mult：连续调用两次eval()取两个操作数（递归天然处理了任意嵌套），跳过空格后吃掉配对的')'，返回和或积。let：先scopes.push(new HashMap<>())开一层新作用域，然后进入一个循环反复读取。
let循环里的歧义判断是关键。循环每轮先看当前字符：如果是')'，说明括号提前结束（在合法输入下不会走到，作为兜底返回 $0$）；如果是'('、'-'或数字，说明这一项不可能是变量名，只能是返回体表达式，于是求值、吃掉右括号、弹出作用域、返回该值；否则先用parseToken()读出一个标识符，再往后偷看一眼：若跳过空格后紧跟的是')'，说明这个标识符就是返回体（形如... x)），解析它的值后收尾返回；若不是')'，说明它是一个变量名，后面还跟着绑定值，于是eval()求出值并写进栈顶作用域，继续下一轮循环。「读一个 token 再偷看下一个字符」这一步就是消解「变量名 vs 返回体」歧义的全部手段——因为绑定总是成对出现，只有返回体是孤零零地贴着右括号的那一个。
变量查找
resolve从栈顶向栈底逐层找，第一个命中即返回，这就实现了内层遮蔽外层。作用域在返回前pop，恰好与let表达式的词法范围对齐，实现了「离开即恢复」。
解题步骤
把解析器封装成一个持有
s、idx、scopes的对象，而不是用一堆全局变量或到处传参。理由：递归下降的每个函数都要读写同一个游标，把它做成成员变量能让所有函数共享推进进度；如果用参数传递idx就必须同时返回「值」和「新位置」，签名会变得很难看。写
skipSpaces()，把idx推过所有连续空格。理由：题目允许 token 之间有空格，但空格本身没有语义；把跳过空格集中成一个函数，在每个「即将读取下一个语法单元」的位置调用一次，能避免在十几处手写while且漏掉某处。写
parseToken()：从当前位置读到遇见空格或')'为止，返回中间的子串。理由：token 的终止符只有这两个（左括号只会出现在 token 之前），把边界条件收敛成一处，操作符名和变量名就能共用同一个读取函数。写
parseAtom()：跳空格后看首字符，若是'-'或数字则按符号加逐位累加解析出整数；否则读一个 token 当作变量名，交给resolve查值。理由：负号只可能出现在数字最前面（题目没有一元减运算），所以「首字符是-」是判定数字的充分条件之一；逐位累加而不是Integer.parseInt是为了让游标推进和解析同步完成，符合前面定下的契约。
eval()先跳空格，看首字符是否为'('：不是就直接返回parseAtom()。理由：这是递归出口，把「原子表达式」这一最简形态单独剥离，后面就只需处理括号形态。是
'('时先idx++吃掉左括号，跳空格后parseToken()读出操作符。理由：三种操作符长度不同（add、mult、let），用 token 读取而不是固定长度截取才安全。
add分支：int a = eval(); int b = eval();然后跳空格、idx++吃掉右括号，返回a + b。理由：两次eval()的调用顺序保证了游标按左到右推进；结尾必须显式吃掉自己这一层的右括号，否则外层看到的将是多余的)。mult分支同理，只把加号换成乘号。
let分支先压入一个空作用域，再进入循环。理由：必须在解析任何绑定值之前就建好新层，否则第一个绑定会写进外层作用域，污染上层环境。循环内先跳空格取当前字符
c：若c是'('、'-'或数字，说明是返回体，求值后吃右括号、弹作用域、返回。理由：变量名必须以小写字母开头，所以这三类首字符能百分之百排除「变量名」的可能，判定是确定性的而非启发式的。否则
parseToken()读出标识符后跳空格，检查下一个字符是不是')'：是则该标识符是返回体，resolve取值后吃右括号、弹作用域、返回；不是则它是变量名，调用eval()求出绑定值并写入栈顶作用域，进入下一轮。理由：这是消解歧义的唯一手段，「后面还有东西」等价于「这是个待绑定的变量」。写入栈顶而非某个固定层，保证了顺序绑定对后续表达式立刻可见。
resolve(var)从栈顶向栈底遍历，命中即返回。理由：内层作用域在栈顶，先查内层就自动实现了遮蔽；Java 的ArrayDeque配合push时迭代顺序正好是从头（最新压入）到尾，天然满足要求，Go 里则要显式用下标从len-1递减。以
expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"走一遍。eval见'('，吃掉后读到let，压入作用域 $S_1$。循环第一轮：字符是x，是字母，parseToken读出"x"，偷看下一个非空格字符是2不是')'，所以x是变量名；eval()解析出 $2$，写入 $S_1$，此时 $S_1 = {x: 2}$。第二轮：字符是'('，命中「返回体」分支，调用eval()。这个内层eval读到mult，两次递归求操作数：第一次eval()读到变量x，resolve在 $S_1$ 找到 $2$；第二次eval()见'('读到let，压入 $S_2$，循环第一轮读"x"后偷看是3，绑定 $x = 3$ 到 $S_2$（遮蔽了 $S_1$ 的 $x$），第二轮读"y"后偷看是4，绑定 $y = 4$，第三轮字符是'('走返回体分支，eval()求(add x y)：resolve("x")从栈顶 $S_2$ 找到 $3$（不是 $S_1$ 的 $2$），resolve("y")找到 $4$，和为 $7$；随后吃掉let的右括号、弹出 $S_2$，返回 $7$。回到mult，两个操作数是 $2$ 和 $7$，吃掉右括号返回 $14$。回到最外层let的返回体分支，吃掉右括号、弹出 $S_1$，返回 $14$。最终答案 $14$——过程中 $S_2$ 的弹出使得x的遮蔽在内层结束时准确失效。
代码实现
class Solution {
public int evaluate(String expression) {
Parser parser = new Parser(expression);
return parser.eval();
}
private static class Parser {
private final String s;
private int idx;
private final Deque<Map<String, Integer>> scopes = new ArrayDeque<>();
Parser(String s) {
this.s = s;
this.idx = 0;
}
int eval() {
skipSpaces();
char ch = s.charAt(idx);
if (ch == '(') {
idx++;
skipSpaces();
String op = parseToken();
if (op.equals("add")) {
int a = eval();
int b = eval();
skipSpaces();
idx++;
return a + b;
}
if (op.equals("mult")) {
int a = eval();
int b = eval();
skipSpaces();
idx++;
return a * b;
}
scopes.push(new HashMap<>());
while (true) {
skipSpaces();
char c = s.charAt(idx);
if (c == ')') {
idx++;
scopes.pop();
return 0;
}
if (c == '(' || c == '-' || Character.isDigit(c)) {
int val = eval();
skipSpaces();
idx++;
scopes.pop();
return val;
}
String var = parseToken();
skipSpaces();
if (s.charAt(idx) == ')') {
int val = resolve(var);
idx++;
scopes.pop();
return val;
}
int val = eval();
scopes.peek().put(var, val);
}
}
return parseAtom();
}
private int parseAtom() {
skipSpaces();
char ch = s.charAt(idx);
if (ch == '-' || Character.isDigit(ch)) {
int sign = 1;
if (ch == '-') {
sign = -1;
idx++;
}
int num = 0;
while (idx < s.length() && Character.isDigit(s.charAt(idx))) {
num = num * 10 + (s.charAt(idx) - '0');
idx++;
}
return sign * num;
}
String var = parseToken();
return resolve(var);
}
private int resolve(String var) {
for (Map<String, Integer> scope : scopes) {
if (scope.containsKey(var)) {
return scope.get(var);
}
}
return 0;
}
private String parseToken() {
int start = idx;
while (idx < s.length()) {
char ch = s.charAt(idx);
if (ch == ' ' || ch == ')') {
break;
}
idx++;
}
return s.substring(start, idx);
}
private void skipSpaces() {
while (idx < s.length() && s.charAt(idx) == ' ') {
idx++;
}
}
}
}
type Parser struct {
s string
idx int
scopes []map[string]int
}
func evaluate(expression string) int {
p := &Parser{s: expression, idx: 0}
return p.eval()
}
func (p *Parser) eval() int {
p.skipSpaces()
ch := p.s[p.idx]
if ch == '(' {
p.idx++
p.skipSpaces()
op := p.parseToken()
if op == "add" {
a := p.eval()
b := p.eval()
p.skipSpaces()
p.idx++
return a + b
}
if op == "mult" {
a := p.eval()
b := p.eval()
p.skipSpaces()
p.idx++
return a * b
}
p.scopes = append(p.scopes, map[string]int{})
for {
p.skipSpaces()
c := p.s[p.idx]
if c == ')' {
p.idx++
p.scopes = p.scopes[:len(p.scopes)-1]
return 0
}
if c == '(' || c == '-' || (c >= '0' && c <= '9') {
val := p.eval()
p.skipSpaces()
p.idx++
p.scopes = p.scopes[:len(p.scopes)-1]
return val
}
varName := p.parseToken()
p.skipSpaces()
if p.s[p.idx] == ')' {
val := p.resolve(varName)
p.idx++
p.scopes = p.scopes[:len(p.scopes)-1]
return val
}
val := p.eval()
p.scopes[len(p.scopes)-1][varName] = val
}
}
return p.parseAtom()
}
func (p *Parser) parseAtom() int {
p.skipSpaces()
ch := p.s[p.idx]
if ch == '-' || (ch >= '0' && ch <= '9') {
sign := 1
if ch == '-' {
sign = -1
p.idx++
}
num := 0
for p.idx < len(p.s) {
c := p.s[p.idx]
if c < '0' || c > '9' {
break
}
num = num*10 + int(c-'0')
p.idx++
}
return sign * num
}
varName := p.parseToken()
return p.resolve(varName)
}
func (p *Parser) resolve(name string) int {
for i := len(p.scopes) - 1; i >= 0; i-- {
if val, ok := p.scopes[i][name]; ok {
return val
}
}
return 0
}
func (p *Parser) parseToken() string {
start := p.idx
for p.idx < len(p.s) {
ch := p.s[p.idx]
if ch == ' ' || ch == ')' {
break
}
p.idx++
}
return p.s[start:p.idx]
}
func (p *Parser) skipSpaces() {
for p.idx < len(p.s) && p.s[p.idx] == ' ' {
p.idx++
}
}
复杂度分析
- 时间复杂度：$O(n \cdot d)$，其中 $n$ 是表达式长度、$d$ 是
let的最大嵌套深度。游标idx只单调前进从不回退，因此字符扫描总量是 $O(n)$；额外开销来自resolve，每次查变量最坏要沿作用域栈走 $d$ 层，而变量引用次数不超过 $O(n)$。由于 $n \le 2000$ 且嵌套深度受括号数限制，实际运算量很小。- 空间复杂度：$O(n)$。递归深度与表达式的括号嵌套深度同阶，最坏是 $O(n)$；作用域栈的层数等于
let嵌套深度，所有层中存储的变量总数也不超过表达式中出现的绑定次数，同样是 $O(n)$；解析过程本身不复制字符串，只做子串截取。
关键点总结
- 面对递归定义的语法，递归下降几乎总是最优选择：让函数调用栈充当语法树，语法规则一条对应一个分支，代码结构和文法定义一一对应，可读性远超手工维护的显式栈。判断标准是「输入是否可以无限嵌套」，一旦是，就不要试图用扁平的栈去凑。
- 递归下降的生命线是游标契约：每个解析函数「只消费自己那一段，返回时游标停在段尾之后」。写代码时逐个函数确认这条契约，比写完之后调试要高效一个量级——因为游标错位的症状会在很远处才显现，几乎无法通过打断点定位。
- 变量作用域天然对应「进入时压栈、离开时弹栈」的结构，而在递归下降里这个时机与函数的进入/返回完全重合，所以直接把
push放在分支开头、pop放在每个return之前即可。查找从栈顶向栈底走就实现了遮蔽语义，无需任何额外机制。- 语法歧义要靠前瞻消解，而不是靠猜。本题「变量名 vs 返回体」的区分手段是「读完 token 后偷看下一个非空格字符是否为右括号」，这是一个确定性的 LL(1) 判断；用「计数绑定对数的奇偶」之类的间接推断则会在嵌套时失效。
- 首字符能提供强判定信息时要充分利用。本题里
'('、'-'和数字三者都不可能是变量名的开头，所以看一眼就能立刻走返回体分支，省掉一次 token 读取和回退。- 面试视角：字节考这题主要看能否把非平凡文法翻译成结构清晰的代码，而不是看你能不能想出巧思。答题的正确姿势是先在白板上把文法写出来（
expr := int | var | (add expr expr) | (mult expr expr) | (let (var expr)* expr)），指着它说明每条产生式对应哪个分支，再写代码。写之前主动声明游标契约，写完主动举(let x 2 (let x 3 x) x)这个遮蔽用例验证作用域弹出，能极大提升说服力。若被追问「怎么支持更多操作符」，回答是把分支表改成Map<String, 处理函数>即可扩展，不影响主框架。
易错点总结
- 错误写法：
add/mult分支求完两个操作数后忘记吃掉自己的右括号（漏掉idx++）→ 用例"(add 1 2)"→ 外层解析器随后读到多余的')'，在嵌套场景如"(mult (add 1 2) 3)"中会把)当成 token 起点，解析彻底错位。- 错误写法：
let分支的pop只写在其中一个返回路径上 → 用例"(let x 2 (let x 3 x) x)"→ 内层let通过「首字符是(」路径返回时若漏了pop，外层再查x会先命中残留的内层作用域返回 $3$，正确答案是 $2$。- 错误写法：用一张全局哈希表代替作用域栈，
let结束时不恢复 → 用例"(let x 2 (let x 3 x) x)"→ 内层把x改成 $3$ 之后再没改回来，最终返回 $3$，正确答案是 $2$。- 错误写法：
resolve从作用域栈底向栈顶查找（Java 里误用descendingIterator，或 Go 里下标从 $0$ 递增）→ 用例"(let x 2 (let x 3 x))"→ 先命中外层的 $2$，返回 $2$，正确答案是 $3$，遮蔽方向完全反了。- 错误写法：把
let的绑定值写进栈底或某个固定作用域而不是栈顶 → 用例"(let x 2 (let y 3 (add x y)))"→ 内层的y被写到外层，虽然本例侥幸能算对，但换成"(let x 1 (let x 2 x) x)"时内层绑定污染外层，最终返回 $2$ 而非 $1$。- 错误写法：判断「返回体」时只检查首字符是不是
'('，忘记数字和负号 → 用例"(let x 2 5)"→ 读到5时把它当成变量名，parseToken读出"5"后偷看是')'，走resolve("5")返回默认值 $0$，正确答案是 $5$。- 错误写法：读 token 的终止条件只判空格不判
')'→ 用例"(let x 2 x)"→ 最后的x)被整体读成 token"x)"，resolve查不到返回 $0$，且游标已经越过右括号导致后续全乱。- 错误写法：解析数字时不处理前导负号，或把
'-'当成减法运算符 → 用例"(add 1 -2)"→ 要么解析出 $2$ 得到答案 $3$，要么试图找第三个操作数而崩溃，正确答案是 $-1$。- 错误写法：用
Integer.parseInt(s.substring(start, end))解析数字却没有同步推进idx→ 用例"(add 12 3)"→ 游标仍停在1上，下一次读取重复消费同一段字符，陷入死循环或读出错误的 token。- 错误写法：
let循环里读完变量名后不跳空格就检查下一个字符是否为')'→ 用例"(let x 2 x )"（右括号前有空格）→ 检查到的是空格不是')'，误判x为变量名并调用eval()去读)，解析崩溃。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1106. 解析布尔表达式 | 困难 | 同为括号嵌套的递归下降，但操作数个数可变且没有变量作用域 |
| 772. 基本计算器 III | 困难 | 中缀表达式带运算符优先级，需在递归下降中分层处理加减与乘除 |
| 394. 字符串解码 | 中等 | 嵌套结构更简单，可用显式栈归约，是理解「递归 vs 栈」两种写法的入门对照 |
| 726. 原子的数量 | 困难 | 括号带乘数因子，返回的是计数表而非单值，考察递归返回复合结果的合并 |
| 385. 迷你语法分析器 | 中等 | 解析嵌套列表并构造对象树，重点在游标推进与容器构造的配合 |