Lisp表达式解析：如何处理嵌套let作用域？LeetCode 736面试题详解

刚来实习一个月，就把 leader 看成心动嘉宾了，这剧情是不是有点太熟悉了？办公室恋情八字还没一撇，你连“她没男朋友”都脑补完了，HR 要是知道都得扶额。

这种事情最让人纠结的，其实不是加不加微信，而是你这边正上头，对方可能只把你当成一个普通实习生。在群里聊工作一切自然，一旦你单独去加，又找不到什么正当理由，气氛确实容易变得尴尬。我看评论区的建议就挺实在：别轻易把欣赏误会成对方也有意思；也有人劝，先混熟再说，别一上来就“开冲”。

我的看法是，现阶段最好别冲动。你才来一个月，连她对你有没有额外印象都不确定。不如先把工作干明白，多找机会自然接触，感受一下线下真实的相处状态。如果真有互动，以后再找个工作需要为由加好友，也不会显得突兀。实习期最宝贵的可不是“恋爱脑”，而是别让自己在多年以后回想起来，尴尬到脚趾抠地。

面试题：Lisp 语法解析

一看到 "(let x 2 (mult x (let x 3 y 4 (add x y))))" 这种题，很多人的第一反应就是递归。递归的思路没错，但真动笔写起来，最容易在两个地方栽跟头：一个是作用域的处理，另一个是字符串指针的推进。尤其是 let 表达式，变量绑定可不是全局替换，它是带作用域的，内层的同名变量可以覆盖外层的，这种特性让我从一开始就不太相信“简单 split 一下就能搞定”的写法。

这道题的本质并不是做四则运算，而是需要你边扫描字符串、边构建作用域、边进行求值。我们来看这个例子：

(let x 2
  (mult x
    (let x 3 y 4
      (add x y))))

外层 x 绑定为 2，但内层 let 又定义了一个 x=3，所以 add x y 使用的是内层变量，结果是 7，然后再乘以外层的 x=2，最终得到 14。如果你把整个解析过程中的变量表只维护成一个简单的 Map<String,Integer>，很快就会把结果算错。

我一般的处理思路是：递归地解析表达式，每进入一层括号，就复制一份当前的作用域环境。虽然空间上有些开销，但代码逻辑清晰，在面试场景下足够稳健。

先看核心入口，我们用一个下标 idx 来遍历字符串：

class Solution {
    private int idx = 0;

    public int evaluate(String expression) {
        return parse(expression, new HashMap<>());
    }

parse 方法是主力。如果当前字符不是左括号，说明遇到了数字或变量，直接取值：

    private int parse(String s, Map<String, Integer> scope) {
        if (s.charAt(idx) != '(') {
            if (s.charAt(idx) == '-' || Character.isDigit(s.charAt(idx))) {
                return parseInt(s);
            }
            return scope.get(parseVar(s));
        }

如果遇到左括号，则意味着是一个表达式（add、mult 或 let）。我们需要先跳过 (，然后读取操作符：

        idx++; // 跳过 '('
        String op = parseToken(s);
        idx++; // 跳过空格

add 和 mult 的处理相对简单，递归解析两个操作数，计算后跳过右括号即可：

        if ("add".equals(op)) {
            int a = parse(s, new HashMap<>(scope));
            idx++;
            int b = parse(s, new HashMap<>(scope));
            idx++;
            return a + b;
        }

        if ("mult".equals(op)) {
            int a = parse(s, new HashMap<>(scope));
            idx++;
            int b = parse(s, new HashMap<>(scope));
            idx++;
            return a * b;
        }

真正容易让人绕进去的是 let。它的结构不是固定的两个参数，而是一系列“变量名-表达式”对，最后跟一个结果表达式。所以这里不能写死，必须边读边判断：

        // 处理 let 表达式
        Map<String, Integer> local = new HashMap<>(scope);
        while (true) {
            // 如果下一个 token 是表达式（括号或数字），说明它是 let 的最终结果表达式
            if (s.charAt(idx) == '(' || s.charAt(idx) == '-' || Character.isDigit(s.charAt(idx))) {
                int ans = parse(s, local);
                idx++; // 跳过这个表达式后的空格或‘)’
                return ans;
            }

            // 否则，读取一个变量名
            String name = parseVar(s);
            // 如果紧跟的是‘)’，说明这个变量名就是结果（返回它的值）
            if (s.charAt(idx) == ')') {
                return local.get(name);
            }
            idx++; // 跳过空格，准备读取该变量的值

            // 读取变量的值并绑定到局部作用域
            int val = parse(s, local);
            local.put(name, val);

            // 如果赋值后遇到‘)’，说明这个值就是整个let的结果（特殊情况）
            if (s.charAt(idx) == ')') {
                return val;
            }
            idx++; // 跳过空格，准备读取下一个变量名或结果表达式
        }
    }

最后，补上解析整数和变量名的小工具方法，整个算法就能跑通了：

    private int parseInt(String s) {
        int sign = 1, num = 0;
        if (s.charAt(idx) == '-') { sign = -1; idx++; }
        while (idx < s.length() && Character.isDigit(s.charAt(idx))) {
            num = num * 10 + s.charAt(idx++) - '0';
        }
        return sign * num;
    }

    private String parseVar(String s) {
        int start = idx;
        while (idx < s.length() && s.charAt(idx) != ' ' && s.charAt(idx) != ')') {
            idx++;
        }
        return s.substring(start, idx);
    }

    private String parseToken(String s) {
        return parseVar(s);
    }
}

这题代码量不大，但非常考验细节。尤其要记住两点：第一，let 的作用域必须分层，新作用域要继承并隔离外层，别偷懒共用一张表。第二，下标 idx 每次跳过空格或右括号时，位置必须非常精确，多移一下或少移一下，整个解析链就全乱了。

写完这种题，千万别急着提交。用几组嵌套很深的 let 表达式多测试几次，比对着代码空想十分钟要靠谱得多。说到底，无论是在Java里解析表达式，还是在职场中处理人际关系，清晰的边界感和对细节的掌控，往往才是破局的关键。如果你在准备面试时遇到过其他有趣的题目，欢迎来云栈社区和大家一起聊聊。