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

科技 07-06 来源：南方葵籽

题目描述

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

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

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

表达式语法如下所示:

表达式可以为整数，let 表达式，add 表达式，mult 表达式，或赋值的变量。表达式的结果总是一个整数。
(整数可以是正整数、负整数、000)
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 表达式的值之积。
在该题目中，变量名以小写字符开始，之后跟随 000 个或多个小写字符或数字。为了方便，"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<=20001 <= expression.length <= 20001<=expression.length<=2000
exprssion 中不含前导和尾随空格
expressoin 中的不同部分（token）之间用单个空格进行分隔
答案和所有中间计算结果都符合 32-bit 整数范围

DFS 模拟

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

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

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

若 s[l]=(s[l] = (s[l]=(，说明是表达式，此时从 lll 开始往后取，取到空格为止（假设位置为 idx），从而得到操作 op（其中 op 为 let、add 或 mult 三者之一），此时 op 对应参数为 [idx+1,r−1][idx + 1, r - 1][idx+1,r−1]，也就是需要跳过位置 rrr（即跳过 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]s[l...r] 不是表达式，通过判断 s[l...r]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 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;
    }
}