当前位置：网站首页>736. Lisp 语法解析 : DFS 模拟题

736. Lisp 语法解析 : DFS 模拟题

2022-07-06 17:32:00 【宫水三叶的刷题日记】

题目描述

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

Tag : 「DFS」、「模拟」、「哈希表」

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

表达式语法如下所示:

表达式可以为整数， let 表达式， add 表达式， mult 表达式，或赋值的变量。表达式的结果总是一个整数。
(整数可以是正整数、负整数、 )
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 表达式的值之积。
在该题目中，变量名以小写字符开始，之后跟随个或多个小写字符或数字。为了方便， "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 。

提示：

exprssion 中不含前导和尾随空格
expressoin 中的不同部分（ token）之间用单个空格进行分隔
答案和所有中间计算结果都符合 32-bit 整数范围

DFS 模拟

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

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

根据传入的是否为表达式分情况讨论：

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

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

// 对于 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

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

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

代码：

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--; // 判别为 "(let"、"(add" 或 "(mult" 后，跳过对应的 ")"
            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 if (op.equals("add")) {
                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 a + b;
            } 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 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;
    }
}