当前位置:网站首页>【736. Lisp 语法解析】
【736. Lisp 语法解析】
2022-07-06 22:14:00 【千北@】
来源:力扣(LeetCode)
描述:
给你一个类似 Lisp
语句的字符串表达式 expression
,求出其计算结果。
表达式语法如下所示:
表达式可以为整数,let 表达式,add 表达式,mult 表达式,或赋值的变量。表达式的结果总是一个整数。(整数可以是正整数、负整数、0)
let 表达式采用
"(let v1 e1 v2 e2 ... vn en expr)"
的形式,其中let
总是以字符串"let"
来表示,接下来会跟随一对或多对交替的变量和表达式,也就是说,第一个变量v1
被分配为表达式e1
的值,第二个变量v2
被分配为表达式e2
的值,依次类推;最终let
表达式的值为expr
表达式的值。add 表达式表示为
"(add e1 e2)"
,其中add
总是以字符串"add"
来表示,该表达式总是包含两个表达式e1、e2
,最终结果是e1
表达式的值与e2
表达式的值之 和 。mult 表达式表示为
"(mult e1 e2)"
,其中mult
总是以字符串"mult"
表示,该表达式总是包含两个表达式e1、e2
,最终结果是e1
表达式的值与e2
表达式的值之 积 。在该题目中,变量名以小写字符开始,之后跟随 0 个或多个小写字符或数字。为了方便,
"add"
,"let"
,"mult"
会被定义为 “关键字” ,不会用作变量名。最后,要说一下作用域的概念。计算变量名所对应的表达式时,在计算上下文中,首先检查最内层作用域(按括号计),然后按顺序依次检查外部作用域。测试用例中每一个表达式都是合法的。有关作用域的更多详细信息,请参阅示例。
示例 1:
输入:expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
输出:14
解释:
计算表达式 (add x y), 在检查变量 x 值时,
在变量的上下文中由最内层作用域依次向外检查。
首先找到 x = 3, 所以此处的 x 值是 3 。
示例 2:
输入:expression = "(let x 3 x 2 x)"
输出:2
解释:let 语句中的赋值运算按顺序处理即可。
示例 3:
输入:expression = "(let x 1 y 2 x (add x y) (add x y))"
输出:5
解释:
第一个 (add x y) 计算结果是 3,并且将此值赋给了 x 。
第二个 (add x y) 计算结果是 3 + 2 = 5 。
提示:
- 1 <= expression.length <= 2000
- exprssion 中不含前导和尾随空格
- expressoin 中的不同部分(token)之间用单个空格进行分隔
- 答案和所有中间计算结果都符合 32-bit 整数范围
- 测试用例中的表达式均为合法的且最终结果为整数
方法一:递归解析
对于一个表达式 expression
,如果它的首字符不等于左括号 ‘ ( ’
,那么它只能是一个整数或者变量;否则它是 let
, add
和 mult
三种表达式之一。
定义函数 parseVar
用来解析变量以及函数 parseInt
用来解析整数。使用 scope
来记录作用域,每个变量都依次记录下它从外到内的所有值,查找时只需要查找最后一个数值。我们递归地解析表达式 expression
。
expression
的下一个字符不等于左括号‘ ( ’
expression
的下一个字符是小写字母,那么表达式是一个变量,使用函数parseVar
解析变量,然后在scope
中查找变量的最后一个数值即最内层作用域的值并返回结果。expression
的下一个字符不是小写字母,那么表达式是一个整数,使用函数parseInt
解析并返回结果。
去掉左括号后,
expression
的下一个字符是‘ l ’
,那么表达式是let
表达式。对于let
表达式,需要判断是否已经解析到最后一个expr
表达式。- 如果下一个字符不是小写字母,或者解析变量后下一个字符是右括号
‘ ) ’
,说明是最后一个expr
表达式,计算它的值并返回结果。并且我们需要在scope
中清除let
表达式对应的作用域变量。 - 否则说明是交替的变量
vi
和表达式ei
,在scope
将变量vi
的数值列表增加表达式ei
的数值。
- 如果下一个字符不是小写字母,或者解析变量后下一个字符是右括号
去掉左括号后,
expression
的下一个字符是‘ a ’
,那么表达式是add
表达式。计算add
表达式对应的两个表达式 e1 和 e2 的值,返回两者之和。去掉左括号后,
expression
的下一个字符是‘ m ’
,那么表达式是mult
表达式。计算mult
表达式对应的两个表达式 e1 和 e2 的值,返回两者之积。
代码:
class Solution {
private:
unordered_map<string, vector<int>> scope;
public:
int evaluate(string expression) {
int start = 0;
return innerEvaluate(expression, start);
}
int innerEvaluate(const string &expression, int &start) {
if (expression[start] != '(') {
// 非表达式,可能为:整数或变量
if (islower(expression[start])) {
string var = parseVar(expression, start); // 变量
return scope[var].back();
} else {
// 整数
return parseInt(expression, start);
}
}
int ret;
start++; // 移除左括号
if (expression[start] == 'l') {
// "let" 表达式
start += 4; // 移除 "let "
vector<string> vars;
while (true) {
if (!islower(expression[start])) {
ret = innerEvaluate(expression, start); // let 表达式的最后一个 expr 表达式的值
break;
}
string var = parseVar(expression, start);
if (expression[start] == ')') {
ret = scope[var].back(); // let 表达式的最后一个 expr 表达式的值
break;
}
vars.push_back(var);
start++; // 移除空格
int e = innerEvaluate(expression, start);
scope[var].push_back(e);
start++; // 移除空格
}
for (auto var : vars) {
scope[var].pop_back(); // 清除当前作用域的变量
}
} else if (expression[start] == 'a') {
// "add" 表达式
start += 4; // 移除 "add "
int e1 = innerEvaluate(expression, start);
start++; // 移除空格
int e2 = innerEvaluate(expression, start);
ret = e1 + e2;
} else {
// "mult" 表达式
start += 5; // 移除 "mult "
int e1 = innerEvaluate(expression, start);
start++; // 移除空格
int e2 = innerEvaluate(expression, start);
ret = e1 * e2;
}
start++; // 移除右括号
return ret;
}
int parseInt(const string &expression, int &start) {
// 解析整数
int n = expression.size();
int ret = 0, sign = 1;
if (expression[start] == '-') {
sign = -1;
start++;
}
while (start < n && isdigit(expression[start])) {
ret = ret * 10 + (expression[start] - '0');
start++;
}
return sign * ret;
}
string parseVar(const string &expression, int &start) {
// 解析变量
int n = expression.size();
string ret;
while (start < n && expression[start] != ' ' && expression[start] != ')') {
ret.push_back(expression[start]);
start++;
}
return ret;
}
};
执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:8.5 MB, 在所有 C++ 提交中击败了75.73%的用户
复杂度分析
时间复杂度: O(n),其中 n 是字符串 expression 的长度。递归调用函数 innerEvaluate 在某一层调用的时间复杂度为 O(k),其中 k 为指针 start 在该层调用的移动次数。在整个递归调用过程中,指针 start 会遍历整个字符串,因此解析 expression 需要 O(n)。
空间复杂度: O(n)。保存 scope 以及递归调用栈需要 O(n) 的空间。
方法二:状态机
代码:
enum ExprStatus {
VALUE = 0, // 初始状态
NONE, // 表达式类型未知
LET, // let 表达式
LET1, // let 表达式已经解析了 vi 变量
LET2, // let 表达式已经解析了最后一个表达式 expr
ADD, // add 表达式
ADD1, // add 表达式已经解析了 e1 表达式
ADD2, // add 表达式已经解析了 e2 表达式
MULT, // mult 表达式
MULT1, // mult 表达式已经解析了 e1 表达式
MULT2, // mult 表达式已经解析了 e2 表达式
DONE // 解析完成
};
struct Expr {
ExprStatus status;
string var; // let 的变量 vi
int value; // VALUE 状态的数值,或者 LET2 状态最后一个表达式的数值
int e1, e2; // add 或 mult 表达式的两个表达式 e1 和 e2 的数值
Expr(ExprStatus s) {
status = s;
}
};
class Solution {
private:
unordered_map<string, vector<int>> scope;
public:
int evaluate(string expression) {
vector<vector<string>> vars;
int start = 0, n = expression.size();
stack<Expr> s;
Expr cur(VALUE);
while (start < n) {
if (expression[start] == ' ') {
start++; // 去掉空格
continue;
}
if (expression[start] == '(') {
start++; // 去掉左括号
s.push(cur);
cur = Expr(NONE);
continue;
}
string token;
if (expression[start] == ')') {
// 本质上是把表达式转成一个 token
start++; // 去掉右括号
if (cur.status == LET2) {
token = to_string(cur.value);
for (auto var : vars.back()) {
// 清除作用域
scope[var].pop_back();
}
vars.pop_back();
} else if (cur.status == ADD2) {
token = to_string(cur.e1 + cur.e2);
} else {
token = to_string(cur.e1 * cur.e2);
}
cur = s.top(); // 获取上层状态
s.pop();
} else {
while (start < n && expression[start] != ' ' && expression[start] != ')') {
token.push_back(expression[start]);
start++;
}
}
switch (cur.status) {
case VALUE:
cur.value = stoi(token);
cur.status = DONE;
break;
case NONE:
if (token == "let") {
cur.status = LET;
vars.emplace_back(); // 记录该层作用域的所有变量, 方便后续的清除
} else if (token == "add") {
cur.status = ADD;
} else if (token == "mult") {
cur.status = MULT;
}
break;
case LET:
if (expression[start] == ')') {
// let 表达式的最后一个 expr 表达式
cur.value = calculateToken(token);
cur.status = LET2;
} else {
cur.var = token;
vars.back().push_back(token); // 记录该层作用域的所有变量, 方便后续的清除
cur.status = LET1;
}
break;
case LET1:
scope[cur.var].push_back(calculateToken(token));
cur.status = LET;
break;
case ADD:
cur.e1 = calculateToken(token);
cur.status = ADD1;
break;
case ADD1:
cur.e2 = calculateToken(token);
cur.status = ADD2;
break;
case MULT:
cur.e1 = calculateToken(token);
cur.status = MULT1;
break;
case MULT1:
cur.e2 = calculateToken(token);
cur.status = MULT2;
break;
}
}
return cur.value;
}
int calculateToken(const string &token) {
if (islower(token[0])) {
return scope[token].back();
} else {
return stoi(token);
}
}
};
执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:7.3 MB, 在所有 C++ 提交中击败了93.20%的用户
复杂度分析
时间复杂度: O(n),其中 nn 是字符串 expression 的长度。状态机解析会遍历整个字符串,因此需要 O(n) 的时间。
空间复杂度: O(n)。保存状态的栈以及作用域变量都需要 O(n) 的空间。
author:LeetCode-Solution
边栏推荐
- 关于01背包个人的一些理解
- On the 110th anniversary of Turing's birth, has the prediction of intelligent machine come true?
- 树与图的深度优先遍历模版原理
- AI表现越差,获得奖金越高?纽约大学博士拿出百万重金,悬赏让大模型表现差劲的任务
- Break the memory wall with CPU scheme? Learn from PayPal to expand the capacity of aoteng, and the volume of missed fraud transactions can be reduced to 1/30
- Jetson nano configures pytorch deep learning environment / / to be improved
- Tiktok may launch an independent grass planting community platform: will it become the second little red book
- MySQL null value processing and value replacement
- B站大佬用我的世界搞出卷积神经网络,LeCun转发!爆肝6个月,播放破百万
- acwing 843. n-皇后问题
猜你喜欢
Intel and Xinbu technology jointly build a machine vision development kit to jointly promote the transformation of industrial intelligence
Field data acquisition and edge calculation scheme of CNC machine tools
计数排序基础思路
树与图的深度优先遍历模版原理
Windows are not cheap things
Depth first traversal template principle of tree and graph
Programmers go to work fishing, so play high-end!
[line segment tree practice] recent requests + area and retrieval - array modifiable + my schedule I / III
【实践出真理】import和require的引入方式真的和网上说的一样吗
Break the memory wall with CPU scheme? Learn from PayPal to expand the capacity of aoteng, and the volume of missed fraud transactions can be reduced to 1/30
随机推荐
Code source de la fonction [analogique numérique] MATLAB allcycles () (non disponible avant 2021a)
浙江大学周亚金:“又破又立”的顶尖安全学者,好奇心驱动的行动派
leetcode 53. Maximum subarray maximum subarray sum (medium)
Unit test asp Net MVC 4 Application - unit testing asp Net MVC 4 apps thoroughly
Intel and Xinbu technology jointly build a machine vision development kit to jointly promote the transformation of industrial intelligence
Up to 5million per person per year! Choose people instead of projects, focus on basic scientific research, and scientists dominate the "new cornerstone" funded by Tencent to start the application
广告归因:买量如何做价值衡量?
MySQL数据库(基础篇)
What is Web3
[line segment tree practice] recent requests + area and retrieval - array modifiable + my schedule I / III
Digital chemical plants realize the coexistence of advantages of high quality, low cost and fast efficiency
How does vscade use the built-in browser?
Vscode 如何使用内置浏览器?
Windows are not cheap things
九章云极DataCanvas公司蝉联中国机器学习平台市场TOP 3
Jetson nano configures pytorch deep learning environment / / to be improved
EasyCVR集群重启导致其他服务器设备通道状态离线情况的优化
Master the secrets of software security testing methods, and pinch the security test report with your hands
树与图的深度优先遍历模版原理
Fiance donated 500million dollars to female PI, so that she didn't need to apply for projects, recruited 150 scientists, and did scientific research at ease!