0736. Parse Lisp Expression

题目信息

题号:

0736

难度:

Hard

主题:

字符串、表达式求值、词法作用域

原题:

LeetCode 0736

重点:

表达式包含整数、变量、let、add 和 mult;let 赋值按顺序生效,变量查找优先使用最内层作用域

题目重述

给定一个合法的类 Lisp 表达式字符串 expression,按以下语法计算并返回其整数值:

  • 整数表达式可以是正整数或负整数;

  • 变量表达式取该变量在当前可见作用域中的值;

  • (add e1 e2) 计算两个子表达式之和;

  • (mult e1 e2) 计算两个子表达式之积;

  • (let v1 e1 v2 e2 ... vn en expr) 依次计算并完成每组变量赋值,最后计算 expr,其值就是整个 let 表达式的值。

同一 let 中的赋值严格按从左到右的顺序生效,后续表达式可以读取此前已完成的赋值。嵌套表达式形成词法作用域:读取变量时先查找最内层作用域,再依次查找外层;内层对同名变量的赋值只在该内层作用域中遮蔽外层值。

变量名以小写英文字母开头,后面可跟小写字母或数字;add、let、mult 不会作为变量名。输入长度在 [1, 2000] 范围内,没有首尾空格,标记之间恰好由一个空格分隔;表达式保证合法,最终结果及全部中间计算均在 32 位有符号整数范围内。

自建示例

赋值按顺序使用此前变量:

输入:expression = "(let x 5 y (add x 3) (mult y (add x -1)))"
输出:32
解释:先令 x = 5,再令 y = 5 + 3 = 8;最终表达式为 8 * (5 + (-1)) = 32。

内层同名变量遮蔽外层变量:

输入:expression = "(let a 2 (add (let a 7 a) a))"
输出:9
解释:内层 let 中的 a 为 7,离开内层后外层 a 仍为 2,因此最终结果为 7 + 2 = 9。