LC 736. Lisp 语法解析

题目描述

这是 LeetCode 上的 736. Lisp 语法解析 ，难度为 困难。

给你一个类似 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：

1
2
3
4
5
6
7
8
输入：expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"

输出：14

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

示例 2：

1
2
3
4
5
输入：expression = "(let x 3 x 2 x)"

输出：2

解释：let 语句中的赋值运算按顺序处理即可。

示例 3：
1
2
3
4
5
6
7
输入：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 整数范围

DFS 模拟

今天身体不舒服，不写太详细，题目不难，大家结合代码看吧。

设计函数 int dfs(int l, int r, Map<String, Integer> map)，代表计算 $s[l…r]$ 的结果，答案为 dfs(0,n-1,map)，其中 $n$ 为字符串的长度。

根据传入的 $[l, r]$ 是否为表达式分情况讨论：

  • 若 $s[l] = ($，说明是表达式，此时从 $l$ 开始往后取，取到空格为止（假设位置为 idx），从而得到操作 op（其中 op 为 let、add 或 mult 三者之一），此时 op 对应参数为 $[idx + 1, r - 1]$，也就是需要跳过位置 $r$（即跳过 op 对应的 ) 符号）；

    再根据 op 为何种操作进一步处理，我们设计一个「传入左端点找右端点」的函数 int getRight(int left, int end)，含义为从 left 出发，一直往右找（不超过 end），直到取得合法的「子表达式」或「对应的值」。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 对于 getRight 函数作用，给大家举个 🌰 理解吧，其实就是从 left 出发，找到合法的「子表达式」或「值」为止

    // (let x 2 (mult x (let x 3 y 4 (add x y))))
    //          a                               b
    // 传入 a 返回 b，代表 [a, b) 表达式为 (mult x (let x 3 y 4 (add x y)))

    // (let x 2 (mult x (let x 3 y 4 (add x y))))
    //      ab
    // 传入 a 返回 b，代表 [a, b) 表达式为 x

  • 否则 $s[l…r]$ 不是表达式，通过判断 $s[l…r]$ 是否有被哈希表记录来得知结果：若在哈希表中有记录，结果为哈希表中的映射值，否则结果为本身所代表的数值。

需要注意，根据「作用域」的定义，我们不能使用全局哈希表，而要在每一层递归时，传入 clone 出来的 map。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    char[] cs;
    String s;
    public int evaluate(String _s) {
        s = _s;
        cs = s.toCharArray();
        return dfs(0, cs.length - 1, new HashMap<>());
    }
    int dfs(int l, int r, Map<String, Integer> map) {
        if (cs[l] == '(') {
            int idx = l;
            while (cs[idx] != ' ') idx++;
            String op = s.substring(l + 1, idx);
            r--;
            if (op.equals("let")) {
                for (int i = idx + 1; i <= r; ) {
                    int j = getRight(i, r);
                    String key = s.substring(i, j);
                    if (j >= r) return dfs(i, j - 1, new HashMap<>(map));
                    j++; i = j;
                    j = getRight(i, r);
                    int value = dfs(i, j - 1, new HashMap<>(map));
                    map.put(key, value);
                    i = j + 1;
                }
                return -1; // never
            } else {
                int j = getRight(idx + 1, r);
                int a = dfs(idx + 1, j - 1, new HashMap<>(map)), b = dfs(j + 1, r, new HashMap<>(map));
                return op.equals("add") ? a + b : a * b;
            }
        } else {
            String cur = s.substring(l, r + 1);
            if (map.containsKey(cur)) return map.get(cur);
            return Integer.parseInt(cur);
        }
    }
    int getRight(int left, int end) {
        int right = left, score = 0;
        while (right <= end) {
            if (cs[right] == '(') {
                score++; right++;
            } else if (cs[right] == ')') {
                score--; right++;
            } else if (cs[right] == ' ') {
                if (score == 0) break;
                right++;
            } else {
                right++;
            }
        }
        return right;
    }
}

  • 时间复杂度：除对表达式进行递归划分以外，还存在对 map 的每层拷贝操作，复杂度为 $O(n^2)$
  • 空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.736 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

哈希表 模拟 DFS

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！