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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/681467.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

软件需求分析文档(需求报告实际项目直接套用模板Word及软件全文档)

软件需求分析文档(需求报告实际项目直接套用模板Word及软件全文档)

目录 第1章 序言 第2章 引言 2.1 项目概述 2.1.1 项目背景 2.1.2 项目目标 2.2 编写目的 2.3 文档约定 2.4 预期读者及阅读建议 第3章 技术要求 3.1 软件开发要求 3.1.1 接口要求 3.1.2 系统专有技术 3.1.3 查询功能 3.1.4 数据安全 3.1.5 可靠性要求 3.1.6 稳定…
阅读更多...
Java面试题:解决Redis缓存击穿问题

Java面试题:解决Redis缓存击穿问题

缓存击穿 当一个key过期时,需要对这个key进行数据重建 在重建的时间内如果有大量的并发请求进入,就会绕过缓存进入数据库,会瞬间击垮DB 重建时间可能因为数据是多个表的混合结果需要分头统计而延长,从而更容易出现缓存击穿问题 缓存击穿的解决方案 添加互斥锁 先查询缓存…
阅读更多...
随身WiFi十大热门品牌优缺点分析！哪个品牌的随身wifi更值得买？随身wifi推荐测评！

随身WiFi十大热门品牌优缺点分析！哪个品牌的随身wifi更值得买？随身wifi推荐测评！

格行随身wifi 【品牌特点】&#xff1a;服务好&#xff0c;性价比高&#xff0c;随身WiFi行业的“海底捞” 【优点】&#xff1a;专注物联网行业15年&#xff0c;产品和服务双驱动&#xff0c;综合实力和客户口碑领先 【缺点】&#xff1a;产品相对聚焦&#xff0c;产品类型…
阅读更多...
JVM（Java虚拟机）、JMM（Java内存模型）笔记

JVM（Java虚拟机）、JMM（Java内存模型）笔记

面试常见&#xff1a; 请你谈谈你对JVM的理解?java8虚拟机和之前的变化更新?什么是OOM&#xff0c;什么是栈溢出StackOverFlowError? 怎么分析?JVM的常用调优参数有哪些?内存快照如何抓取&#xff1f;怎么分析Dump文件&#xff1f;谈谈JVM中&#xff0c;类加载器你的认识…
阅读更多...
家庭海外仓系统：做好标准化管理，小空间也能做出高收益

家庭海外仓系统：做好标准化管理，小空间也能做出高收益

家庭海外仓凭借其运营模式灵活&#xff0c;合作成本低的独有特点&#xff0c;还是被很多跨境卖家所接受的。不过家庭海外仓的盈利也面临着一些问题。 首先&#xff0c;家庭海外仓的仓储空间有限&#xff0c;很难通过规模效应放大收益。家庭海外仓通常只能存储少量货物&#xf…
阅读更多...
[leetcode hot 150]第一百零八题，将有序数组转换为二叉搜索树

[leetcode hot 150]第一百零八题，将有序数组转换为二叉搜索树

题目&#xff1a;给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 平衡二叉搜索树。 给定一个有序的整数数组,我们需要构建一棵平衡的二叉搜索树。平衡二叉树是指任意一个节点的左右子树的高度差不超过1。 由于给定的数组是有序的…
阅读更多...
SpringBoot前端URL访问本地磁盘文件

SpringBoot前端URL访问本地磁盘文件

SpringBoot前端通过 URL访问本地磁盘文件&#xff0c;其实就是 SpringBoot访问web中的静态资源的处理方式。 SpringBoot 访问web中的静态资源&#xff1a;https://blog.csdn.net/qq_42402854/article/details/90295079 首先&#xff0c;我们知道浏览器访问本地磁盘文件的方式为…
阅读更多...
免费的维吾尔语翻译器：维汉翻译通App，最近新增了什么功能呢？让我们一起来看看！好用的维语翻译工具支持语音评分功能、支持汉语查拼音等等。

免费的维吾尔语翻译器：维汉翻译通App，最近新增了什么功能呢？让我们一起来看看！好用的维语翻译工具支持语音评分功能、支持汉语查拼音等等。

“阿拉伯语是知识&#xff0c;波斯语是糖&#xff0c;印度语是盐&#xff0c;而维吾尔语则是艺术。” 这是一句流传在西域的古老谚语&#xff0c;它不仅道出了维吾尔语言的独特魅力&#xff0c;也表达了人们对语言艺术的无限热爱。 而今&#xff0c;我们带着这份热爱&#x…
阅读更多...
揭秘2024最新版会声会影旗舰版本功能，下载即享专业编辑

揭秘2024最新版会声会影旗舰版本功能，下载即享专业编辑

在如今这个数字化时代&#xff0c;视频编辑已经成为了许多人生活中不可或缺的一部分。无论是专业的影视制作人员&#xff0c;还是普通的短视频爱好者&#xff0c;都希望能够找到一款功能强大、操作简便的视频编辑软件。而今天&#xff0c;我要为大家介绍的这款产品——会声会影…
阅读更多...
python中return语句的用法

python中return语句的用法

