【栈】736. Lisp 语法解析

农妇山泉一亩田 · 2024-6-14 23:11:12

本文涉及知识点

栈
LeetCode736. Lisp 语法解析

给你一个类似 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 整数范围
测试用例中的表达式均为正当的且终极效果为整数
栈

包罗标识符（变量关键字）常量（）
递归解析每个括号。unorder_map<string,stack> m_mVar 记录各变量的值。
一个括号从左到右解析，解析到变量入栈，本括号解析结束出栈。注意：不能先解析最内层括号，好比：(let x 2 add(x 1)) 先解析add会检测到未定义变量，而误认为黑白法字符串。
Parse 函数大致流程：
一，如果有前置空格，忽略。忽略左括号。
二，解析下令名。
三，如果是加或乘法，读取两个值。并返回效果。
四，读取变量，如果失败则读值。
五，忽略空格后，如果是右括号。则盘算返回值，并变量出栈。
六，忽略空格后，如果不是右括号。读取值，更新变量的值，并入栈。
IgronSpace ：如果有空格，则忽略。
GetNum1：读取值，包罗变量常量表达式。
ParseName：解析变量名，字母开始，后效字符可以是字母，也可以是数字。
ParseNum：解析数字和表达式。
注意：iPos指向下一个待处理惩罚的字符。
代码

核心代码

class Solution {
public:
int evaluate(string expression) {
m_exp = expression;
int iPos = 0;
return Parse(iPos);
}
int Parse(int& iPos) {
auto tmp = m_exp.substr(iPos);
while ((iPos < m_exp.length()) && ('(' != m_exp[iPos])) {
iPos++;
}
iPos += 1;//跳过(和空格
string strName = ParseName(iPos);
iPos++;
if ("mult" == strName) {
int num1 = GetNum1(iPos);
int num2 = GetNum1(++iPos);
IgronSpace(iPos);
iPos++;
return num1 * num2;
}
if ("add" == strName) {
int num1 = GetNum1(iPos);
int num2 = GetNum1(++iPos);
IgronSpace(iPos);
iPos++;
return num1 + num2;
}
assert("let" == strName);
vector<string> vars;
while (true) {
auto iRet = 0;
string strVarName = ParseName(iPos);
if ("" != strVarName) {
IgronSpace(iPos);
}
else {
iRet += GetNum1(iPos);
IgronSpace(iPos);
}
if (')' == m_exp[iPos]) {
if ("" != strVarName)
{
iRet = m_mVar[strVarName].top();
}
for (auto var : vars) {//变量出栈
m_mVar[var].pop();
}
iPos++;
return iRet;
}
vars.emplace_back(strVarName);
const int cur = GetNum1(iPos);
m_mVar[strVarName].emplace();
m_mVar[strVarName].top() = cur;
iPos++;
}
}
void IgronSpace(int& iPos) {
if((iPos < m_exp.length())&&(' ' == m_exp[iPos])){iPos++;};
}
int GetNum1(int& iPos) {
string strName = ParseName(iPos);
if ("" != strName) { return m_mVar[strName].top(); }
return ParseNum(iPos);
}
string ParseName(int& iPos) {
string strName;
while ((isalpha(m_exp[iPos]))||(strName.size() && isalnum(m_exp[iPos]))) {
strName += m_exp[iPos++];
}
return strName;
}
int ParseNum(int& iPos) {
int num = 0;
if ('(' == m_exp[iPos]) { return Parse(iPos); }
int iSign = 1;
if ('-' == m_exp[iPos]) {
iSign = -1; iPos++;
}
while (isdigit(m_exp[iPos])) {
num = num*10+ (m_exp[iPos]-'0');
iPos++;
}
return iSign* num;
}
unordered_map<string, stack<int>> m_mVar;
string m_exp;
};

复制代码

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
Assert::AreEqual(t1 , t2);
}
template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
Assert::AreEqual(v1.size(), v2.size());
for (int i = 0; i < v1.size(); i++)
{
Assert::AreEqual(v1[i], v2[i]);
}
}
template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
sort(vv1.begin(), vv1.end());
sort(vv2.begin(), vv2.end());
Assert::AreEqual(vv1.size(), vv2.size());
for (int i = 0; i < vv1.size(); i++)
{
AssertEx(vv1[i], vv2[i]);
}
}
namespace UnitTest
{
string expression;
TEST_CLASS(UnitTest)
{
public:
TEST_METHOD(TestMethod0)
{
expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))";
auto res = Solution().evaluate(expression);
AssertEx(14,res);
}
TEST_METHOD(TestMethod1)
{
expression = "(let x 3 x 2 x)";
auto res = Solution().evaluate(expression);
AssertEx(2, res);
}
TEST_METHOD(TestMethod2)
{
expression = "(let x 1 y 2 x (add x y) (add x y))";
auto res = Solution().evaluate(expression);
AssertEx(5, res);
}
TEST_METHOD(TestMethod3)
{
expression = "(let x 7 -12)";
auto res = Solution().evaluate(expression);
AssertEx(-12, res);
}
TEST_METHOD(TestMethod5)
{
expression = "(let x 2 (add (let x 3 (let x 4 x)) x))";
auto res = Solution().evaluate(expression);
AssertEx(6, res);
}
TEST_METHOD(TestMethod6)
{
expression = "(let x 2 (add (let x 3 4) x))";
auto res = Solution().evaluate(expression);
AssertEx(6, res);
}
TEST_METHOD(TestMethod7)
{
expression = "(let x 2 (add 4 x))";
auto res = Solution().evaluate(expression);
AssertEx(6, res);
}
TEST_METHOD(TestMethod8)
{
expression = "(let a1 3 b2 (add a1 1) b2)";
auto res = Solution().evaluate(expression);
AssertEx(4, res);
}
};
}

复制代码

扩展阅读

视频课程

有效学习：明白的目标实时的反馈拉伸区（难度符合），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相干下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对各人说的话《喜缺全书算法册》以原理、正确性证明、总结为主。闻缺陷则喜是一个美好的愿望，早发现题目，早修改题目，给老板节约钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。如果步伐是一条龙，那算法就是他的是睛测试情况

操纵体系：win7 开发情况： VS2019 C++17
或者操纵体系：win10 开发情况： VS2022 C++17
如无特别说明，本算法用**C++**实现。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

【栈】736. Lisp 语法解析

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云