数据结构与算法-(7)---栈的应用拓展-前缀表达式转换+求值

 

 🌈write in front🌈
🧸大家好,我是Aileen🧸.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流.
🆔本文由Aileen_0v0🧸 原创 CSDN首发🐒 如需转载还请通知⚠️
📝个人主页:Aileen_0v0🧸—CSDN博客
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​
📣系列专栏:Aileen_0v0🧸的PYTHON学习系列专栏——CSDN博客
🗼我的格言:"没有罗马,那就自己创造罗马~" 

目录

回顾+思路讲解

(1)中缀表达式转前缀 

(2) 前缀表达式求值


 

回顾+思路讲解

之前我们介绍过了什么是后缀表达式,以及它如何通过中缀表达式进行转换,以及关于后缀表达式的求值问题,如有遗忘👉🔗http://t.csdnimg.cn/Hl4Y9

今天我们拓展一下,前缀表达式的转换和求值问题

💫中缀转后缀表达式的思路:

从左到右扫描逐个字符扫描中缀表达式的过程中,采用一个栈来暂存未处理的操作符
这样,栈顶的操作符就是最近暂存进去的,当遇到一个新的操作符,就需要跟栈顶的操作符比较下优先级,再行处理--->新符号和栈顶对比,新的高,就入栈(因为取时也先取);       新的低,就把栈顶出栈,让栈顶的先运算

想要了解具题后缀的相关知识点点击👉🔗http://t.csdnimg.cn/9100K

中缀转前缀思路也类似,不过 

中缀表达式中运算符的优先级和结合性需要考虑,从左往右扫描的话,需要对每个运算符的优先级和结合性进行判断,才能决定是否需要先进行计算。这样会增加算法的复杂度。

从右往左扫描,则可以利用栈的特性,遇到运算符时先将其压入栈中,再比较栈顶运算符的优先级和结合性,来决定是否需要先进行计算。这样可以简化算法,提高效率。另外,从右往左扫描还可以处理右结合性的运算符。

 参考后缀表达式代码思路:

我们利用一个栈来进行中缀表达式转前缀表达式的操作。其中prec{}是一个字典,用于记录操作符的优先级,优先级由低到高依次为1~3。opStack是我们初始化的操作符栈,prefixList是用于储存前缀表达式的空列表。

我们首先将中缀表达式解析为一个tokenList列表,并反转该列表,这样我们就可以正向扫描这个列表。

在扫描过程中,对于每个操作数token,我们需要分别处理三种情况:

  1. 操作数--将其添加到前缀表达式列表prefixList中。
  2. 右括号--将其压入操作符栈opStack中。
  3. 左括号--从操作符栈opStack中弹出并返回顶部元素topToken,直到遇到右括号为止。期间,将所有弹出的操作符添加到前缀表达式列表prefixList中。

对于第4种情况---操作符,

我们需要通过while循环语句比较操作符的优先级。

如果当前操作符的优先级小于等于栈顶操作符的优先级,我们就将栈顶操作符弹出并添加到前缀表达式列表prefixList中。然后将当前操作符压入操作符栈opStack中

(1)中缀表达式转前缀 

class Stack :def __init__(self):self.items = []def isEmpty(self):return self.items == []def push(self,item):self.items.append(item)def pop(self):return  self.items.pop()def peek(self):return self.items[len(self.items) - 1]def size(self):return len(self.items)def infix_to_prefix(infix_expr):# 定义一个空字典prec{}--记录操作符优先级  -- 优先级由低到高是1~3prec = {}prec["*"] = 3prec["/"] = 3prec["+"] = 2prec["-"] = 2prec[")"] = 1opStack = Stack()#初始化操作符栈#初始化列表用于储存前缀表达式prefixList = []#将中缀表达式解析为一个 tokenList 列表,并反转该列表tokenList = infix_expr.split()[::-1]#利用split切割成一个一个,然后通过切片转置到列表里#列表的元素为:c +  ) B + A (  遇到右括号入栈,左计算for token in tokenList:#若token是操作数---添加到列表if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":prefixList.append(token)# )---压入操作符栈elif token == ")":opStack.push(token)# (---从操作符栈opStack中弹出并返回顶部元素topTokenelif token == "(":topToken = opStack.pop()#当topToken不是")"while topToken != ")":prefixList.append(topToken)topToken = opStack.pop()# 若token是操作符,通过while循环语句比较他们的优先级,大的操作符添加到式子末端else:while (not opStack.isEmpty()) and \(prec[opStack.peek()] > prec[token]):#opStack.pop()会直接把栈顶元素弹出并返回prefixList.append(opStack.pop())opStack.push(token)#扫描完后将栈中的元素弹出while not opStack.isEmpty():#  操作符prefixList.append(opStack.pop())#  将后缀表达式通过切片转置合成前缀表达式字符串return " ".join(prefixList[::-1])
print(infix_to_prefix("A + B * C "))

