特投网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

(站外) 特投工作室

查看: 2303|回复: 0

中序表达式转后序表达式

[复制链接]

2145

主题

3139

帖子

5万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
57583
QQ
发表于 2015-6-10 21:12:39 | 显示全部楼层 |阅读模式

例如:中序表达式(23+34*45/(5+6+7))转换成后序表达式23 34 45 * 5 6 + 7 + / +

后序表达式用处

当转换成后序表达式后更方便计算表达式的值,如将后序表达式的元素依次进栈直到遇到运算符,这时候从栈中弹出两个元素,再结合运算符计算出这两个数运算的结果(如34*45=1530),将其结果压栈(此时栈元素为23 1530),然后继续将后序非符号元素压栈,直到遇到运算符。重复之前的操作。。。

InfixExp(中序表达式)转换PostfixExp(后序表达式)算法

1)当输入的是操作数时候,直接输出到后序表达式PostfixExp序列中

2)当输入开括号时候,把它压栈

3)当输入的是闭括号时候,先判断栈是否为空,若为空,则发生错误并进行相关处理。若非空,把栈中元素依次弹出并输出到Postfix中,知道遇到第一个开括号,若没有遇到开括号,也发生错误,进行相关处理

4)当输入是运算符op(+、- 、×、/)时候

a)循环,当(栈非空and栈顶不是开括号and栈顶运算符的优先级不低于输入的运算符的优先级)时,反复操作:将栈顶元素弹出并添加到Postfix中

b)把输入的运算符op压栈

5)当中序表达式InfixExp的符号序列全部读入后,若栈内扔有元素,把他们依次弹出并放到后序表达式PostfixExp序列尾部。若弹出的元素遇到空括号,则说明不匹配,发生错误,并进行相关处理


参考文献许卓群版《数据结构与算法》


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

您尚未登录,请登录后浏览更多精彩内容!
 立即注册
找回密码

QQ|Archiver|手机版|小黑屋|特投网 ( 皖ICP备13010674号-1 

GMT+8, 2021-3-7 16:46 , Processed in 0.186127 second(s), 34 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表