题目描述
这是 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
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{
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{
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 - 时间复杂度：除对表达式进行递归划分以外，还存在对
map
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第
No.736
篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)