(2) 前缀表达式求值

def postfix_eval(prefix_expr):operandStack = Stack()tokenList = prefix_expr.split()for token in reversed(tokenList):if token in "0123456789":#遇到操作数,入栈operandStack.push(int(token))else:operand2 = operandStack.pop()operand1 = operandStack.pop()result = doMath(token,operand1,operand2)operandStack.push(result)return operandStack.pop()def doMath(op, op1, op2):if op == "*":return op1 * op2elif op == "/":return op1 / op2elif op == "+":return op1 + op2else:return op1 - op2print(doMath("*", 11, 11))

定义两个函数:postfix_eval()doMath()

postfix_eval()函数接受一个前缀表达式,将其转换为后缀表达式并计算结果。

在计算过程中,它先将操作数入栈,然后遇到运算符就弹出栈顶的两个元素进行计算,并将计算结果重新入栈。最终,栈中仅剩下一个元素,即表达式的计算结果。

doMath()函数用于执行基本的数学运算,包括加、减、乘、除。

程序的最后一行在调用doMath()函数,并输出结果。用于计算11乘以11的结果。

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

带IV的分组加密下密文分散存储且存在混淆密文片段的多项式时间解密方案

在使用带IV的分组加密模式下,考虑这样一个场景:分组加密后,每组密文都被分散保存,且在恢复的时候,每组密文会和n个混淆的密文一起提供,此时,若想完整的恢复明文,需要一个多项式时间的…

UDP 协议

UDP协议特点: 无连接:只需要知道对方的IP和端口就可以向对方发送数据。 不可靠:没有确认应答机制,没有重传机制。 面向数据报:每调用一次sendto() ,就直接将这些数据交给网络层了,不能控制数据读…

双十一限时优惠!沃通SSL证书、代码签名证书年度好价

2023年11月01日至11月11日,沃通2023“双十一限时特惠”活动,精选9款SSL证书、国密SSL证书、代码签名证书产品推出年度好价,部分SSL证书产品低至5折,更有EV代码签名证书爆款特惠!多种数字证书一站式采购,解决…

改进YOLOv3!IA-YOLO:恶劣天气下的目标检测

恶劣天气条件下从低质量图像中定位目标还是极具挑战性的任务。现有的方法要么难以平衡图像增强和目标检测任务,要么往往忽略有利于检测的潜在信息。本文提出了一种新的图像自适应YOLO (IA-YOLO)框架,可以对每张图像进行自适应增强,以提高检测…

电源控制系统架构(PCSA)之电源管理软件

下图显示了电源管理软件栈的简化表示。该图说明了OS电源管理框架、具有直接从SCP请求操作功能的组件以及它们与SCP固件之间的关系。 一个重要的方面是,所有硬件电源管理操作都是由SCP代表这些请求者执行的。 这种OS电源管理(OSPM)的简化表示可以分为两部分&#xff…

MySQL -- 表的增删查改

MySQL – 表的增删查改 文章目录 MySQL -- 表的增删查改一、Create创建1.插入数据2.插入否则更新3.替换 二、Retrieve查找1.select列1.1.全列查询1.2.指定列查询1.3.查询字段为表达式1.4.为查询结果指定别名1.5.结果去重 2.where条件2.1.英语不及格的同学&#xff08;英语<6…

数字孪生三剑客!云渲染及虚拟仿真服务器产品MapGIS Server for Unreal来了

10月18日&#xff0c;新一代全空间智能GIS平台的升级之作——MapGIS 10.6 Pro在深圳正式发布&#xff0c;整场发布会全空间GIS、智能GIS、信创GIS、全栈开发各维度创新一一揭晓&#xff0c;全空间一体化、深度融合云端的全系产品全面升级&#xff0c;科技盛宴、高潮迭起。其中尤…

STM智能小车——OLED实现测速小车

目录 1. 测速模块 2. 测试原理和单位换算 3. 定时器和中断实现测速开发和调试代码 4. 小车速度显示在OLED屏 1. 测速模块 用途&#xff1a;广泛用于电机转速检测&#xff0c;脉冲计数,位置限位等。有遮挡&#xff0c;输出高电平&#xff1b;无遮挡&#xff0c;输出低电平接线…

