逆波兰表达式_逆波兰表达式gof是什么

逆波兰表达式_逆波兰表达式gof是什么逆波兰表达式表达式一般由操作数(Operand)、运算符(Operator)组成,例如算术表达式中,通常把运算符放在两个操作数的中间,这称为中缀表达式(InfixExpression),如A+B。波

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

逆波兰表达式

 
表达式一般由操作数(Operand)、运算符(Operator)组成,例如算术表达式中,通常把运算符放在两个操作数的中间,
这称为中缀表达式(Infix Expression),如A+B。
波兰数学家Jan Lukasiewicz提出了另一种数学表示法,它有两种表示形式:
把运算符写在操作数之前,称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression),如+AB;
把运算符写在操作数之后,称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression),如AB+;
其中,逆波兰表达式在编译技术中有着普遍的应用。
 
算法:
一、 将中缀表达式转换成后缀表达式算法:
1、从左至右扫描一中缀表达式。
2、若读取的是操作数,则判断该操作数的类型,并将该操作数存入操作数堆栈
3、若读取的是运算符
  (1) 该运算符为左括号”(“,则直接存入运算符堆栈。
  (2) 该运算符为右括号”)”,则输出运算符堆栈中的运算符到操作数堆栈,直到遇到左括号为止。
  (3) 该运算符为非括号运算符:
      (a) 若运算符堆栈栈顶的运算符为括号,则直接存入运算符堆栈。
      (b) 若比运算符堆栈栈顶的运算符优先级高或相等,则直接存入运算符堆栈。
      (c) 若比运算符堆栈栈顶的运算符优先级低,则输出栈顶运算符到操作数堆栈,并将当前运算符压入运算符堆栈。
4、当表达式读取完成后运算符堆栈中尚有运算符时,则依序取出运算符到操作数堆栈,直到运算符堆栈为空。
 
二、逆波兰表达式求值算法:
1、循环扫描语法单元的项目。
2、如果扫描的项目是操作数,则将其压入操作数堆栈,并扫描下一个项目。
3、如果扫描的项目是一个二元运算符,则对栈的顶上两个操作数执行该运算。
4、如果扫描的项目是一个一元运算符,则对栈的最顶上操作数执行该运算。
5、将运算结果重新压入堆栈。
6、重复步骤2-5,堆栈中即为结果值。
 
 
 

  C语言讲解【复合复制运算符】时会提到,复合运算简练并且产生机器码的效率高。为什么效率高呢,

这就必须要了解:【编译原理】中提到的【逆波兰式】。逆波兰表达式又叫做【后缀表达式】。推而广之必然还

存在【前缀表达式】、【中缀表达式。】(有时也成为,前序式,中序式,后序式)。中缀表达式就是我们常用的

所谓的标准的表达式如”A+B”,它在数学上学名叫中缀表达式(Infix Notation),原因是:

