当前位置:网站首页>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
边栏推荐
- Oracle: Practice of CDB restricting PDB resources
- How to manage distributed teams?
- Neon Optimization: an instruction optimization case of matrix transpose
- Yunna | work order management measures, how to carry out work order management
- 实现mysql与ES的增量数据同步
- NEON优化:性能优化经验总结
- C language instance_ five
- 如何管理分布式团队?
- 力扣1037. 有效的回旋镖
- 交叉验证如何防止过拟合
猜你喜欢
Transformation transformation operator
Make Jar, Not War
对C语言数组的再认识
[case sharing] basic function configuration of network loop detection
2022 Google CTF SEGFAULT LABYRINTH wp
阿里云中mysql数据库被攻击了,最终数据找回来了
ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
Can the system hibernation file be deleted? How to delete the system hibernation file
Make Jar, Not War
Js逆向——捅了【马蜂窝】的ob混淆与加速乐
随机推荐
Typical problems of subnet division and super network construction
golang 基础 —— 数据类型
[signal and system]
Vocabulary in Data Book
C # method of calculating lunar calendar date 2022
Dark horse notes - create immutable sets and streams
Boot - Prometheus push gateway use
Neon Optimization: summary of performance optimization experience
Can the system hibernation file be deleted? How to delete the system hibernation file
1123. The nearest common ancestor of the deepest leaf node
Dark horse notes - exception handling
阿里云中mysql数据库被攻击了,最终数据找回来了
Implementation principle of waitgroup in golang
【芯片方案设计】脉搏血氧仪
C language - array
Match VIM from zero (0) -- Introduction to vimscript
Yunna | work order management measures, how to carry out work order management
【C语言进阶篇】指针的8道笔试题
系统休眠文件可以删除吗 系统休眠文件怎么删除
ARM裸板调试之JTAG调试体验