【栈】736. Lisp 语法解析
本文涉及知识点栈
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 += 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) {
if ("" != strVarName)
{
iRet = m_mVar.top();
}
for (auto var : vars) {//变量出栈
m_mVar.pop();
}
iPos++;
returniRet;
}
vars.emplace_back(strVarName);
const int cur = GetNum1(iPos);
m_mVar.emplace();
m_mVar.top() = cur;
iPos++;
}
}
void IgronSpace(int& iPos) {
if((iPos < m_exp.length())&&(' ' == m_exp)){iPos++;};
}
int GetNum1(int& iPos) {
string strName = ParseName(iPos);
if ("" != strName) { return m_mVar.top(); }
return ParseNum(iPos);
}
string ParseName(int& iPos) {
string strName;
while ((isalpha(m_exp))||(strName.size() && isalnum(m_exp))) {
strName += m_exp;
}
return strName;
}
int ParseNum(int& iPos) {
int num = 0;
if ('(' == m_exp) { return Parse(iPos); }
int iSign = 1;
if ('-' == m_exp) {
iSign = -1; iPos++;
}
while (isdigit(m_exp)) {
num = num*10+ (m_exp-'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, v2);
}
}
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, vv2);
}
}
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);
}
};
}
https://img-blog.csdnimg.cn/8d37dcd13ddb4df9af8f95fefd86828d.gif#pic_center#pic_center
扩展阅读
视频课程
有效学习：明白的目标 实时的反馈 拉伸区（难度符合），可以先学简单的课程，请移步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++**实现。
https://img-blog.csdnimg.cn/f95ddae62a4e43a68295601c723f92fb.gif#pic_center
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]