运算符号在两个运算对象的中间

      其优势: 在于只:用两种简单操作,入栈和出栈就可以搞定任何普通表达式(仅包含:+-*/和()的表达式)的运算。

      其基本运算方式 :如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。

      为什么说逆波兰式产生机器码的效率高因为逆波兰式非常易于计算机的处理。原因是这样的。举例:

     3   32   + 5 3   *   –
  12 34 2   –   *   8 /
  乍一看上面两个式子很奇怪,是吗?它们就是一种表达式的记法——逆波兰表达式。
  现在,准备一个很窄的圆筒逆波兰表达式_逆波兰表达式gof是什么,筒是有底的,像一个细长的杯子逆波兰表达式_逆波兰表达式gof是什么,粗细刚好和一枚硬币相当。再做几个和硬币一样大的小圆纸片逆波兰表达式_逆波兰表达式gof是什么,在纸片上依次写上“3”“32”“+”“5”“3”“*”“-”,记住,每个纸片上要么只写一个数,要么只写一个运算符号逆波兰表达式_逆波兰表达式gof是什么,把它们按上面的顺序排好。好,现在仔细听我说,按顺序一个接一个地拿起小圆纸片,反复执行以下几个规则:
  1. 如果你拿着的是一个数,不多说,直接把它放进圆筒;
  2. 如果你拿着的是一个运算符号,不要把它放进去。先从圆筒里取出两个数(当然是先取最上而的啦,筒很细的),然后处这两个数作运算符号指定的运算,并把结果写在一张新的纸片上,然后放进筒里。比如你拿着的是“+”,你要依次取出“32”和“3”,让它们相加,得“35”,把“35”写在一张新纸片上(现在“34”和“12”可以扔掉了),并把这张新纸片放进圆筒。
  当圆筒里只有一个数时,你就可以停下来了,我猜逆波兰表达式_逆波兰表达式gof是什么这个数是20,没错,这就是这个表达式的值!
  我们刚才操作的,其实就是一个“栈”,栈是一种数据结构逆波兰表达式_逆波兰表达式gof是什么,具有一个性质——后进先出(LIFO——Last Input First Output),你已经深有体会了,就像一摞盘子,你只能从最上面的开始取,放的时候也只能放在最上面。放进去的动作叫做“入栈”,取出来叫做“弹出”。以后你就可以把栈想像成一摞盘子,或是上面说的小圆筒和小纸片,栈就是这么简单逆波兰表达式_逆波兰表达式gof是什么
  逆波兰表达式虽然看起来比较繁琐,其实在计算机中很有用。计算机可不知道先乘除后加减,先括号内后括号外,它要把你输入的式子变成逆波兰表达式,它就可以不断地执行上面两个固定的规则,直至把结果算出来告诉你。逆波兰表达式_逆波兰表达式gof是什么编译器在处理时候按照从左至右的顺序读取逆波兰表达式,遇到运算对象直接压入堆栈,遇到运算符就从堆栈提取后进的两个对象进行计算,这个过程正好符合了计算机计算的原理。所以,逆波兰式非常适宜计算机的处理。

       那么,接下来的问题就是:

      将一个中缀表达式 转换成 逆波兰式的算法 结合一个具体例子分析如下:

a)给出一个中缀表达式1*(2+3)

 

b)系统先定义两个先进后出的堆栈:运算符号栈(简称入栈in),后缀表达式输出符号栈(简称出栈out)

 

c)系统按从左至右的顺序读取中缀表达式

 

d)读入数字直接压入出栈(out)

 

e)读入第一个运算符直接压入入栈(in)

 

