当前位置:网站首页>LeetCode 736. LISP syntax parsing
LeetCode 736. LISP syntax parsing
2022-07-07 08:50:00 【Sasakihaise_】
【DFS】 String parsing + recursive
First extract the operator , Later, it will be split according to the concept of sub expression , Put it in a list in .
If the operator is let, So two by two traversal , The first string is used as key, The second string is an expression , Continue recursive parsing , Take the return value as value Deposit together map in . Then return the parsed value of the last string .
If the operator is add, Then you only need to add the parsing results of the two expressions to return .
The operator is mult Empathy .
class Solution {
// dfs 9:32 11:00
int ans = 0;
int dfs(Map<String, Integer> map, String ex) {
if ((ex.charAt(0) >= '0' && ex.charAt(0) <= '9') || ex.charAt(0) == '-') {
return Integer.parseInt(ex);
}
if (ex.charAt(0) == '(') {
ex = ex.substring(1, ex.length() - 1);
}
// System.out.println(ex);
// for (var k: map.keySet()) {
// System.out.print(k + "," + map.get(k) + ";");
// }
// System.out.println();
int n = ex.length(), i = 0, j = 0;
while (j < n && ex.charAt(j) != ' ') {
j++;
}
List<String> list = new ArrayList();
String op = ex.substring(i, j);
i = ++j;
int t = 0;
char c;
if (op.equals("let")) {
while (i < n) {
while (j < n) {
c = ex.charAt(j);
if (t != 0) {
if (c == ')') {
t--;
} else if (c == '(') {
t++;
}
} else {
if (c == '(') {
t++;
} else if (c == ' ') {
break;
}
}
j++;
}
list.add(ex.substring(i, j));
i = ++j;
}
int m = list.size() - 1;
Map<String, Integer> next = new HashMap(map);
for (i = 0; i < m; i += 2) {
char ch = list.get(i + 1).charAt(0);
if ((ch >= '0' && ch <= '9') || ch == '-') {
next.put(list.get(i), Integer.parseInt(list.get(i + 1)));
} else {
next.put(list.get(i), dfs(next, list.get(i + 1)));
}
}
ans = dfs(next, list.get(m));
return ans;
} else if (op.equals("add") || op.equals("mult")) {
while (i < n) {
while (j < n) {
c = ex.charAt(j);
if (t != 0) {
if (c == ')') {
t--;
} else if(c == '(') {
t++;
}
} else {
if (c == '(') {
t++;
} else if (c == ' ') {
break;
}
}
j++;
}
list.add(ex.substring(i, j));
i = ++j;
}
int ret = 0;
if (op.equals("add")) {
for (var e: list) {
if (map.containsKey(e)) {
ret += map.get(e);
} else {
ret += dfs(map, e);
}
}
} else {
ret = 1;
for (var e: list) {
if (map.containsKey(e)) {
ret *= map.get(e);
} else {
ret *= dfs(map, e);
}
}
}
return ret;
} else {
// System.out.println(op);
return map.get(op);
}
}
public int evaluate(String expression) {
Map<String, Integer> map = new HashMap();
return dfs(map, expression);
// return ans;
}
}
边栏推荐
- Test pits - what test points should be paid attention to when adding fields to existing interfaces (or database tables)?
- [Nanjing University] - [software analysis] course learning notes (I) -introduction
- National SMS center number inquiry
- opencv之图像分割
- Greenplum6.x-版本变化记录-常用手册
- All about PDF crack, a complete solution to meet all your PDF needs
- 【微信小程序:缓存操作】
- Data type - floating point (C language)
- How to add a mask of a target in a picture
- Teach you how to select PCB board by hand (II)
猜你喜欢
NCS Chengdu New Electric interview Experience
Explain Huawei's application market in detail, and gradually reduce 32-bit package applications and strategies in 2022
Data type - floating point (C language)
快速集成认证服务-HarmonyOS平台
路由信息协议——RIP
Appeler l'interface du moteur de création du service multimédia de jeu Huawei renvoie le Code d'erreur 1002, le message d'erreur: les paramètres sont l'erreur
Greenplum 6.x build_ install
联想混合云Lenovo xCloud:4大产品线+IT服务门户
Download and install orcale database11.2.0.4
最长上升子序列模型 AcWing 1017. 怪盗基德的滑翔翼
随机推荐
Routing information protocol rip
Analysis of using jsonp cross domain vulnerability and XSS vulnerability in honeypot
阿里p8推荐,测试覆盖率工具—Jacoco,实用性极佳
Appeler l'interface du moteur de création du service multimédia de jeu Huawei renvoie le Code d'erreur 1002, le message d'erreur: les paramètres sont l'erreur
Frequently Asked Coding Problems
平台化,强链补链的一个支点
How to realize sliding operation component in fast application
[machine learning] watermelon book data set_ data sharing
NCS Chengdu New Electric interview Experience
Tronapi-波场接口-源码无加密-可二开--附接口文档-基于ThinkPHP5封装-作者详细指导-2022年7月6日-新手快速上手-可无缝升级tp6版本
Redis summary
求有符号数的原码、反码和补码【C语言】
[Yu Yue education] higher vocational English reference materials of Nanjing Polytechnic University
Basic data types and string types are converted to each other
Go write a program that runs within a certain period of time
【微信小程序:缓存操作】
Greenplum6.x-版本变化记录-常用手册
[MySQL] detailed explanation of trigger content of database advanced
Oracle makes it clear at one time that a field with multiple separators will be split into multiple rows, and then multiple rows and columns. Multiple separators will be split into multiple rows, and
更改当前文件夹及文件夹下文件日期shell脚本