共计 3257 个字符，预计需要花费 9 分钟才能阅读完成。
题目形容
这是 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整数范畴
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），直到获得非法的「子表达式」或「对应的值」。// 对于 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 多平台公布
