当前位置:网站首页>LeetCode 736. Lisp 语法解析
LeetCode 736. Lisp 语法解析
2022-07-07 06:14:00 【Sasakihaise_】
【DFS】字符串解析+递归
首先提取出操作符后,后面按照子表达式的概念进行拆分,拆分后放在一个list中。
如果操作符为let,那么两两遍历,第一个字符串作为key,第二个字符串是一个表达式,继续递归解析,将返回值作为value一起存入map中。然后返回最后一个字符串的解析值。
如果操作符为add,那么只需要将两个表达式的解析结果相加返回。
操作符为mult同理。
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;
}
}
边栏推荐
- Virtual address space
- SSM integration
- National SMS center number inquiry
- [南京大学]-[软件分析]课程学习笔记(一)-introduction
- Greenplum6.x-版本变化记录-常用手册
- [Chongqing Guangdong education] organic electronics (Bilingual) reference materials of Nanjing University of Posts and Telecommunications
- Are you holding back on the publicity of the salary system for it posts such as testing, development, operation and maintenance?
- Exercise arrangement 2.10, 11
- redis故障处理 “Can‘t save in background: fork: Cannot allocate memory“
- Upload an e-office V9 arbitrary file [vulnerability recurrence practice]
猜你喜欢
Category of IP address
NCS Chengdu Xindian interview experience
[Yugong series] February 2022 U3D full stack class 006 unity toolbar
Teach you how to select PCB board by hand (II)
Novice entry SCM must understand those things
Why choose cloud native database
Virtual address space
Laravel8 uses passport login and JWT (generate token)
数据分析方法论与前人经验总结2【笔记干货】
Arm GIC (IV) GIC V3 register class analysis notes.
随机推荐
求有符号数的原码、反码和补码【C语言】
Componentspace2022, assertions, protocols, bindings, and configuration files
Analysis of using jsonp cross domain vulnerability and XSS vulnerability in honeypot
[Yugong series] February 2022 U3D full stack class 006 unity toolbar
Calling the creation engine interface of Huawei game multimedia service returns error code 1002, error message: the params is error
Uniapp wechat applet monitoring network
[machine learning] watermelon book data set_ data sharing
字符串操作
Mock. JS usage details
[Chongqing Guangdong education] organic electronics (Bilingual) reference materials of Nanjing University of Posts and Telecommunications
Tips for using jeditabletable
2 - 3 arbre de recherche
[Yu Yue education] C language programming reference of Zhongbei College of Nanjing Normal University
GOLand idea intellij 无法输入汉字
Data analysis methodology and previous experience summary 2 [notes dry goods]
Frequently Asked Coding Problems
[南京大学]-[软件分析]课程学习笔记(一)-introduction
Greenplum6.x监控软件搭建
Greenplum6.x重新初始化
Input and output of floating point data (C language)