前缀中缀后缀表达式介绍_chengqiuming的博客-程序员宅基地_前缀表达式中缀表达式后缀表达式

技术标签: 算法  数据结构与算法  

一 前缀表达式

1 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前。

2 举例

 (3+4)×5-6 对应的前缀表达式是: - × + 3 4 5 6

3 前缀表达式的计算机求值过程

从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 和 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。

例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:

第一步:从右至左扫描,将6、5、4、3压入堆栈

第二步:遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素),计算出3+4的值,得7,再将7入栈。

第三步:接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈。

第四步:最后是-运算符,计算出35-6的值,即29,由此得出最终结果。

二 中缀表达式

中缀表达式注意下面两点。

1 中缀表达式就是常见的运算表达式,如(3+4)×5-6。

2 中缀表达式的求值是我们人最熟悉的,但是对计算机来说却不好操作,因此,计算结果时,往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式)。

三 后缀表达式 

1 后缀表达式又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后。

2 后缀表达式举例

(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

3  后缀表达式的计算机求值

从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下。

第一步:从左至右扫描,将3和4压入堆栈。

第二步:遇到+运算符,弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈。

第三步:将5入栈。

第四步:接下来是×运算符,弹出5和7,计算出7×5=35,将35入栈。

第五步:将6入栈。

第六步:最后是-运算符,计算出35-6的值,即29,由此得出最终结果。

四 中缀表达式转后缀表达式

后缀表达式适合计算机进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将中缀表达式转成后缀表达式。

中缀表达式转后缀表达式具体步骤如下:

1 初始化两个栈:运算符栈s1和储存中间结果的栈s2。

2 从左至右扫描中缀表达式。

3 遇到操作数时,将其压s2;

4 遇到运算符时,比较其与s1栈顶运算符的优先级:

4.1 如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈。

4.2 否则,若优先级比栈顶运算符的高,也将运算符压入s1。

4.3 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到4.1与s1中新的栈顶运算符相比较。

5 遇到括号时,分下面两种情况进行处理。

5.1 如果是左括号“(”,则直接压入s1。

5.2 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃。

6 重复步骤2至5,直到表达式的最右边。

7 将s1中剩余的运算符依次弹出并压入s2。

8 依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式。

举例说明

将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下

结果为"1 2 3 + 4 × + 5 –"

 

 

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/chengqiuming/article/details/114441652

智能推荐

python label怎么用_labelImg安装使用教程_weixin_39574869的博客-程序员宅基地

系统环境:win10 64位,Python3.51、安装Python3.5不要用3.6,到目前为止,当执行 from lxml import etree 时,会失败,目前没有解决办法。这里推荐一篇文章,Windows10下python3和python2同时安装2、安装PyQt5进入cmd后,输入: pip install PyQt5此处有坑,基本上这条命令执行后,因网络问题会出现执行不成功的情况注...

python @修饰符_Python基础(面向对象之类成员与修饰符)_weixin_39774491的博客-程序员宅基地

本篇将介绍Python 类的成员、类成员修饰符、类的特殊成员。类的成员可以分为三大类:字段、方法、属性1、字段:也可理解为变量,分为:普通字段:保存在对象中,访问时通过“对象.字段名”访问。静态字段:保存在类中,访问时通过“类.字段名”访问。例子:class Person(object): #继承object类说明是一个新式类country = 'China' #静态字段de...

怎么将c语言应用程序做成界面,用C语言编的图形界面应用程序_prosoo的博客-程序员宅基地

/*************wan nian li*****************************/setcolor(RED);settextstyle(0,0,4);for(j=15;j>=0;j-=2){delay(1000000);outtextxy(j+10,j+50,\"Wan\");}for(j=15;j>=0;j-=2){delay(1000000);outte...

Ubuntu linux更改IP,Linux Ubuntu下IP的查看跟修改_徐瑞涛的博客-程序员宅基地

Linux Ubuntu下IP的查看和修改>>查看IP.>ifconfig -aeth0 Link encap:Ethernet HWaddr 08:00:27:a8:00:8cinet addr:10.0.2.15 Bcast:10.0.2.255 Mask:255.255.255.0inet6 addr: fe80::a00:27ff:fea8:8c/64 S...

java axis 调用wsdl_axis使用WSDL2Java方式调用WebService_蒋大钳的博客-程序员宅基地

1 WSDL2Java基于x5_biz_integration案例,不清楚这个案例的请先看1.1 切换到java视图1.2 右键菜单->运行方式->运行配置1.3 左边选择”应用程序”,新建1.4 主要->项目:x5_biz_integration->main类:WSDL2Java1.5 自变量->程序自变量:-o src -p demo http://localh...

PTA(java)爬动的蠕虫_山东大学-苏苏的博客-程序员宅基地

作者: C课程组单位: 浙江大学时间限制: 400ms内存限制: 64MB代码长度限制: 16KB7-6 爬动的蠕虫(15 分)一条蠕虫长1寸,在一口深为N寸的井的底部。已知蠕虫每1分钟可以向上爬U寸,但必须休息1分钟才能接着往上爬。在休息的过程中,蠕虫又下滑了D寸。就这样,上爬和下滑重复进行。请问,蠕虫需要多长时间才能爬出井?这里要求不足1分钟按1分钟计,并且假定只要在某次上爬过程中蠕虫的头部到...

随便推点

mysql long类型格式_MySQL 数据类型_weixin_39715460的博客-程序员宅基地

MySQL 的数值数据类型可以大致划分为两个类别,一个是整数,另一个是浮点数或小数。许多不同的子类型对这些类别中的每一个都是可用的,每个子类型支持不同大小的数据,并且 MySQL 允许我们指定数值字段中的值是否有正负之分或者用零填补。表列出了各种数值类型以及它们的允许范围和占用的内存空间。类型 大小范围(有符号)...

如何在MapReduce中使用Avro数据格式?_木木统的博客-程序员宅基地

本文转载自:http://blog.itpub.net/31077337/viewspace-2214709/本文作为《Hadoop从入门到精通》大型专题的第三章后续,主要是对前一章中所提及的Protocol Buffers概念的补充以及如何在MapReduce中使用Avro数据格式。Avro改进了Protocol Buffers,因为其代码生成是可选的,并且以容器文件格式嵌入模式,允许...

狗狗的年龄的python编程_狗狗的年龄怎么算|人和狗狗年龄对照表_weixin_39646725的博客-程序员宅基地

1.狗出生后20天时具有跟人类1岁幼儿相同的机能。2.出生3个月时跟人类的5岁幼儿一样,而智慧也增加到与幼儿园的儿童或小学1年级学生相似。3.出生后的6个月已相当于人类的10岁了,但身体已生长完成,有些品种的狗以后则很少会再长大了。4.出生后1年是约等于人类的18岁,这时不论是雌雄都具有生殖能力,尤其雌犬则已有发情出血现象。5.虽然狗的平均寿命只有15岁,但已经等于人的79岁老人了,也可以说是高寿...

nmap命令_白帽子黑客教你:如何用Nmap探测目标主机操作系统类型?_weixin_39602569的博客-程序员宅基地

课前声明:1、本分享仅做学习交流,请自觉遵守法律法规!2、课程讲师实时交流和在线答疑微信:ihaha12一、背景介绍nmap是一个网络连接端扫描软件,用来扫描网上电脑开放的网络连接端。确定哪些服务运行在哪些连接端,并且推断计算机运行哪个操作系统(这是亦称 fingerprinting)。它是网络管理员必用的软件之一,以及用以评估网络系统安全。正如大多数被用于网络安全的工具,nmap也是不...

贪婪算法_找零钱问题_学习记录_guozhu_zhu的博客-程序员宅基地

贪婪算法_找零钱问题_学习记录package p33;import java.util.Scanner;/** * 贪婪算法-解决找零钱问题 * @author Guozhu Zhu * @date 2018/8/30 * @version 1.0 * */public class Test10 { public static int max = 10; ...

python基于摄像头的手势识别_基于python的kinect手势识别:hmm学习_weixin_39861882的博客-程序员宅基地

我想用kinect在python中进行手势识别。在在阅读了一些理论之后,我认为最好的方法之一是用隐马尔可夫模型(HMM)(baum-welch或其他EM方法)对一些已知的手势数据进行无监督学习,得到一组经过训练的HMM(我想识别的每个手势对应一个)。在然后我会进行匹配最大对数似然的识别(用viterbi?)在训练集中使用HMM的观测数据。在例如,我用kinect设备记录了一些手势的数据(右手坐标x...

推荐文章

热门文章

相关标签