做视频网站对服务器要去,昆山网站建设哪里好,申请商标注册,华为云速建站模板本文涉及知识点
栈
LeetCode736. Lisp 语法解析
给你一个类似 Lisp 语句的字符串表达式 expression#xff0c;求出其计算结果。 表达式语法如下所示: 表达式可以为整数#xff0c;let 表达式#xff0c;add 表达式#xff0c;mult 表达式#xff0c;或赋值的变量。表达…本文涉及知识点
栈
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_mapstring,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);vectorstring 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_mapstring, stackint m_mVar;string m_exp;
};单元测试
templateclass T1,class T2
void AssertEx(const T1 t1, const T2 t2)
{Assert::AreEqual(t1 , t2);
}templateclass T
void AssertEx(const vectorT v1, const vectorT v2)
{Assert::AreEqual(v1.size(), v2.size()); for (int i 0; i v1.size(); i){Assert::AreEqual(v1[i], v2[i]);}
}templateclass T
void AssertV2(vectorvectorT vv1, vectorvectorT 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
