736. 解析 Lisp 表达式

Hard

题目描述

给你一个类似 Lisp 语法的字符串表达式 expression，求出其计算结果。

表达式语法如下所示：

表达式可以为整数、let 表达式、add 表达式、mult 表达式，或变量。表达式的结果为整数。
整数可以是正整数、负整数、0。
let 表达式采用 "(let v1 e1 v2 e2 ... vn en expr)" 的形式，其中 let 始终是字符串 "let"，接下来会有若干对按序出现的变量和表达式，也就是说，第一个变量 v1 被赋值为表达式 e1 的结果，第二个变量 v2 被赋值为表达式 e2 的结果，依次类推；最终 let 表达式的结果为 expr 表达式的结果。
add 表达式表示为 "(add e1 e2)" ，其中 add 始终为字符串 "add"，该表达式总是包含两个表达式 e1、e2 ，结果为 e1 表达式的结果与 e2 表达式的结果之和。
mult 表达式表示为 "(mult e1 e2)" ，其中 mult 始终为字符串 "mult"，该表达式总是包含两个表达式 e1、e2，结果为 e1 表达式的结果与 e2 表达式的结果之积。
在题目的所有测试用例中，变量名以小写字符开始，之后跟随 0 个或多个小写字符或数字。此外，为了便于解析，"add"、"let"、"mult" 会被保护，不会用作变量名。
最后，要说一下作用域的概念。计算变量名所对应的表达式时，在计算上下文中，首先检查最内层作用域（括号内），然后按顺序依次检查外层作用域。测试用例中每一个表达式都是合法的。请参阅示例进行更深入的理解。

示例 1：

输入：expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
输出：14
解释：计算表达式 (add x y), 在检查变量 x 值时，
在变量的上下文中由最内层作用域依次向外层检查。
首先找到 x = 3, 所以此处的 x 值是 3。

示例 2：

输入：expression = "(let x 3 x 2 x)"
输出：2
解释：let 语句中的赋值运算按顺序处理即可。

示例 3：

输入：expression = "(let x 1 y 2 x (add x y) (add x y))"
输出：5
解释：第一个 (add x y) 计算结果是 3，并赋值给了 x。
第二个 (add x y) 计算结果是 3+2 = 5。

提示：

1 <= expression.length <= 2000
expression 中不含前导和尾随空格
expression 中的所有 token 之间用单个空格分隔
答案及所有中间计算结果都符合 32 位整数范围
题目的表达式均为合法的且最终结果为整数

解题思路

这是一个典型的表达式解析和计算问题，需要处理嵌套结构和变量作用域。

核心思路：

递归解析：表达式具有递归嵌套的结构，使用递归函数来解析和计算
作用域管理：使用栈或映射来管理变量的作用域，内层作用域会覆盖外层的同名变量
Token 解析：需要正确分割和解析表达式中的各个 token（操作符、变量、子表达式）

解题步骤：

如果表达式以数字或负号开头，直接解析为整数
如果以字母开头，说明是变量，从当前作用域查找其值
如果以括号开头，需要解析操作类型（let/add/mult）并递归处理子表达式
对于 let 表达式，需要创建新的作用域，依次处理变量赋值，最后计算最终表达式
对于 add/mult 表达式，递归计算两个操作数并返回结果

关键点：

正确解析嵌套的括号结构
维护变量作用域的层级关系
处理 let 表达式中的顺序赋值

推荐使用递归 + 作用域栈的方法，代码结构清晰，易于理解和实现。

代码实现

class Solution {
public:
    unordered_map<string, int> scope;
    
    int evaluate(string expression) {
        return eval(expression);
    }
    
private:
    int eval(string expr) {
        if (expr[0] != '(') {
            // 数字或变量
            if (isdigit(expr[0]) || expr[0] == '-') {
                return stoi(expr);
            } else {
                return scope[expr];
            }
        }
        
        // 解析表达式
        vector<string> tokens = parse(expr);
        string op = tokens[0];
        
        if (op == "add") {
            return eval(tokens[1]) + eval(tokens[2]);
        } else if (op == "mult") {
            return eval(tokens[1]) * eval(tokens[2]);
        } else { // let
            // 保存当前作用域
            unordered_map<string, int> backup;
            for (int i = 1; i < tokens.size() - 1; i += 2) {
                if (scope.count(tokens[i])) {
                    backup[tokens[i]] = scope[tokens[i]];
                }
                scope[tokens[i]] = eval(tokens[i + 1]);
            }
            
            int result = eval(tokens.back());
            
            // 恢复作用域
            for (int i = 1; i < tokens.size() - 1; i += 2) {
                if (backup.count(tokens[i])) {
                    scope[tokens[i]] = backup[tokens[i]];
                } else {
                    scope.erase(tokens[i]);
                }
            }
            
            return result;
        }
    }
    
    vector<string> parse(string expr) {
        vector<string> tokens;
        int i = 1; // 跳过左括号
        
        while (i < expr.length() - 1) {
            if (expr[i] == ' ') {
                i++;
                continue;
            }
            
            if (expr[i] == '(') {
                int count = 1, start = i;
                i++;
                while (count > 0) {
                    if (expr[i] == '(') count++;
                    else if (expr[i] == ')') count--;
                    i++;
                }
                tokens.push_back(expr.substr(start, i - start));
            } else {
                int start = i;
                while (i < expr.length() && expr[i] != ' ' && expr[i] != ')') {
                    i++;
                }
                tokens.push_back(expr.substr(start, i - start));
            }
        }
        
        return tokens;
    }
};

