当前位置:网站首页>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
边栏推荐
- Body mass index program, entry to write dead applet project
- Metauniverse urban legend 02: metaphor of the number one player
- HMM 笔记
- Neon Optimization: an optimization case of log10 function
- Failed to successfully launch or connect to a child MSBuild. exe process. Verify that the MSBuild. exe
- Make Jar, Not War
- Neon Optimization: an instruction optimization case of matrix transpose
- How to evaluate load balancing performance parameters?
- 身体质量指数程序,入门写死的小程序项目
- 黑马笔记---创建不可变集合与Stream流
猜你喜欢
JTAG principle of arm bare board debugging
Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
Yunna - work order management system and process, work order management specification
[advanced C language] 8 written questions of pointer
Typical problems of subnet division and super network construction
ARM裸板调试之JTAG调试体验
Force buckle 1037 Effective boomerang
ARM裸板调试之JTAG原理
阿里云中mysql数据库被攻击了,最终数据找回来了
Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman
随机推荐
Sword finger offer II 035 Minimum time difference - quick sort plus data conversion
Oracle: Practice of CDB restricting PDB resources
736. Lisp 语法解析 : DFS 模拟题
Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
Oracle:CDB限制PDB资源实战
c语言—数组
Clickhouse fields are grouped and aggregated, and SQL is queried according to the granularity of any time period
golang中的WaitGroup实现原理
[Niuke] [noip2015] jumping stone
实现mysql与ES的增量数据同步
Taro applet enables wxml code compression
树莓派/arm设备上安装火狐Firefox浏览器
Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman
安利一波C2工具
【案例分享】网络环路检测基本功能配置
LeetCode:1175. Prime permutation
云呐-工单管理制度及流程,工单管理规范
免费白嫖的图床对比
身体质量指数程序,入门写死的小程序项目
2022 Google CTF SEGFAULT LABYRINTH wp