Ubuntu20.04操作系统安装及重中之重:系统分区

最近因为学习原因&#xff0c;需要将电脑设置为双系统&#xff0c;在windows10的系统下去安装Ubuntu操作系统。本来看网上相关的安装教程蛮多的&#xff0c;以为比较简单&#xff0c;结果一路过五关斩六将&#xff0c;坑的七零八落的&#xff0c;折腾了好久&#xff0c;才算安装…

知识图谱实战应用30-知识图谱在反欺诈情报分析项目中的应用实践

大家好,我是微学AI,今天给大家介绍一下知识图谱实战应用30-知识图谱在反欺诈情报分析项目中的应用实践,现代商业环境中,各类欺诈行为日益猖獗,严重影响企业的运营和社会秩序。传统的欺诈检测方法难以满足实时性和有效性方面的要求。本文介绍了采用知识图谱技术构建反欺诈情报…

Go学习第十五章——Gin参数绑定bind与验证器

Go web框架——Gin&#xff08;参数绑定bind与验证器&#xff09; 1 bind参数绑定1.1 JSON参数1.2 Query参数1.3 Uri绑定动态参数1.4 ShouldBind自动绑定 2 验证器2.1 常用验证器2.2 gin内置验证器2.3 自定义验证的错误信息2.4 自定义验证器 1 bind参数绑定 在Gin框架中&#…

x3daudio1 7.dll丢失怎么修复?多种x3daudio1 7.dll修复方法对比

x3daudio1_7.dll是Windows操作系统中的一个动态链接库文件&#xff0c;它主要负责处理音频相关的功能。当这个文件缺失或损坏时&#xff0c;可能会导致一些音频播放问题&#xff0c;如无声、杂音等。那么&#xff0c;x3daudio1_7.dll缺失的原因是什么呢&#xff1f;又该如何修复…

chorme安装esay scholar及chrome 无法从该网站添加应用、扩展程序和用户脚本解决方案

问题描述 如题&#xff0c;博主想安装easy scholar用于查询论文的分区&#xff0c;结果安装了半天一直出现chrome 无法从该网站添加应用、扩展程序和用户脚本解决方案的问题。 解决方案 先从这个网址下载&#xff1a;https://www.easyscholar.cc/download 然后对下载好的文…

处理固定资产折旧报错 AFAB “根据记帐循环, 您必须接下来对期间 001记帐”

会计在运用进行固定资产折旧时&#xff0c;发现有个报错“根据记帐循环, 您必须接下来对期间 001记帐”&#xff0c; 根据记帐循环, 您必须接下来对期间 001记帐 消息编号 AA683 诊断 不可以在指定的期间过帐折旧&#xff0c;因为此操作会遗漏过帐期间。 系统响应 该期间不能进…

损坏的视频不能观看,还能修复吗?

3-1 在日常的生活或者工作中&#xff0c;特别是做摄像工作的人&#xff0c;有一定的概率会遇到损坏的视频文件&#xff0c;比如相机突然断电、无人机炸机等&#xff0c;都有可能导致保存的视频文件损坏。 如果遇到这种情况&#xff0c;该如何修复这种损坏的视频文件&#xff…

菜单管理中icon图标回显

<el-table-column prop"icon" label"图标" show-overflow-tooltip algin"center"><template v-slot"{ row }"><el-icon :class"row.icon"></el-icon></template></el-table-column>

NlogPrismWPF

文章目录 Nlog&Prism&WPF日志模块实现原理添加配置注入服务应用测试其他模块怎么调用&#xff1f; Nlog&Prism&WPF 日志模块 介绍了为WPF框架Prism注册Nlog日志服务的方法 实现原理 无论是在WPF或者ASP.NET Core当中, 都可以使用ServiceCollection来做到着…

c#方法中的参数

无参 //无参数直接调用即可MethodWithoutParameters();/// <summary>/// 没有参数的方法/// </summary>private void MethodWithoutParameters(){Debug.Log("没有参数的方法");}有参 //有一个参数MethodWithOneParameters("我是参数");/// <…

标签推荐Top-N列表优化算法_朱小兵

2算法模型 2&#xff0e;1 Top-N推荐列表重排序算法

LeetCode 2402.会议室III ----堆+模拟

5e5 的st与ed 容易看出来是用堆来写的一道题目&#xff0c;一开始我只用了一个堆&#xff0c;出现了问题 问题就是当我们当前这个会议有多个可以选择的会议室可以选择的时候不一定选择那个最先结束的会议室而是应该选择可以选择的那些里面编号最小的那一个&#xff0c;因此我们…