一、了解函数的标准格式 def 函数名(参数1, 参数2, ...&#xff0c;参数n):函数体第一行代码函数体第二行代码函数体第三行代码...return 语句变量 函数名(参数1&#xff0c;参数2&#xff0c;...&#xff0c;参数n) python遇到return语句时&#xff0c;会结束整个函数调用&a…
阅读更多...
高效数据处理的前沿：【C++】、【Redis】、【人工智能】与【大数据】的深度整合

高效数据处理的前沿：【C++】、【Redis】、【人工智能】与【大数据】的深度整合

目录 1.为什么选择 C 和 Redis&#xff1f; 2.人工智能与大数据的背景 1.大数据的挑战 2.人工智能的需求 3.C 与 Redis 的完美结合 1.安装 Redis 和 Redis C 客户端 2.连接 Redis 并进行数据操作 高级数据操作 列表操作 哈希操作 4.与大数据和人工智能结合 5.实际应…
阅读更多...
Jan任意文件读取/下载和上传漏洞

Jan任意文件读取/下载和上传漏洞

自从ChatGPT横空出世以来&#xff0c;我一直想找一个可以自己训练的AI大模型&#xff0c;然而在使用Jan的过程中&#xff0c;数据包中传递的参数引起了我的兴趣&#xff0c;简单尝试后发现了任意文件读取和任意文件上传漏洞。 简介 Jan是ChatGPT的开源替代品&#xff0c;它在…
阅读更多...
八、细化XML语句构建器，完善静态SQL解析

八、细化XML语句构建器，完善静态SQL解析

这一节主要是优化XML解析SQL部分&#xff0c;流程大概为&#xff1a; 1.XMLConfigBuilder解析配置文件&#xff0c;先解析数据源信息&#xff0c;然后再解析SQL信息&#xff0c;拿到mapper元素下的地址 2.XMLMapperBuilder对上面拿到的mapper地址进行处理&#xff0c;根据标签…
阅读更多...
什么是 LLM 大模型训练，详解 Transformer 结构模型

什么是 LLM 大模型训练，详解 Transformer 结构模型

1.模型/训练/推理知识介绍 深度学习领域所谓的“模型”&#xff0c;是一个复杂的数学公式构成的计算步骤。为了便于理解&#xff0c;我们以一元一次方程为例子解释&#xff1a; y ax b复制代码 该方程意味着给出常数 a、b 后&#xff0c;可以通过给出的 x 求出具体的 y。比…
阅读更多...
风机5G智能制造工厂工业物联数字孪生平台，推进制造业数字化转型

风机5G智能制造工厂工业物联数字孪生平台，推进制造业数字化转型

风机5G智能制造工厂工业物联数字孪生平台&#xff0c;推进制造业数字化转型。在信息化、智能化的浪潮中&#xff0c;风机5G智能制造工厂工业物联数字孪生平台正以其独特的优势&#xff0c;推动制造业实现数字化转型。数字孪生平台不仅为风机制造业带来了前所未有的机遇&#xf…
阅读更多...
【力扣刷题 动态规划】LeetCode 139 单词拆分、LeetCode 300 最长递增子序列 ✌

【力扣刷题 动态规划】LeetCode 139 单词拆分、LeetCode 300 最长递增子序列 ✌

文章目录 1. 单词拆分2. 最长递增子序列 1. 单词拆分 题目链接 &#x1f34e; 解题思路&#xff1a; class Solution {bool dp[310] {false};public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> myset;for(auto& str :…
阅读更多...
香橙派 AIpro 的系统评测

香橙派 AIpro 的系统评测

0. 前言 你好&#xff0c;我是悦创。 今天受邀测评 Orange Pi AIpro开发板&#xff0c;我将准备用这个测试简单的代码来看看这块开发版的性能体验。 分别从&#xff1a;Sysbench、Stress-ng、PyPerformance、RPi.GPIO Benchmark、Geekbench 等方面来测试和分析结果。 下面就…
阅读更多...
使用Flask框架在Python中获取HTTP请求头信息

使用Flask框架在Python中获取HTTP请求头信息

目录 引言 一、Flask框架简介 二、获取HTTP请求头的方法 三、案例分析 案例一&#xff1a;基于请求头进行用户身份验证 案例二&#xff1a;基于请求头的内容类型处理不同格式的响应 四、总结 引言 在Web开发领域&#xff0c;HTTP协议是客户端和服务器之间进行通信的基础…
阅读更多...
Linux 内核优化：提升性能测试效率的关键步骤

Linux 内核优化：提升性能测试效率的关键步骤

大家好&#xff0c;本文介绍了如何通过优化 Linux 内核配置来提高系统性能&#xff0c;特别是在进行性能测试时。从调整文件系统、网络参数到内核参数优化&#xff0c;我们将深入探讨每个关键步骤&#xff0c;以帮助你在性能测试中取得更好的效果。 在进行性能测试时&#xff0…
阅读更多...
OpenCV学习(4.3) 图像阈值

OpenCV学习(4.3) 图像阈值

1.目的 在本教程中&#xff1a; 你会学到简单阈值法&#xff0c;自适应阈值法&#xff0c;以及 Otsu 阈值法(俗称大津法)等。你会学到如下函数&#xff1a;**cv.threshold&#xff0c;cv.adaptiveThreshold** 等。 2.简单阈值法 此方法是直截了当的。如果像素值大于阈值&am…
阅读更多...
最新文章

Copyright @ 2022~2023