- 浏览: 47178 次
- 性别:
- 来自: 未来
文章分类
最新评论
-
lurenjiaxxy:
我这边测下来可是StringUtils比较快,StringUt ...
apache的replace,trim方法 StringUtils.replace(),StringUtils.trimWhitespace() java原生 -
cgddm:
...
apache的replace,trim方法 StringUtils.replace(),StringUtils.trimWhitespace() java原生
逆波兰表达式 计算完成时,栈内只有一个操作数,这就是表达式的结果:14
逆波兰表达式又叫做后缀表达式。在通常的表达式中,运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家 J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法,每一运算符都置于其运算对象之后,故称为后缀表示。
逆波兰表达式,它的语法规定,表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍,下面是一些例子:
正常的表达式 逆波兰表达式
a+b ---> a,b,+
a+(b-c) ---> a,b,c,-,+
a+(b-c)*d ---> a,b,c,-,d,*,+
a+d*(b-c) ---> a,d,b,c,-,*,+
逆波兰表达式的用途
它的优势在于只用两种简单操作,入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下: 按顺序扫描逆波兰表达式,如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元
素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。
中序表达式转换为逆波兰表达式
1、建立运算符栈stackOperator用于运算符的存储,此运算符在栈内遵循越往栈顶优先级越高的原则。
2、预处理表达式,正、负号前加0(如果一个加号(减号)出现在最前面或左括号后面,则该加号(减号) 为正负号) 。
3、顺序扫描表达式,如果当前字符是数字(优先级为0的符号),则直接输出该数字;如果当前字符为运算符或括号(优先级不为0的符号),则判断第4点 。
4、若当前运算符为'(',直接入栈;
若为')',出栈并顺序输出运算符直到遇到第一个'(',遇到的第一个'('出栈但不输出;
若为其它,比较stackOperator栈顶元素与当前元素的优先级:如果栈顶元素是'(',当前元素入栈;如果栈顶元素 >= 当前元素,出栈并顺序输出运算符直到 栈顶元素 < 当前元素,然后当前元素入栈; 如果 栈顶元素 < 当前元素,直接入栈。
5、重复第3点直到表达式扫描完毕。
6、顺序出栈并输出运算符直到栈元素为空。
上面的算法比较抽象,下面来个实际例子:
写一个方法,参数传递一个字符串表达式,返回结果为表达式计算结果。
如:传递表达式"5 + ((1 + 2) * 4) − 3"返回计算的结果。
1.将中缀表达式转换为逆波兰表达式
1)建立一个运算符栈stackOperator用来存放运算符;建立一个字符串链表reversePolishExpression用来存放逆波兰表达式
2)顺序扫描"5 + ((1 + 2) * 4) − 3",根据算法可以得出stackOperator及reversePolishExpression值的变化过程:
扫描 操作 stackOperator值 reversePolishExpression值 注释
5 输出 空 5 当前字符是数字直接输出该数字
+ 入栈 + 5 栈顶元素为空,不用比较,入栈
( 入栈 ( 5 当前运算符为'(',直接入栈
( 入栈 ( ( 5 当前运算符为'(',直接入栈
1 输出 ( ( 5 1 当前字符是数字直接输出该数字
+ 入栈 ( ( + 5 1 + 优先级< 栈顶元素 ( ,入栈
2 输出 ( ( + 5 1 2 当前字符是数字直接输出该数字
) 出栈 ( 5 1 2 + 出栈并顺序输出运算符直到遇到第一个'('
* 入栈 ( * 5 1 2 + * 优先级< 栈顶元素 ( ,入栈
4 输出 ( * 5 1 2 + 4 当前运算符为'(',直接入栈
) 输出 空 5 1 2 + 4 * 出栈并顺序输出运算符直到遇到第一个'('
- 入栈 - 5 1 2 + 4 * 栈顶元素为空,不用比较,入栈
3 输出 - 5 1 2 + 4 * 3 当前字符是数字直接输出该数字
最后 输出 空 5 1 2 + 4 * 3 - 顺序出栈并输出运算符直到栈元素为空
下表给出了该逆波兰表达式从左至右求值的过程,堆栈栏给出了中间值,用于跟踪算法。
输入
操作
堆栈
注释
5
入栈
5
1
入栈
5, 1
2
入栈
5, 1, 2
+
加法运算
5, 3
(1, 2)出栈;将结果(3)入栈
4
入栈
5, 3, 4
*
乘法运算
5, 12
(3, 4)出栈;将结果(12)入栈
+
加法运算
17
(5, 12)出栈;将结果 (17)入栈
3
入栈
17, 3
−
减法运算
14
(17, 3)出栈;将结果(14)入栈
发表评论
-
quartz的定时配置表达式
2012-04-10 14:26 1201ava服务自带了定时服务Timer,不过我在研究spring, ... -
Spring JMS 整合Tomcat和ActiveMQ
2012-03-15 14:45 13271.Active MQ安装配置 1.1.下载并解压Active ... -
java 动态添加方法和属性
2012-02-27 17:07 0Java字节码操纵框架 :ASM 和 javassist -
oracle的体系
2012-02-03 13:41 692一:oracle体系 oracle的体系很庞大,要学习它,首 ... -
oracle数据备份
2012-02-02 13:52 728ORACLE 备份三种方法: 1. imp(导入),e ... -
项目预警管理
2012-02-01 15:39 66010个项目死亡的信号:(1)第一版做太多功能;(2)太依赖新技 ... -
spring视频
2012-01-13 16:55 0http://www.verycd.com/topics/93 ... -
不错的架构选择
2012-01-07 11:36 0我心目中最好的框架组合是: 表示层:spring mv ... -
JAVA学习之路
2011-12-12 15:49 721JAVA是一种平台,也是一 ... -
ORACLE函数大全
2011-12-09 18:05 670SQL中的单记录函数1.ASCII返回与指定的字符对应的十 ... -
职位要求
2011-12-08 09:24 0架构师 职位描述: 1、 发展应用开发框架和开发工具 ... -
其他一些东西
2011-12-07 15:09 0解压:tar Zxvf FileName.tar.Z ... -
oracle解决死锁
2011-11-28 14:49 759--第一步:查看是否有死锁存在,查出有数据则代表有死锁 s ... -
oracle 字符串加密算法
2011-11-28 11:34 22141、方法一 MD5加密 Java代码 ... -
JAVA程序员的25个标准
2011-11-26 15:52 7761) 你需要精通面向对象分析与设计(OOA/O ... -
计算机试题
2011-11-22 00:09 728一、选择题(每题1.5分 ... -
程序员做业余项目
2011-11-17 23:17 0编程是一种创造过程,业余项目允许程序员在没有截止日期或各 ... -
各种框架
2011-11-17 23:00 0restlet框架(Restlet项目为“建立REST概念与J ... -
仿百度文库
2011-11-16 15:13 868前向公司有个业务需求,是关于ISO的文件管理! 客户的要求:跟 ... -
几本有用的电子书
2011-11-16 14:35 749一下几个电子书,相信对初学者绝对有帮助,有兴趣的朋友可以去 ...
相关推荐
C语言:设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达式的值。数据结构实验
逆波兰表达式_课程设计.doc 逆波兰表达式_课程设计.doc
易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言...
逆波兰表达式的C++实现,用类封装,用于计算逆波兰表达式
以字符串的形式输入一个算术表达式,转换为逆波兰表达式,并求取其数值。
逆波兰表达式及其算法实现 很好的资料 里面分析很全面
C语言之逆波兰表达式完整代码(附算法),详细讲解其实现
是个人上数据结构课后,通过4天努力写出的代码文章,可能不是很好,但可用来参考参考!
逆波兰表达式的长 度不超过一行,以 "$"作为输入结束,操作数之间用空格分隔,操作符只可能有+、—、*、/四种 运算。例如: 23434 + 2*$。 数据结构作业
【数据结构与算法】逆波兰表达式完整版,使用java语言编写。逆波兰表达式又叫做后缀表达式,是一种没有括号,并严格遵循“从左到右”运算的后缀式表达方法
基于c语言的将算术中缀表达式转化为逆波兰表达式,注释清晰且代码打头有写好的思想。
中缀表达式转换成逆波兰表达式、c语言编写、用栈来实现
使用c语言实现,将给定的运算表达式翻译成逆波兰表达式的形式
对逆波兰表达式的解释与求解方法,运行平台支持c/c++或者是Linux系统都可以。
表达式求值,逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好
根据逆波兰表达式将各序表达式显示出来,并且将二叉树输出
计算字符串形式的逆波兰表达式(即两个操作数在前,计算符在后)。本题内,保证每个操作数均为1位数。操作符有'+','-','*','/'四种。且保证计算过程中除法运算全部为整数除法,结果为整数。 如23+4*,,结果20
将任意字符串转换为其逆波兰表达式,然后打印出来。
表达式求值 逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好