数据结构与算法-(7)---栈的应用-(3)表达式转换

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

目录

​编辑

​编辑

回顾 🧸

​编辑

中缀表达式🀄

全括号表达式与前后缀表达式的关系🎡

中缀表达式转换为前后缀形式的方法🪐

通用的中缀转后缀算法⭐

利用中缀转后缀的操作流程🪂

转成后缀表达式对应的代码🚀



 

回顾 🧸

"温故而知新"

通过思维导图回顾一下我们学了什么,我们先学了什么是线性结构,栈(Stack)是一种抽象数据类型的线性结构,栈是什么,栈的特点以及操作步骤,我们还可以通过列表去实现栈,不过不同的栈顶其对应的时间复杂度也不同,了解完栈的基础知识点后我们开始学习栈的应用,栈可以用于

(1)匹配符号(Balance Symbols),

    (2)进制转换(Decimal conversion),

    (3)表达式转换(Experssion conversion)」

(1) 和 (2) 我们已经在前面的文章写过了:不记得知识点或者对前面内容感兴趣的小伙伴可以点击👉

🔗(1)http://t.csdnimg.cn/Ypv3q

🔗(2)http://t.csdnimg.cn/OLIJW

对应专栏数据结构与算法学习系列专栏🌸🔗:http://t.csdnimg.cn/6BQDo

中缀表达式🀄

我们通常看到的表达式如:B*C , 很容易就知道是B乘以C

像  这种操作符( operator ) 介于操作数 ( operand )中间的表示法,称为 "中缀" 表示法.

But sometimes 中缀表示法会 case confusion(引起混淆),如 "A + B * C"

是A+B然后再乘以C  还是B*C然后再加A?

为了消除混淆,人们引入"优先级"的概念

规定高优先级的操作符先计算
相同优先级的操作符从左到右依次计算这样A+B*C就没有疑义是A加上 B与C的乘积
同时
引入了括号来表示强制优先级括号的优先级最高,而且在嵌套的括号中,内层的优先级更高这样(A+B)*C就是A与B的和再乘以C


全括号表达式与前后缀表达式的关系🎡

虽然人们已经习惯了这种表示法,但计算机处理最好是能明确规定所有的计算顺序,这样无需处理复杂的优先规则
于是,我们引入全括号表达式:

在所有的表达式项两边都加上括号A+B*C+D,应表示为((A+(B*C))+D)
可否将表达式中操作符的位置稍移动一下?

例如中缀表达式A+B操作符移到前面,变为"+AB"
或者将
操作符移到最后,变为“AB+
我们就得到了表达式的另外两种表示法:"
前缀"和“后缀”表示法以操作符相对于操作数的位置来定义

这样A+B*C将变为前缀的"+A*BC"后缀的"ABC*+"为了帮助理解,子表达式加了下划线

前缀和后缀表达式中,操作符的次序完全决定了运算的次序,不再有混淆

所以在很多情况下,表达式在计算机中的表示都避免使用复杂的中缀形式

让我们先看看这些前中缀和后缀表达式

中缀表达式前缀表达式后缀表达式
A + B * C + D+ + A * B C DA B C * + D +
( A + B ) * ( C + D )* + A B + C DA B + C D + *
A * B + C * D+ * A B * C DA B * C D * +
A + B + C + D+ + + A B C DA  B + C + D +

想必初看的小伙伴会觉得眼花缭乱,但是不要着急,我们接下来会一一讲解.

一定得有个算法来转换任意复杂的表达式

为了分解算法的复杂度,我们从“全括号中缀表达式入手我们看A+B*C

如果写成全括号形式:(A+(B*C)),显式表达了计算次序我们注意到每一对括号,都包舍了一组完整的操作符和操作数,让我们看看如何将其转换成前后缀表达式吧~


中缀表达式转换为前后缀形式的方法🪐

✨Summary:

        (1)将中缀表达式转换为全括号形式

        (2)将所有的操作符移动到子表达式所在的 左括号(前缀prefix) 或者 右括号(后缀postfix) 处~

              替代之,再删除所有的括号.


通用的中缀转后缀算法⭐

在中缀表达式转换为后缀形式的处理过程中,操作符比操作数要晚输出

所以在扫描到对应的第二个操作数之前,需要把操作符先保存起来


而这些暂存的操作符,由于优先级的规则还有可能要反转次序输出.