class Solution:
    def evaluate(self, expression: str) -> int:
        self.scope = {}
        return self.eval(expression)
    
    def eval(self, expr):
        if expr[0] != '(':
            # 数字或变量
            if expr[0].isdigit() or expr[0] == '-':
                return int(expr)
            else:
                return self.scope[expr]
        
        # 解析表达式
        tokens = self.parse(expr)
        op = tokens[0]
        
        if op == 'add':
            return self.eval(tokens[1]) + self.eval(tokens[2])
        elif op == 'mult':
            return self.eval(tokens[1]) * self.eval(tokens[2])
        else:  # let
            # 保存当前作用域
            backup = {}
            for i in range(1, len(tokens) - 1, 2):
                if tokens[i] in self.scope:
                    backup[tokens[i]] = self.scope[tokens[i]]
                self.scope[tokens[i]] = self.eval(tokens[i + 1])
            
            result = self.eval(tokens[-1])
            
            # 恢复作用域
            for i in range(1, len(tokens) - 1, 2):
                if tokens[i] in backup:
                    self.scope[tokens[i]] = backup[tokens[i]]
                else:
                    del self.scope[tokens[i]]
            
            return result
    
    def parse(self, expr):
        tokens = []
        i = 1  # 跳过左括号
        
        while i < len(expr) - 1:
            if expr[i] == ' ':
                i += 1
                continue
            
            if expr[i] == '(':
                count = 1
                start = i
                i += 1
                while count > 0:
                    if expr[i] == '(':
                        count += 1
                    elif expr[i] == ')':
                        count -= 1
                    i += 1
                tokens.append(expr[start:i])
            else:
                start = i
                while i < len(expr) and expr[i] != ' ' and expr[i] != ')':
                    i += 1
                tokens.append(expr[start:i])
        
        return tokens

public class Solution {
    private Dictionary<string, int> scope = new Dictionary<string, int>();
    
    public int Evaluate(string expression) {
        return EvaluateExpression(expression);
    }
    
    private int EvaluateExpression(string expr) {
        if (expr[0] != '(') {
            // 数字或变量
            if (char.IsDigit(expr[0]) || expr[0] == '-') {
                return int.Parse(expr);
            } else {
                return scope[expr];
            }
        }
        
        // 解析表达式
        List<string> tokens = Parse(expr);
        string op = tokens[0];
        
        if (op == "add") {
            return EvaluateExpression(tokens[1]) + EvaluateExpression(tokens[2]);
        } else if (op == "mult") {
            return EvaluateExpression(tokens[1]) * EvaluateExpression(tokens[2]);
        } else { // let
            // 保存当前作用域
            Dictionary<string, int> backup = new Dictionary<string, int>();
            for (int i = 1; i < tokens.Count - 1; i += 2) {
                if (scope.ContainsKey(tokens[i])) {
                    backup[tokens[i]] = scope[tokens[i]];
                }
                scope[tokens[i]] = EvaluateExpression(tokens[i + 1]);
            }
            
            int result = EvaluateExpression(tokens[tokens.Count - 1]);
            
            // 恢复作用域
            for (int i = 1; i < tokens.Count - 1; i += 2) {
                if (backup.ContainsKey(tokens[i])) {
                    scope[tokens[i]] = backup[tokens[i]];
                } else {
                    scope.Remove(tokens[i]);
                }
            }
            
            return result;
        }
    }
    
    private List<string> Parse(string expr) {
        List<string> tokens = new List<string>();
        int i = 1; // 跳过左括号
        
        while (i < expr.Length - 1) {
            if (expr[i] == ' ') {
                i++;
                continue;
            }
            
            if (expr[i] == '(') {
                int count = 1;
                int start = i;
                i++;
                while (count > 0) {
                    if (expr[i] == '(') count++;
                    else if (expr[i] == ')') count--;
                    i++;
                }
                tokens.Add(expr.Substring(start, i - start));
            } else {
                int start = i;
                while (i < expr.Length && expr[i] != ' ' && expr[i] != ')') {
                    i++;
                }
                tokens.Add(expr.Substring(start, i - start));
            }
        }
        
        return tokens;
    }
}

var evaluate = function(expression) {
    function parse(expr, scope) {
        if (expr[0] !== '(') {
            if (isNaN(expr)) {
                for (let i = scope.length - 1; i >= 0; i--) {
                    if (scope[i].has(expr)) {
                        return scope[i].get(expr);
                    }
                }
            }
            return parseInt(expr);
        }
        
        let tokens = tokenize(expr);
        let op = tokens[0];
        
        if (op === 'add') {
            return parse(tokens[1], scope) + parse(tokens[2], scope);
        } else if (op === 'mult') {
            return parse(tokens[1], scope) * parse(tokens[2], scope);
        } else if (op === 'let') {
            let newScope = new Map();
            scope.push(newScope);
            
            let i = 1;
            while (i < tokens.length - 1) {
                let variable = tokens[i];
                let value = parse(tokens[i + 1], scope);
                newScope.set(variable, value);
                i += 2;
            }
            
            let result = parse(tokens[tokens.length - 1], scope);
            scope.pop();
            return result;
        }
    }
    
    function tokenize(expr) {
        let tokens = [];
        let i = 1;
        let parenCount = 0;
        let start = 1;
        
        while (i < expr.length - 1) {
            if (expr[i] === '(') {
                parenCount++;
            } else if (expr[i] === ')') {
                parenCount--;
            } else if (expr[i] === ' ' && parenCount === 0) {
                tokens.push(expr.substring(start, i));
                start = i + 1;
            }
            i++;
        }
        
        if (start < expr.length - 1) {
            tokens.push(expr.substring(start, expr.length - 1));
        }
        
        return tokens;
    }
    
    return parse(expression, []);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n)	n 为表达式长度，每个字符最多被访问常数次
空间复杂度	O(n)	递归调用栈和作用域存储的空间开销

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目