0736：Lisp 语法解析（★★）

2017-01-05 约 1036 字预计阅读 3 分钟次阅读

力扣第 736 题

题目

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

表达式语法如下所示:

表达式可以为整数，let 表达式，add 表达式，mult 表达式，或赋值的变量。表达式的结果总是一个整数。
(整数可以是正整数、负整数、0)
let 表达式采用 "(let v₁ e₁ v₂ e₂ ... v_n e_n expr)" 的形式，其中 let 总是以字符串 "let"来表示，接下来会跟随一对或多对交替的变量和表达式，也就是说，第一个变量 v₁被分配为表达式 e₁ 的值，第二个变量 v₂ 被分配为表达式 e₂ 的值，依次类推；最终 let 表达式的值为 expr表达式的值。
add 表达式表示为 "(add e₁ e₂)" ，其中 add 总是以字符串 "add" 来表示，该表达式总是包含两个表达式 e₁、e₂ ，最终结果是 e₁ 表达式的值与 e₂ 表达式的值之和。
mult 表达式表示为 "(mult e₁ e₂)" ，其中 mult 总是以字符串 "mult" 表示，该表达式总是包含两个表达式 e₁、e₂，最终结果是 e₁ 表达式的值与 e₂ 表达式的值之积。
在该题目中，变量名以小写字符开始，之后跟随 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
exprssion 中不含前导和尾随空格
expressoin 中的不同部分（token）之间用单个空格进行分隔
答案和所有中间计算结果都符合 32-bit 整数范围
测试用例中的表达式均为合法的且最终结果为整数

相似问题：

分析

典型的用栈模拟递归的问题
每一层需要单独维护 let 的赋值
需要注意赋值 (let v e) 中，v 和 e 可能都是变量，如 (let x 2 y x)

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def evaluate(self, expression: str) -> int:
        sk, D = [[]], [{}]
        for l,op,r,c in re.findall('(\()([a-z]+)|(\))|(-?[a-z0-9]+)',expression):
            if l:
                sk.append([op])
                D.append(D[-1].copy())
            elif r:
                x = sk.pop()[-1]
                sk[-1].append(D.pop().get(x,x))
            else:
                sk[-1].append(c if c[0].isalpha() else int(c))
            if len(sk[-1])>2:
                y,x,d = sk[-1].pop(),sk[-1].pop(),D[-1]
                if sk[-1][0]=='let':
                    d[x] = d.get(y,y)
                else:
                    a,b = d.get(x,x),d.get(y,y)
                    sk[-1].append(a+b if sk[-1][0]=='add' else a*b)
        return sk[0][-1]

3 ms

目录

0736：Lisp 语法解析（★★）

题目

分析

解答