在A+B*C中,+虽然先出现,但优先级比后面这个*要低,所以它要等*处理完后,才能再处理.


这种反转特性,使得我们考虑用保存暂时未处理操作符

再看看(A+B)*C,对应的后缀形式是AB+C*
这里+的输出比*要早,主要是因为括号使得+的优先级提升,高于括号之外的*


根据上面的“全括号”表达式,后缀表达式中操作符应该出现在左括号对应的右括号位置

所以遇到左括号,要标记下,其后出现的操作符优先级提升了,一旦扫描到对应的右括号,就可以马上输出这个操作符

总结:

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

利用中缀转后缀的操作流程🪂

后面的算法描述中,约定中缀表达式是由空格隔开的一系列单词(token)构成

操作符单词包括*/+-()

操作数单词则是单字母标识符A、B、C等。

1.首先,创建空栈opstack用于暂存操作符空表postfixList用于保存后缀表达式

2.将中缀表达式转换为单词(token)列表

    A + B*C = split => ['A', '+', 'B', ' * ', 'C']

图解: 

转成后缀表达式对应的代码🚀

class Stack:#Stack---->ADTdef __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 infixToPostfix(infixexpr):# 记录操作符优先级prec = {}prec["*"] = 3prec["/"] = 3prec["+"] = 2prec["-"] = 2prec["("] = 1opStack = Stack()postfixList = []# 解析表达式到列表tokenList = infixexpr.split()for token in tokenList:# 操作数if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":postfixList.append(token)#  (elif token == "(":opStack.push(token)#  )elif token == ")":topToken = opStack.pop()while topToken != '(':postfixList.append(topToken)topToken = opStack.pop()# 操作符else:while (not opStack.isEmpty()) and \(prec[opStack.peek()] >= prec[token]):postfixList.append(opStack.pop())opStack.push(token)while not opStack.isEmpty():#  操作符postfixList.append(opStack.pop())#  合成后缀表达式字符串   return " ".join(postfixList)
print(infixToPostfix("A + B * C "))

运行代码测试结果 :

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

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

相关文章

【刷题笔记10.2】LeetCode: 罗马数字转整数

