LeetCode 736 题《Lisp 语法解析》要求实现一个函数 public int evaluate(String expression)，用于解析并计算类似 Lisp 的表达式。该表达式支持整数、变量、let（变量绑定）、add（加法）和 mult（乘法）操作，并具有嵌套作用域语义。

✅ 核心思路

使用 递归下降解析器 + 作用域栈：

• 用一个全局索引 index 从左到右遍历字符串。
• 用 Map> scope 来维护每个变量的值栈（模拟作用域）：
  • 每次进入 let 表达式时，将新值压入对应变量的栈；
  • 退出 let 时，弹出这些值，恢复外层作用域。

✅ 实现细节

1. 辅助函数

• parseVar(String exp)：从当前位置解析变量名（以小写字母开头，后接字母或数字）。
• parseInt(String exp)：解析整数（支持负号）。

2. 主递归函数 innerEvaluate

• 如果当前不是 ‘(’，说明是变量或整数，直接返回值。
• 如果是 ‘(’，判断是 let / add / mult：
  • let：循环读取 var expr 对，最后求值返回表达式。
  • add / mult：分别求两个子表达式的值，做加法或乘法。

✅ 完整 Java 代码（通过 LeetCode）

import java.util.*;

class Solution {
// 作用域：每个变量对应一个值栈（Deque）
private Map> scope = new HashMap();
// 当前解析位置
private int index = 0;

public int evaluate(String expression) {
    return innerEvaluate(expression);
}

private int innerEvaluate(String exp) {
    if (exp.charAt(index) != '(') {
        // 是整数或变量
        if (exp.charAt(index) == '-' || Character.isDigit(exp.charAt(index))) {
            return parseInt(exp);
        } else {
            String var = parseVar(exp);
            return scope.get(var).peek(); // 取当前作用域的值
        }
    }

    index++; // 跳过 '('
    char type = exp.charAt(index);
    int result = 0;

    if (type == 'l') { // let
        index += 4; // 跳过 "let "
        List assignedVars = new ArrayList();

        while (true) {
            if (!Character.isLowerCase(exp.charAt(index))) {
                // 最后一个表达式（不是变量名）
                result = innerEvaluate(exp);
                break;
            }

            String var = parseVar(exp);
            if (exp.charAt(index) == ')') {
                // 如 "(let x 2 x)"，最后一个 x 是返回值
                result = scope.get(var).peek();
                break;
            }

            assignedVars.add(var);
            index++; // 跳过空格
            int val = innerEvaluate(exp);
            scope.putIfAbsent(var, new ArrayDeque());
            scope.get(var).push(val);
            index++; // 跳过空格
        }

        // 退出 let 作用域：恢复变量旧值
        for (String var : assignedVars) {
            scope.get(var).pop();
        }

    } else if (type == 'a') { // add
        index += 4; // 跳过 "add "
        int e1 = innerEvaluate(exp);
        index++; // 跳过空格
        int e2 = innerEvaluate(exp);
        result = e1 + e2;

    } else if (type == 'm') { // mult
        index += 5; // 跳过 "mult "
        int e1 = innerEvaluate(exp);
        index++; // 跳过空格
        int e2 = innerEvaluate(exp);
        result = e1 * e2;
    }

    index++; // 跳过 ')'
    return result;
}

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

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

}

✅ 示例验证

“(let x 2 (mult x (let x 3 y 4 (add x y))))” → 14
“(let x 3 x 2 x)” → 2
“(let x 1 y 2 x (add x y) (add x y))” → 5

全部通过！

✅ 复杂度分析

• 时间复杂度：O(n)，每个字符最多被访问一次（递归+指针移动）。
• 空间复杂度：O(n)，递归栈深度 + 作用域栈存储。

如需进一步优化或转换为其他语言（如 Python/C++），也可以告诉我！