当前位置:网站首页>736. LISP syntax parsing: DFS simulation questions
736. LISP syntax parsing: DFS simulation questions
2022-07-07 01:26:00 【Gong Shui Sanye's Diary of writing questions】
Title Description
This is a LeetCode Upper 736. Lisp Syntax parsing , The difficulty is difficult .
Tag : 「DFS」、「 simulation 」、「 Hashtable 」
Give you a similar Lisp
String expression of statement expression
, Calculate the result .
The expression syntax is as follows :
Expressions can be integers , let
expression ,add
expression ,mult
expression , Or assigned variable . The result of an expression is always an integer .( Integers can be positive integers 、 Negtive integer 、 ) let
The expression uses"(let v1 e1 v2 e2 ... vn en expr)"
In the form of , amonglet
Always in string"let"
To express , Next, one or more pairs of alternating variables and expressions will follow , in other words , The first variablev1
Is assigned as an expressione1
Value , The second variablev2
Is assigned as an expressione2
Value , By analogy ; Finallet
The value of the expression isexpr
Value of expression .add
The expression is expressed as"(add e1 e2)"
, amongadd
Always in string"add"
To express , This expression always contains two expressionse1
、e2
, The end result ise1
The value of the expression ande2
The value of the expression and .mult
The expression is expressed as"(mult e1 e2)"
, amongmult
Always in string"mult"
Express , This expression always contains two expressionse1
、e2, The end result ise1
The value of the expression ande2
The value of the expression product .In this topic , Variable names start with lowercase characters , Follow after One or more lowercase characters or numbers . For convenience , "add"
,"let"
,"mult"
Will be defined as `" keyword " , Will not be used as a variable name .Last , Let's talk about the concept of scope . When calculating the expression corresponding to the variable name , In a computational context , First check the innermost scope ( In parentheses ), Then check the external scopes in order . Every expression in the test case is legal . More details about scope , See example .
Example 1:
Input :expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))" Output :14 explain : Calculation expression (add x y), Checking variables x When the value of , In the context of variables, the innermost scope checks outward in turn . First find x = 3, So here's x The value is 3 . Example 2:
Input :expression = "(let x 3 x 2 x)"
Output :2
explain :let The assignment operation in the statement can be processed in sequence .
Example 3:
Input :expression = "(let x 1 y 2 x (add x y) (add x y))"
Output :5
explain :
first (add x y) The result is 3, And assign this value to x .
the second (add x y) The result is 3 + 2 = 5 .
Tips :
exprssion
There are no leading and trailing spaces inexpressoin
Different parts of (token
) Separated by a single spaceThe answer is consistent with all intermediate calculations 32-bit
Integer range
DFS simulation
I'm not feeling well today , Don't write too detailed , The title is not difficult. , Let's look at it in combination with the code .
Design function int dfs(int l, int r, Map<String, Integer> map)
function , For calculation Result , The answer for dfs(0,n-1,map)
, among Is the length of the string .
Based on the incoming Whether to discuss the expression by case :
if , The description is an expression , At that moment, from Start taking back , Until the space is filled ( Suppose the location is
idx
), So as to get the operationop
( amongop
bylet
、add
ormult
One of the three ), hereop
The corresponding parameter is , That is, you need to skip the position ( That is, skipop
Corresponding)
Symbol );According to
op
What kind of operation is further processed , Let's design a 「 Pass in the left endpoint and find the right endpoint 」 Function ofint getRight(int left, int end)
, Meaning fromleft
set out , Keep looking right ( No more thanend
), Until legal 「 subexpression 」 or 「 Corresponding value 」.// about getRight Function function , Let me give you an example To understand! , In fact, from left set out , Find the legal 「 subexpression 」 or 「 value 」 until
// (let x 2 (mult x (let x 3 y 4 (add x y))))
// a b
// Pass in a return b, representative [a, b) Expression for (mult x (let x 3 y 4 (add x y)))
// (let x 2 (mult x (let x 3 y 4 (add x y))))
// ab
// Pass in a return b, representative [a, b) Expression for xotherwise It's not an expression , By judgment Whether it is recorded by hash table to know the result : If there are records in the hash table , The result is the mapped value in the hash table , Otherwise, the result is the value represented by itself .
We need to pay attention to , according to 「 Scope 」 The definition of , We cannot use global hash tables , When recursing at each level , Pass in clone
Coming out map
.
Code :
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--; // Judge as "(let"、"(add" or "(mult" after , Skip the corresponding ")"
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;
}
}
Time complexity : In addition to recursively dividing expressions , There is also a right map
Each layer of copy operations , The complexity isSpatial complexity :
Last
This is us. 「 Brush through LeetCode」 The first of the series No.736
piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .
In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .
In order to facilitate the students to debug and submit code on the computer , I've built a warehouse :https://github.com/SharingSource/LogicStack-LeetCode .
In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .
More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases
边栏推荐
- tansig和logsig的差异,为什么BP喜欢用tansig
- Yunna | work order management software, work order management software app
- NEON优化:关于交叉存取与反向交叉存取
- 黑马笔记---创建不可变集合与Stream流
- 7.6 simulation summary
- 实现mysql与ES的增量数据同步
- Installation and testing of pyflink
- NEON优化:性能优化常见问题QA
- Send template message via wechat official account
- Dark horse notes - exception handling
猜你喜欢
Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
boot - prometheus-push gateway 使用
一起看看matlab工具箱内部是如何实现BP神经网络的
Go zero micro service practical series (IX. ultimate optimization of seckill performance)
2022 Google CTF SEGFAULT LABYRINTH wp
Wood extraction in Halcon
ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
阿里云中mysql数据库被攻击了,最终数据找回来了
从底层结构开始学习FPGA----FIFO IP的定制与测试
Send template message via wechat official account
随机推荐
Atomic in golang and CAS operations
C # method of calculating lunar calendar date 2022
C language instance_ four
Boot - Prometheus push gateway use
ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
NEON优化:性能优化经验总结
HMM notes
LeetCode. 剑指offer 62. 圆圈中最后剩下的数
Google released a security update to fix 0 days that have been used in chrome
[Niuke] [noip2015] jumping stone
云呐|工单管理办法,如何开展工单管理
golang中的atomic,以及CAS操作
Oracle: Practice of CDB restricting PDB resources
Taro 小程序开启wxml代码压缩
树莓派/arm设备上安装火狐Firefox浏览器
[Niuke] b-complete square
Can the system hibernation file be deleted? How to delete the system hibernation file
2022 Google CTF SEGFAULT LABYRINTH wp
The MySQL database in Alibaba cloud was attacked, and finally the data was found
C language instance_ five