LeetCode 736. Lisp 语法解析

2025-05-13 HGNULB 约 11 分钟

文章信息 7 个分类 4 个标签

分类

LeetCode CodeTop 困难未解决 2-5 字节拼多多

题目描述

✅ 736. Lisp 语法解析

题意分析

表达式可以是整数、已绑定变量，或以 add、mult、let 开头的括号表达式。add 和 mult 各计算两个子表达式；let 先依次执行若干次变量绑定，再返回最后一个表达式的值。

let 的绑定按从左到右的顺序立即生效，同一层可以重新绑定同名变量。内层变量会遮蔽外层同名变量，但退出内层后，外层原有绑定必须恢复。题目保证语法和变量引用合法，无需处理非法表达式。

解法：递归下降解析

核心思路

[!blue]

用递归函数 eval() 对应语法中的“一个表达式”，共享游标 idx 指向尚未消费的位置。函数进入时跳过空格，返回时不仅交出计算值，还要把游标移动到整个表达式之后。这样外层可以接着解析下一个部分，不必切分字符串或重新寻找匹配括号。

当前字符不是左括号时，它是一个原子：数字按位累积并处理负号，变量名则读取完整单词，再从最内层作用域向外查找，使用第一次找到的绑定。每个 let 对应一张独立哈希表；Java 把最新作用域放在栈顶，Go 从作用域切片末尾向前查找。

遇到左括号后，先读取操作符。add、mult 都递归调用两次 eval()，得到两个完整子表达式的值，再消费自己的右括号并计算结果。它们不引入新变量，因此不必另建作用域，直接沿用当前可见的绑定。

处理 let 时先压入空作用域，再按顺序读取内容。若下一项以左括号、数字或负号开头，它不可能是变量名，只能是最终返回表达式。若以字母开头，先读出变量名并跳过空格：后面是右括号时，该变量就是最终表达式；否则它是待绑定变量，后面还有一个完整表达式作为它的值。

绑定时必须先求右侧表达式，再把结果写入本层表。这样右侧仍能读取该变量此前的绑定，而写入后的新值又能立即被后面的绑定或最终表达式使用。嵌套 let 求值时会暂时压入更内层的表，结束后弹出，不会改写当前层的绑定。

最终表达式求值完成后，当前 let 消费自己的右括号并弹出本层作用域，再把结果交回父表达式。由此，每次递归都同时满足“游标越过一个完整表达式”和“临时作用域已恢复”两个约定，嵌套再深也不会把括号或变量状态留给错误的层。

解题步骤

读取操作符，add 与 mult 顺序求两个操作数。

let 进入时压作用域，按顺序处理绑定。

数字或括号可直接作为最后表达式，变量用后续右括号区分。

每层消费自己的右括号并恢复作用域。

单独的整数也可以作为整个输入，直接由原子解析返回。变量名以小写字母开头，后续可以含数字，因此不能只读取一个字符；负号则属于整数。题目保证最终答案及运算中间结果在 32 位整数范围内，代码使用 int 保存表达式的值。

代码实现

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;
                }

                // 进入当前 let 的独立作用域，绑定只写到这一层
                scopes.push(new HashMap<>());

                while (true) {
                    skipSpaces();
                    char c = s.charAt(idx);

                    if (c == ')') {
                        idx++;
                        // 本层 let 求值结束，撤销本层绑定以恢复外部作用域
                        scopes.pop();

                        return 0;
                    }

                    if (c == '(' || c == '-' || Character.isDigit(c)) {
                        int val = eval();

                        skipSpaces();
                        idx++;
                        // 本层 let 求值结束，撤销本层绑定以恢复外部作用域
                        scopes.pop();

                        return val;
                    }

                    String var = parseToken();

                    skipSpaces();

                    // 标识符后直接闭合时，它是最终返回值而非待绑定变量
                    if (s.charAt(idx) == ')') {
                        int val = resolve(var);

                        idx++;
                        // 本层 let 求值结束，撤销本层绑定以恢复外部作用域
                        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
        }

        // 进入当前 let 的独立作用域，绑定只写到这一层
        p.scopes = append(p.scopes, map[string]int{})
        for {
            p.skipSpaces()
            c := p.s[p.idx]
            if c == ')' {
                p.idx++
                // 本层 let 求值结束，撤销本层绑定以恢复外部作用域
                p.scopes = p.scopes[:len(p.scopes)-1]
                return 0
            }

            if c == '(' || c == '-' || (c >= '0' && c <= '9') {
                val := p.eval()
                p.skipSpaces()
                p.idx++
                // 本层 let 求值结束，撤销本层绑定以恢复外部作用域
                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++
                // 本层 let 求值结束，撤销本层绑定以恢复外部作用域
                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(D+1))$ 估算，N 为长度、D 为最大作用域层数。

空间复杂度：$O(N)$，活动作用域、变量名与递归状态总量受输入长度约束。

关键点总结

[!green]

先计算绑定值，再写入新值，后续绑定立即可见。

解析结果和游标停留位置都属于函数契约。

易错点总结

[!yellow]

作用域退出不弹出，会让内层变量污染外层。

从外向内查找，会忽略合法遮蔽。

子表达式多消费一个右括号，会使后续语法错位。

相似题目

题目	难度	关联与区别
224. 基本计算器	困难	同样解析嵌套表达式，本题还需支持变量绑定和局部作用域，不能只处理括号数值。
726. 原子的数量	困难	同样使用每层独立状态并在退出时恢复外层，本题保存变量环境，原题保存原子计数。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/79643494

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！