IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构学习笔记——前、中、后缀表达式的转换(栈的应用) -> 正文阅读

[数据结构与算法]数据结构学习笔记——前、中、后缀表达式的转换(栈的应用)

一、前、中、后缀表达式定义

一般我们常用的中缀表达式,中缀表达式不仅依靠运算符的优先级,也要处理括号的优先级;后缀表达式中没有括号,只有操作数和运算符,且运算符放在操作数的后面;前缀表达式也是一种没有括号的算术表达式,其运算符写在前面,操作数写在后面。
在这里插入图片描述
将常用的中缀表达式转换为前缀表达式、后缀表达式后,可以通过栈的相关原理来实现具体的出栈 、入栈操作逻辑,从而可以一样完成与中缀表达式相同的运算。

二、具体转换步骤

(一)中缀表达式转换为前缀表达式

以a+b-c*d为例,将中缀表达式转换为前缀表达式。

1、首先按照运算优先级将所有的操作数都加上括号
在这里插入图片描述
2、将运算符移至相对应的括号
在这里插入图片描述
3、将括号去掉,即可得到前缀表达式。
在这里插入图片描述

(二)中缀表达式转换为后缀表达式

与前缀表达式相反,第二步将运算符移至相对应的括号后,然后再去掉括号,如下图:
在这里插入图片描述
这里以中缀表达式转换为后缀表达式,简单讲解具体的栈的实现方法:
1、将一个中缀表达式转换为后缀表达式,首先从左到右扫描整个中缀表达式,当遇到操作数时加入至待定的后缀表达式区域中(这是一个栈);
2、遇到操作符时,若为’(‘,则入栈,若为’)',则依次将栈中的运算符加入至后缀表达式的栈中,直到出现‘(’后,从栈中删除‘(’;
3、遇到运算符时,当为比括号优先级高的优先级时,直接入栈,否则,依次从栈中弹出比当前运算符优先级高和优先级相等的运算符,直到遇到比它优先级低或者遇到一个‘(’为止;
4、当扫描完结束后,栈中的所有运算符依次出栈加入后缀表达式。
在这里插入图片描述
通过手工算,第一步转换为(a+((b-(c*d))/e)),第二步提运算符转为(a((b(cd)*)-e)/)+,去掉括号得到后缀表达式abcd*-e/+
在这里插入图片描述
通过手工算,第一步转换为((A+B(-((C*D)/E)+F),第二步提运算符转为((AB)+(((CD)*E/)-F)+,去掉括号得到后缀表达式AB+CD*E/-F+

例题

例1、表达式a*(b+c)-d的后缀表达式是________。

首先第一步,加上括号得:((a*(b+c))-d)
然后由于是转为后缀表达式,将符号提至对应的括号后,得:((a(bc)+)*d)-
括号去掉,即可得到后缀表达式:abc+*d-

例2、求表达式a / b + (c * d-e * f) / g的前缀表达式。

第一步也是加上括号:((a/b)+(((c*d)-(e*f))/g))
然后由于是转为前缀表达式,将符号提至对应的括号前,得:+(/(ab)/(-(*(cd)*(ef))g))
括号去掉,即可得到前缀表达式:+/ab/-*cd*efg

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-06-29 19:19:22  更:2022-06-29 19:22:24 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 23:20:21-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码