中缀表达式转换为后缀表达式(栈的使用)

中缀表达式如1*2+(2-1), 其运算符一般出现在操作数之间, 因此称为中缀表达式,也就是大家编程中写的表达式。编译系统不考虑表达式的优先级别, 只是对表达式从左到右进行扫描, 当遇到运算符时, 就把其前面的两个操作数取出, 进行操作。为达到上述目的, 就要将中缀表达式进行改写,变为后缀表达式 如上面的表达式1*2+(2-1), 就变为12*21-+;后缀表达式中不含有括号, 且

大家好,又见面了,我是全栈君。

中缀表达式如1*2+(2-1), 其运算符一般出现在操作数之间, 因此称为中缀表达式,也就是大家编程中写的表达

式。编译系统不考虑表达式的优先级别, 只是对表达式从左到右进行扫描, 当遇到运算符时, 就把其前面的两

个操作数取出, 进行操作。为达到上述目的, 就要将中缀表达式进行改写,变为后缀表达式 如上面的表达式

1*2+(2-1), 就变为12*21-+;

后缀表达式中不含有括号, 且后缀表达式的操作数和中缀表达式的操作数排列次序完全相同, 只是运算符的

次序发生了改变。我们实现的时候,只需要用一个特定工作方式的数据结构(栈),就可以实现。

其中stack op;用来存放运算符栈。数组ans用来存放后缀表达式。

算法思想:

从左到右扫描中缀表达式,是操作数就放进数组ans的末尾。

如果是运算符的话,分为下面3种情况:

1)如果是‘(’直接压入op栈。

2)如果是‘)’,依次从op栈弹出运算符加到数组ans的末尾,知道遇到’(’;

3) 如果是非括号,比较扫描到的运算符,和op栈顶的运算符。如果扫描到的运算符优先级高于栈顶运算符

则,把运算符压入栈。否则的话,就依次把栈中运算符弹出加到数组ans的末尾,直到遇到优先级低于扫描

到的运算符或栈空,并且把扫描到的运算符压入栈中。

就这样依次扫描,知道结束为止。

如果扫描结束,栈中还有元素,则依次弹出加到数组ans的末尾,就得到了后缀表达式。

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

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

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

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

(0)


相关推荐

  • 【elasticsearch系列】windows安装IK分词器插件[通俗易懂]

    【elasticsearch系列】windows安装IK分词器插件[通俗易懂]环境github下载:https://github.com/medcl/elasticsearch-analysis-ik/releases注意,IK分词器插件要与ES版本保持一致;有的小伙伴在GitHub上下载插件时,没有发现与ES相对应的版本,可以切换到Tags中选择分支版本;例如Branchs列表中仅可能存在主版本号;切换到右侧Tags中查找对应的版本即可;小编这里选择的7.8.0的版本;安装IK解压缩后拷贝到ElasticSearch安装目录的plugins文件夹下,默认情况该

  • Java – DOM4J解析XML文件[通俗易懂]

    Java – DOM4J解析XML文件[通俗易懂]XML简单理解和解析

  • 激活windows 10

    激活windows 10企业版1、鼠标右键点击window键,点击”windowpowershell(管理员)”,进入管理员命令行。2、输入以下命令,进行删除密钥slmgr.vbs/upk此时弹出窗口显示“已成功卸载了产品密钥”。3、接着输入以下命令:密钥可以自己网上找对应的版本,可以更换slmgr/ipkNPPR9-FWDCX-D2C8J-H872K-2YT43弹出窗口提示:“成功的安装了产品密钥”。4、继续输入以下命令:slmgr/skmszh.us.to#这个名

  • 青蛙过河谁先过_python knn算法实现

    青蛙过河谁先过_python knn算法实现一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。开始时, 青蛙默认已站在第一块石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格 1 跳至单元格 2 )。如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k – 1、k 或 k + 1 个单位。 另请注意

  • php rdkafka_php rdkafka

    php rdkafka_php rdkafkaKafka是一种分布式的,基于发布/订阅的消息系统。在使用PHP处理Kafka消息的时候需要使用一个PHP的扩展php-rdkafka下面将介绍一下如何在Linux/MacOS下安装php-rdkafka在使用php-rdkafka之前需要先安装好librdkafkaisaClibraryimplementationoftheApacheK…

    2022年10月14日
  • 使用tinyxml2库解析xml

    使用tinyxml2库解析xmltinyxml2简介tinyxml2是c++编写的轻量级的xml解析器,而且是开放源代码的,在一些开源的游戏引擎中用的比较多。源码托管在github上。源码地址:https://github.com/leethomason/tinyxml2tinyxml2使用起来非常简单,下载源码后无需编译成lib文件,直接將tinyxml2.h和tinyxml2.cpp两个文件添加到你自己的工程中即可。

发表回复

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

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