【栈】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++**实现。
相关文章:

【栈】736. Lisp 语法解析
本文涉及知识点 栈 LeetCode736. Lisp 语法解析 给你一个类似 Lisp 语句的字符串表达式 expression,求出其计算结果。 表达式语法如下所示: 表达式可以为整数,let 表达式,add 表达式,mult 表达式,或赋值的变量。表达…...

什么时候用C而不用C++?
做接口只用C,千万别要C。C是编译器敏感的,一旦导出的接口里有 std::string这些东西,以及类,注定了要为各个编译器的各个版本准备独立的库。 刚好我有一些资料,是我根据网友给的问题精心整理了一份「C的资料从专业入门…...
unix环境编程编程扫描版:深度解析与实践指南
unix环境编程编程扫描版:深度解析与实践指南 在探索Unix环境编程的广阔天地时,我们如同行走在一条充满未知与奇遇的旅程中。本篇文章将从四个方面、五个方面、六个方面和七个方面,深入剖析Unix环境编程的精髓,帮助读者在编程的海…...

2024年6月8日 每周新增游戏
中医百科中药: 中医百科中药是一款非常强大的中药知识科普软件,该应用提供500多味中草药的文献资料,强大的搜索功能可根据功效、特点和关键词来快速查找中药,而且每味中药的图片、功效、主治、炮制方法等百科知识,可以很好的帮助你…...
AI提示词Prompts有没有好公式?( 计育韬老师高校公益巡讲答疑实录2024)
这是计育韬老师第 8 次开展面向全国高校的新媒体技术公益巡讲活动了。而在每场讲座尾声,互动答疑环节往往反映了高校师生当前最普遍的运营困境,特此计老师在现场即兴答疑之外,会尽量选择有较高价值的提问进行文字答疑梳理。 *本轮巡讲主题除了…...

一个 buffer 使用的负反馈实例
端到端拥塞控制其实就是负反馈的实施。典型的做法是识别到一系列标志性事件,比如丢包,时延增加等,然后对这些事件做反应,进而形成负反馈,但 inflight 守恒是一种完全不同的做法,它将负反馈平铺到了整个传输…...

小程序简单版录音机
先来看看效果 结构 先来看看页面结构 <!-- wxml --><view class"wx-container"><view id"title">录音机</view><view id"time">{{hours}}:{{minute}}:{{second}}</view><view class"btngroup"…...

苹果手机微信如何直接打印文件
在快节奏的工作和生活中,打印文件的需求无处不在。但你是否曾经遇到过这样的困扰:打印店价格高昂,让你望而却步?今天,我要给大家介绍一款神奇的微信小程序——琢贝云打印,让你的苹果手机微信直接变身移动打…...
51.线程池大小
问题 1.线程池太小会导致程序不能充分利用系统资源、容易导致饥饿。 2.线程池过大导致更多的线程上下文切换,占用更多的内存。 情况一:CPU密集型运算 应用程序是做一些数据分析,需要大量的使用cpu,程序代码全部都是跟cpu相关的࿰…...
Python | 开房门(map)
常把map称之为映射,就是将一个元素(通常称之为key键)与一个相对应的值(通常称之为value)关联起来 通常用**字典dict**实现了映射这种数据结构 字典也是使用{}来包裹(set也是{}),每…...
MATLAB 函数 function
函数定义函数调用局部函数匿名函数函数句柄子函数函数文件的位置函数的文档函数的参数函数的返回值总结 在 MATLAB中,函数是一个执行特定任务的代码块,可以被重复调用。 MATLAB函数可以执行计算、数据操作、文件处理等任务,并且可以接收输入…...

基于阿里云服务网格流量泳道的全链路流量管理(三):无侵入式的宽松模式泳道
作者:尹航 在前文《基于阿里云服务网格流量泳道的全链路流量管理(一):严格模式流量泳道》、《基于阿里云服务网格流量泳道的全链路流量管理(二):宽松模式流量泳道》中,我们介绍了流…...

9行超强代码用Python工具快速获取放假日期
9行超强代码用Python工具快速获取放假日期 在很多场景下,我们需要获知国内具体的节假日安排情况,而国内每一年具体的放假安排以及调休情况,都依赖于国务院发布的具体公告,如果不想自己手动整理相关数据的话,我们可以用Python来快速获取最新的放假日期. 可以通过调用公开的 API…...

Elastic Search(ES)Java 入门实操(2)搜索代码
上篇解释了 ES 的基本概念和分词器。Elastic Search (ES)Java 入门实操(1)下载安装、概念-CSDN博客 Elastic Search(ES)Java 入门实操(3)数据同步-CSDN博客 这篇主要演示 Java 整合…...
Hudi Spark Sql Procedures 回滚 Hudi 表数据
前言 因为有 Hudi Rollback 的需求,所以单独总结 Hudi Spark Sql Procedures Rollback。 版本 Hudi 0.13.0(发现有bug)、(然后升级)0.14.1Spark 3.2.3Procedures 官方文档:https://hudi.apache.org/docs/procedures 相关阅读:Hudi Spark SQL Call Procedures学习总结…...
【重学C语言】十九、SDL2 图形化编程的使用
【重学C语言】十九、SDL2 图形化编程的使用 SDL2 的第一个程序渲染器纹理渲染1. 纹理的概念2. 加载纹理3. 渲染纹理4. 纹理设置和查询5. 纹理渲染流程6. 注意事项SDL2_imageSDL2 的第一个程序 #define SDL_MAIN_HANDLED #include <SDL.h>int main(int argc, char* argv[…...

什么是电风扇行情?
“电风扇行情” 是一个金融术语,用于描述证券市场中价格上下波动频繁、幅度较大,但总体趋势不明显的市场状况。 其名称来源于电风扇的扇叶在旋转时,风向不断变化的特征,形象地比喻了市场价格频繁变动但没有明确方向的情景。 …...
pytho入门教程
文章目录 随机数据生成的方式list操作方式数据操作方式处理缺失数据数据框操作方式画图的方式 随机数据生成的方式 # 随机生成数据的方式 # 1. 随机生成10-20之间的浮点数 holdForce random.uniform(10,20) # print(holdForce)# 2.for循环输出50个数据的方式 # for i in rang…...

Elasticsearch:ES|QL 查询 TypeScript 类型(二)
在我之前的文章 “Elasticsearch:ES|QL 查询 TypeScript 类型(一)”,我们讲述了如何在 Nodejs 里对 ES|QL 进行查询。在今天的文章中,我们来使用一个完整的例子来进行详细描述。更多有关如何使用 Nodejs 来访问 Elasti…...
元音 (音标) 和元音字母的区别
元音 [音标] 和元音字母的区别 1. 音位 (phoneme)1.1. Correspondence between letters and phonemes 2. 元音 (vowel)3. 辅音 (consonant)3.1. Consonant sounds and consonant letters 4. 元音字母 (vowel letter)References 1. 音位 (phoneme) https://en.wikipedia.org/wi…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...