LeetCode: 罗马数字转整数 一、题目描述 二、分析 方法一: 将给定字符串s中的"IV", “IX”, “XL”, “XC”, “CD”, “CM” 全部替换为其他字符如:a, b, c, d, e, f 这种,然后就可以遍历累加了。 s s.replace("IV",…

Grafana 开源了一款 eBPF 采集器 Beyla

eBPF 的发展如火如荼,在可观测性领域大放异彩,Grafana 近期也发布了一款 eBPF 采集器,可以采集服务的 RED 指标,本文做一个尝鲜介绍,让读者有个大概了解。 eBPF 基础介绍可以参考我之前的文章《eBPF Hello world》。理…

Linux命令(二)(文件相关)

目录可以更快找到你想要的命令 1. 命令入门2. 文件(touch、vim、cat、more、mv)touch:用于创建空文件与修改时间戳选项用例 vim:文本编辑工具(三种模式)1. 命令模式:2. 插入模式3. 底线命令模式 cat:在终端…

网站使用SSL证书是趋势吗?

随着互联网技术的不断发展,网络安全问题日益受到重视。其中,SSL证书作为网站安全的基石,其重要性不言而喻。SSL证书能够加密网站与用户之间的通信,保护用户隐私,防止信息被窃取和篡改。因此,越来越多的网站…

Android 性能优化—— 启动优化提升60%

应用启动速度 一个应用App的启动速度能够影响用户的首次体验,启动速度较慢(感官上)的应用可能导致用户再次开启App的意图下降,或者卸载放弃该应用程序 本文将从两个方向优化应用的启动速度 : 1.视觉体验优化 2.代码逻辑优化 视觉优化 应用程序启动有…

KNN(下):数据分析 | 数据挖掘 | 十大算法之一

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据…

初识Java 12-1 流

目录 Java 8对流的支持 流的创建 随机数流 int类型的区间范围 generate() iterate() 流生成器 Arrays 正则表达式 本笔记参考自: 《On Java 中文版》 ||| 流的概念:流是一个与任何特定的存储机制都没有关系的元素序列。 流与对象的成批处理有关…

链表经典面试题(二)

返回中间结点 1.中间结点的题目2.中间结点的图文分析3.中间结点的基本代码4.中间结点的优化代码 1.中间结点的题目 2.中间结点的图文分析 方法1:先求整体长度,再除以2,所得到的就是中间结点 方法2:双指针法,快指针走两…

读者写者问题—内含408真题

读者写者问题—含408 一、问题描述 一个数据问价或记录可以被多个进程共享,我们把只读该文件的进程称为“读者进程”,其他进程为“写者进程”。允许多个进程同时读一个共享对象,但不允许一个写者进程和其他写者进程或读者进程同时访问共享对…

使用ElementUI结合Vue完善主页的导航菜单和书籍管理以及后台数据分页查询

目录 动态树 数据表 案列 书籍管理 动态树 动态树(Dynamic tree)是一种数据结构,它可以在树中动态地插入、删除和修改节点。与静态树不同,静态树的节点是固定的,一旦构建完成就无法再进行修改。而动态树可以在运行时…

Leetcode 1239. 串联字符串的最大长度

文章目录 题目代码&#xff08;9.29 首刷部分看解析&#xff09; 题目 Leetcode 1239. 串联字符串的最大长度 代码&#xff08;9.29 首刷部分看解析&#xff09; class Solution { public:unordered_set<int> skip;unordered_set<char> used;int maxLength(vecto…

cesium 雷达扫描 (线行扩散效果)

cesium 雷达扫描 (线行扩散效果) 1、实现方法 使用ellipse方法加载圆型,修改ellipse中material方法来实现效果 2、示例代码 2.1、 <!DOCTYPE html> <html lang="en"><head><<

Edge扩展插件推荐专业视频下载器

专业视频下载器&#xff0c;这款扩展插件非常好用&#xff0c;强烈推荐。只要能打开的视频&#xff0c;都能下载。 安装完成是这样的&#xff1a; 有用记得点赞。

在linux下预览markdown的方法,转换成html和pdf

背景 markdown是一种便于编写和版本控制的格式&#xff0c;但却不便于预览——特别是包含表格等复杂内容时&#xff0c;单纯的语法高亮是远远不够的——这样就不能边预览边调整内容&#xff0c;需要找到一种预览方法。 思路 linux下有个工具&#xff0c;叫pandoc&#xff0c…

日期范围搜索

1.日期范围选择界面 <?xml version"1.0" encoding"utf-8"?> <ScrollViewandroid:layout_width"fill_parent"android:layout_height"fill_parent"xmlns:android"http://schemas.android.com/apk/res/android">…

mysql面试题6:MySQL索引的底层原理,是如何实现的?B+树和B树的区别?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:MySQL索引的底层原理,是如何实现的? MySQL索引的底层实现是通过B+树来实现的。B+树是一种多叉平衡查找树,它的特点是能够高效地支持数据的插入…

简历项目优化关键方法论-START

START方法论是非常著名的面试法则&#xff0c;经常被面试官使用的工具 Situation:情况、事情、项目需求是在什么情况下发生Task:任务&#xff0c;你负责的做的是什么Action:动作&#xff0c;针对这样的情况分析&#xff0c;你采用了什么行动方式Result:结果&#xff0c;在这样…

设计模式8、装饰者模式 Decorator

解释说明&#xff1a;动态地给一个对象增加一些额外的职责。就扩展功能而言&#xff0c;装饰模式提供了一种比使用子类更加灵活的替代方案 抽象构件&#xff08;Component&#xff09;&#xff1a;定义一个抽象接口以规范准备收附加责任的对象 具体构件&#xff08;ConcreteCom…

八、3d场景的区域光墙

在遇到区域展示的时候我们就能看到炫酷的区域选中效果&#xff0c;那么代码是怎么编辑的呢&#xff0c;今天咱们就好好说说&#xff0c;下面看实现效果。 思路&#xff1a; 首先&#xff0c;光墙肯定有多个&#xff0c;那么必须要创建一个新的js文件来作为他的原型对象。这个光…

unity打包工具

接手了一个项目&#xff0c;打包存在重大问题&#xff0c;故此在unity addressables 基础上弄了一个简单的打包工具&#xff0c;代码也都做好了注释&#xff0c;操作非常简单以下为操作方法&#xff1a; 首先设置导入Addressables插件&#xff0c;并设置好详细参见&#xff1a…