当前位置:网站首页>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;
}
}
时间复杂度:除对表达式进行递归划分以外,还存在对 map
的每层拷贝操作,复杂度为空间复杂度:
最后
这是我们「刷穿 LeetCode」系列文章的第 No.736
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
边栏推荐
- 批量获取中国所有行政区域经边界纬度坐标(到县区级别)
- Boot - Prometheus push gateway use
- Explain in detail the matrix normalization function normalize() of OpenCV [norm or value range of the scoped matrix (normalization)], and attach norm_ Example code in the case of minmax
- Tensorflow GPU installation
- THREE.AxesHelper is not a constructor
- "Exquisite store manager" youth entrepreneurship incubation camp - the first phase of Shunde market has been successfully completed!
- Supersocket 1.6 creates a simple socket server with message length in the header
- BFS realizes breadth first traversal of adjacency matrix (with examples)
- 「笔记」折半搜索(Meet in the Middle)
- Install Firefox browser on raspberry pie /arm device
猜你喜欢
迈动互联中标北京人寿保险,助推客户提升品牌价值
第六篇,STM32脉冲宽度调制(PWM)编程
ARM裸板调试之JTAG调试体验
JTAG debugging experience of arm bare board debugging
「精致店主理人」青年创业孵化营·首期顺德场圆满结束!
第三方跳转网站 出现 405 Method Not Allowed
Activereportsjs 3.1 Chinese version | | | activereportsjs 3.1 English version
Explain in detail the matrix normalization function normalize() of OpenCV [norm or value range of the scoped matrix (normalization)], and attach norm_ Example code in the case of minmax
[Batch dos - cmd Command - Summary and Summary] - String search, find, Filter Commands (FIND, findstr), differentiation and Analysis of Find and findstr
[牛客] [NOIP2015]跳石头
随机推荐
筑梦数字时代,城链科技战略峰会西安站顺利落幕
随时随地查看远程试验数据与记录——IPEhub2与IPEmotion APP
第四篇,STM32中断控制编程
身体质量指数程序,入门写死的小程序项目
Neon Optimization: an optimization case of log10 function
View remote test data and records anytime, anywhere -- ipehub2 and ipemotion app
「精致店主理人」青年创业孵化营·首期顺德场圆满结束!
Do you understand this patch of the interface control devaxpress WinForms skin editor?
Installation of torch and torch vision in pytorch
ESP Arduino (IV) PWM waveform control output
[Batch dos - cmd Command - Summary and Summary] - String search, find, Filter Commands (FIND, findstr), differentiation and Analysis of Find and findstr
Installation and testing of pyflink
Install Firefox browser on raspberry pie /arm device
SuperSocket 1.6 创建一个简易的报文长度在头部的Socket服务器
Make a simple graphical interface with Tkinter
Explain in detail the matrix normalization function normalize() of OpenCV [norm or value range of the scoped matrix (normalization)], and attach norm_ Example code in the case of minmax
Maidong Internet won the bid of Beijing life insurance to boost customers' brand value
城联优品入股浩柏国际进军国际资本市场,已完成第一步
【JVM调优实战100例】04——方法区调优实战(上)
"Exquisite store manager" youth entrepreneurship incubation camp - the first phase of Shunde market has been successfully completed!