`
sxpyrgz
  • 浏览: 72501 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

逆波兰表达式算法

    博客分类:
  • java
阅读更多

逆波兰表达式
逆波兰表达式又叫做后缀表达式。在通常的表达式中,运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家 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",根据算法可以得出stackOperatorreversePolishExpression值的变化过程:

扫描     操作   
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)入栈

计算完成时,栈内只有一个操作数,这就是表达式的结果:14

转载地址:http://hi.baidu.com/johnsoncr/blog/item/99e270d35831b4d2a9ec9a03.html

分享到:
评论
2 楼 sxpyrgz 2011-11-22  
openFox 写道
温故而知新啊 大学的都快忘记了

呵呵,很多东西是理论结合实际应用才记得捞
1 楼 openFox 2011-11-21  
温故而知新啊 大学的都快忘记了

相关推荐

    逆波兰表达式算法_表达式_

    - `ExpressionParserUtil.java` 文件可能包含了逆波兰表达式算法的具体实现,包括一个类`ExpressionParserUtil`,以及可能的解析、计算等方法。 - 类似的方法可能包括 `toPostfixExpression()`(将中缀表达式转换...

    表达式求值 逆波兰表达式算法 java版

    表达式求值 逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好

    逆波兰表达式实现

    逆波兰表达式实现 逆波兰表达式是一种后缀表达式,通常用于表示数学表达式的计算顺序。它的特点是运算符在后面,先计算括号里的运算,然后计算乘除,最后计算加减。逆波兰表达式的实现可以通过栈或队列来实现。 逆...

    逆波兰表达式及其算法实现

    ### 逆波兰表达式及其算法实现 #### 一、引言 逆波兰表达式(Reverse Polish Notation, RPN)是一种特殊的数学表达式表示方法,它最初由波兰逻辑学家Jan Łukasiewicz提出。与传统的中缀表达式相比,逆波兰表达式...

    基于逆波兰表达式的计算程序

    逆波兰表达式,又称后缀表达式,是一种用于表示数学计算的符号表示法。它将操作符放在操作数之后,避免了使用括号,简化了运算过程。在基于逆波兰表达式的计算程序中,通常包括以下几个核心知识点: 1. **逆波兰...

    转化为逆波兰表达式

    C语言:设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达式的值。数据结构实验

    逆波兰表达式

    总的来说,逆波兰表达式是计算机科学中解决计算问题的一种有效工具,它涉及到的数据结构和算法概念如堆栈、队列和链表,都是计算机科学基础中的核心知识点。理解并熟练运用这些知识对于编写高效的代码和解决问题至关...

    利用堆栈实现逆波兰表达式 后缀法

    ### 利用堆栈实现逆波兰表达式(后缀法) #### 一、逆波兰表达式简介 逆波兰表达式,又称后缀表达式或后缀记法,是一种没有括号且运算符位于操作数之后的数学表达式书写方式。在计算机科学中,这种表达式被广泛...

    逆波兰表达式的C++实现

    从传统的中缀表达式转换为逆波兰表达式,通常采用Dijkstra的Shunting Yard算法。该算法通过两个栈,一个用于存储操作符,另一个用于存储中间结果,逐步将中缀表达式转换为后缀表达式。在处理过程中,遇到数字则直接...

    逆波兰表达式求值源代码

    逆波兰表达式求值是计算机科学中的一个重要概念,主要用于避免使用括号来表示运算优先级,从而简化表达式的解析过程。逆波兰表达式,又称后缀表达式,是一种没有括号、无需考虑运算符优先级的数学表达式书写方式。在...

    将一个字符串转换为其逆波兰表达式

    4. 实现中缀表达式到逆波兰表达式的转换算法。 5. 输出生成的逆波兰表达式。 为了深入理解`inverse.c`的具体实现,你需要查看源代码并理解其中的逻辑。如果你需要进一步的帮助,比如代码分析或编程指导,随时告诉我...

    逆波兰表达式求解的程序(2种方法)

    逆波兰表达式,又称后缀表达式,是一种用于...总结,逆波兰表达式的求解涉及到数据结构(栈)、算法(递归下降解析)以及编程语言的基本操作。理解并掌握这两种方法,有助于深入理解计算机科学中的计算原理和算法设计。

    用java和逆波兰表达式写的计算器

    逆波兰表达式(Reverse Polish Notation,RPN)是一种数学表达式表示方法,它不需要使用括号,而是通过运算符后置的方式明确运算顺序。在RPN计算器中,运算符紧跟在其操作数之后,使得计算过程更为简洁。这种表示法...

    java逆波兰表达式【栈】完整版

    【数据结构与算法】逆波兰表达式完整版,使用java语言编写。逆波兰表达式又叫做后缀表达式,是一种没有括号,并严格遵循“从左到右”运算的后缀式表达方法

    易语言逆波兰表达式计算

    在编程领域,逆波兰表达式常用于表达式求值,因为其算法相对简单且效率高。易语言是一款中国本土的编程语言,旨在降低编程难度,提高开发效率。本篇将详细介绍易语言逆波兰表达式计算的相关知识。 1. **逆波兰...

    C++:中缀表达式转变为逆波兰表达式

    标题"中缀表达式转变为逆波兰表达式"涉及的主要知识点是中缀表达式到逆波兰表达式的转换算法,这通常使用两个栈来实现:一个运算符栈和一个临时结果栈。这个过程主要分为以下步骤: 1. 遍历中缀表达式中的每一个...

    libolan.rar_site:www.pudn.com_逆波兰_逆波兰式_逆波兰表达式

    逆波兰表达式的这种方法可以很容易地用算法实现,通常使用两个栈:一个用于存储操作数,另一个用于临时存储待处理的操作符。这种方式避免了中缀表达式解析时需要处理的优先级和括号问题,因此在某些计算和编译场景下...

    中缀表达式转化为逆波兰表达式

    中缀表达式和逆波兰表达式是两种不同的数学表达式表示方式,对于计算和解析有着不同的优势。本文将深入探讨如何将中缀表达式转化为逆波兰表达式,并结合C语言进行实现。 中缀表达式是我们日常生活中最常见的数学...

Global site tag (gtag.js) - Google Analytics