关于程序员:736-Lisp-语法解析-DFS-模拟题

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

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

给你一个相似 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$
exprssion 中不含前导和尾随空格
expressoin 中的不同局部（token）之间用单个空格进行分隔
答案和所有两头计算结果都合乎 32-bit 整数范畴

明天身材不难受，不写太具体，题目不难，大家联合代码看吧。

设计函数 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），直到获得非法的「子表达式」或「对应的值」。
```
// 对于 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。

代码：

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;
    }
}

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

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

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

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

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

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的合集新基地 🎉🎉

本文由 mdnice 多平台公布

关于程序员:736-Lisp-语法解析-DFS-模拟题

题目形容

DFS 模仿

最初