f)读入”(”直接压入入栈(in)。 按上述规则读取若干次后,若,此时两栈的数据为: in 【*,( 】 ; out 【1,2】,开始读取的第二个的运算符”+”,并将之与入栈(in)中的栈顶运算符”(“进行比较,

g)高于栈顶运算符级别的算符直接进栈,低于或等于栈顶级别的要将入栈(in)解栈(即出栈),按次压入出栈(out)中。比如现在入栈的运算顺序为(,*,/,此时若系统读取的运算符为+,级别比/要低,此时要按/,*的顺序压入出栈out中,并在入栈中释放/和*符号,最后得到 in ( ; out /,*的结果。

f)最后读取”)”时要找到入栈in中最近的”(”,将其前面所有符号全部按后进先出的顺序压入出栈,并解压,”(”与”)”抵消。此时两栈的数据为:in 1,2,3,+ ; out *

 

g)系统读取中缀表达式结束后将入栈in中的所有符号按后进先出的顺序全部解压,并依次压入出栈out中,最后出栈的结果就应该为1,2,3,+,*

 

h)按先进先出的顺序将出栈out解压得到后缀标准表达式1,2,3,+,*

 

两个堆栈先后数据情况:

In

out

 

1

*

1

*,(

1

*,(

1,2

*,(,+

1,2

*,(,+

1,2,3

*

1,2,3,+

 

1,2,3,+,*

 

将中缀表达式转换成逆波兰表达式过程中,特别要注意对于中缀标到式中括号的处理

1、要注意的,如果算符是”(”,无论入栈中栈顶级别(只看栈顶)为何直接入栈,所以,“(”的等级

    只用于对其后入栈的算符进行优先级比较,在“(”入栈时是无视优先级的。

    注: 逆波兰用的优先级有以下几种:   等级从高–>低 是:   1、* \       2、+ –       3、(        4、)

2、在遇到”)”时候找到最后进入的”(”,并把”(”前面所有的符号都压入出栈。不能仅凭运算符的级别来判断。

 

将一个 逆波兰式 倒转回 中缀表达式 的算法:

   这个就相当简单了,就是一个机械的入堆栈出堆栈的操作,

1)设置一个堆栈,将逆波兰式从左到右开始进行出入堆栈操作,还以上例为例:1,2,3,+,*

2)遇到数字直接压栈;例如,上例逆波兰先进行三次入栈操作,堆栈的格局是: 1,2,3(栈顶);

3)遇到算符,将堆栈中的两个数字出栈。 如,读到+号后,2,3出栈,进行运算。注意,出栈时先出栈的元素是右算子,后出栈的是左算子,上例是2+3,不是3+2;

4)将运算的结果作为新的算子,压入堆栈中。如运算结果(2+3)入栈,堆栈格局:1,(2+3);

5)反复1-4的操作,得到的中序表达式就是: 1*(2+3);

   中序表式生成的逆波兰式唯一吗?:

是唯一的,和固定形式的中序表达式一一对应,但,请注意这个概念,

例如: a+(b-c)*d 和 (b-c)*d+a 和 a+d*(b-c) 的是完全一样的。但是,他们的中序形式不同,

产生的逆波兰式必然是不同的。

      a+(b-c)*d : abc-d*+

      (b-c)*d+a :   bc-d*a+

      a+d*(b-c) : adbc-*+

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166534.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Excel VBA 编程练习

    Excel VBA 编程练习根据表单名称从work查找

  • 程序员警句

    程序员警句

  • 嵌入式学习路线「建议收藏」

    嵌入式学习路线「建议收藏」嵌入式学习路线1.前言2.嵌入式硬件方向3.嵌入式软件方向4.嵌入式软件学习路线4.1.打好软件基础4.2.学习ARM体系结构编程4.3.嵌入式系统的构建4.4.嵌入式驱动程序的开发4.5.嵌入式应用程序的开发4.6.综合项目5.总结1.前言嵌入式技术是各种电子产品的核心技术,也是工业4.0、远程医疗、3D打印等新兴产业的核心技术,具有广阔的发展前景。很多计算机、电子信息类专业的学生都想把嵌入式开发作为自己的职业目标,但是因为嵌入式涉及的知识太多,太杂,太广,很多嵌入式初学者陷入嵌入式知识的海洋中,东学

  • SpringMVC+Spring+Mybatis实现登录注册Demo「建议收藏」

    SpringMVC+Spring+Mybatis实现登录注册Demo「建议收藏」使用环境:MyEclipse/Eclipse+Tomcat+MySql。使用技术:SpringMVC+Spring+Mybatis。实现效果登录页面:密码错误提示登录成功后注册注册成功目录结构一、配置文件beans.xml<?xmlversion=”1.0″encoding=”UTF-8″?><beansxmlns=”http://www.springframework.org/schema/beans”xmlns:x.

  • 计算机专业的男生喜欢你,男生暗恋你的20个动作 一秒看出他喜欢你

    计算机专业的男生喜欢你,男生暗恋你的20个动作 一秒看出他喜欢你很多女生想知道是不是有男生在暗恋自己,下面小编为大家介绍一下男生暗恋你的20个动作。1、眼睛总是忍不住盯着那个女生。2、在女生的面前会表现得特别活跃。3、在女生开心的时候会很开心,在女生伤心的时候,心情就会像乌云密布的天空。4、如果那个女生和其他男生表现得很要好,就会忍不住要吃醋。5、如果那个女生心情低落,就会想过去安慰她。6、对于女生所拜托的事情,就算再难做也会答应。7、女生一上Q,就会很兴奋,…

  • stata–异方差检验

    stata–异方差检验异方差检验有两种方法:1、残差图2、white检验1、残差图(一般不用这个,这个只是粗略)代码:regyfdirvfplot,yline(0)rvpplotfdi,yline(0)(1)对y和fdi回归:(2)画出残差与拟合值(ybar)散点图:(3)画出残差与fdi(自变量x)的散点图:2、white检验:代码:sscinstallwhitetstestatimtest,white…

    2022年10月28日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号