• 【栈】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 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++**实现。

  • 相关阅读:
    [ CTF 学习 ] CTF 中的隐写集合 —— 图片隐写术
    VoIP之前向纠错(FEC)
    8051开发实例-实现红外寻迹小车
    Django基础之django模型层(一)单表操作
    windows安装composer并更换国内镜像
    三江城115m²3室2厅2卫,现代简约不单是居所更是对生活的向往。福州中宅装饰,福州装修
    从Docker初识K8S
    大数据ClickHouse进阶(五):副本与分片
    推荐几款比较使用的idea插件
    P1113 杂务题解
  • 原文地址:https://blog.csdn.net/he_zhidan/article/details/139172905