逆波兰表达式
逆波兰表达式又叫做后缀表达式。在通常的表达式中,运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家 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)入栈 |
计算完成时,栈内只有一个操作数,这就是表达式的结果:14
转载地址:http://hi.baidu.com/johnsoncr/blog/item/99e270d35831b4d2a9ec9a03.html
分享到:
相关推荐
- `ExpressionParserUtil.java` 文件可能包含了逆波兰表达式算法的具体实现,包括一个类`ExpressionParserUtil`,以及可能的解析、计算等方法。 - 类似的方法可能包括 `toPostfixExpression()`(将中缀表达式转换...
表达式求值 逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好
逆波兰表达式实现 逆波兰表达式是一种后缀表达式,通常用于表示数学表达式的计算顺序。它的特点是运算符在后面,先计算括号里的运算,然后计算乘除,最后计算加减。逆波兰表达式的实现可以通过栈或队列来实现。 逆...
### 逆波兰表达式及其算法实现 #### 一、引言 逆波兰表达式(Reverse Polish Notation, RPN)是一种特殊的数学表达式表示方法,它最初由波兰逻辑学家Jan Łukasiewicz提出。与传统的中缀表达式相比,逆波兰表达式...
逆波兰表达式,又称后缀表达式,是一种用于表示数学计算的符号表示法。它将操作符放在操作数之后,避免了使用括号,简化了运算过程。在基于逆波兰表达式的计算程序中,通常包括以下几个核心知识点: 1. **逆波兰...
C语言:设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达式的值。数据结构实验
总的来说,逆波兰表达式是计算机科学中解决计算问题的一种有效工具,它涉及到的数据结构和算法概念如堆栈、队列和链表,都是计算机科学基础中的核心知识点。理解并熟练运用这些知识对于编写高效的代码和解决问题至关...
### 利用堆栈实现逆波兰表达式(后缀法) #### 一、逆波兰表达式简介 逆波兰表达式,又称后缀表达式或后缀记法,是一种没有括号且运算符位于操作数之后的数学表达式书写方式。在计算机科学中,这种表达式被广泛...
从传统的中缀表达式转换为逆波兰表达式,通常采用Dijkstra的Shunting Yard算法。该算法通过两个栈,一个用于存储操作符,另一个用于存储中间结果,逐步将中缀表达式转换为后缀表达式。在处理过程中,遇到数字则直接...
逆波兰表达式求值是计算机科学中的一个重要概念,主要用于避免使用括号来表示运算优先级,从而简化表达式的解析过程。逆波兰表达式,又称后缀表达式,是一种没有括号、无需考虑运算符优先级的数学表达式书写方式。在...
4. 实现中缀表达式到逆波兰表达式的转换算法。 5. 输出生成的逆波兰表达式。 为了深入理解`inverse.c`的具体实现,你需要查看源代码并理解其中的逻辑。如果你需要进一步的帮助,比如代码分析或编程指导,随时告诉我...
逆波兰表达式,又称后缀表达式,是一种用于...总结,逆波兰表达式的求解涉及到数据结构(栈)、算法(递归下降解析)以及编程语言的基本操作。理解并掌握这两种方法,有助于深入理解计算机科学中的计算原理和算法设计。
逆波兰表达式(Reverse Polish Notation,RPN)是一种数学表达式表示方法,它不需要使用括号,而是通过运算符后置的方式明确运算顺序。在RPN计算器中,运算符紧跟在其操作数之后,使得计算过程更为简洁。这种表示法...
【数据结构与算法】逆波兰表达式完整版,使用java语言编写。逆波兰表达式又叫做后缀表达式,是一种没有括号,并严格遵循“从左到右”运算的后缀式表达方法
在编程领域,逆波兰表达式常用于表达式求值,因为其算法相对简单且效率高。易语言是一款中国本土的编程语言,旨在降低编程难度,提高开发效率。本篇将详细介绍易语言逆波兰表达式计算的相关知识。 1. **逆波兰...
标题"中缀表达式转变为逆波兰表达式"涉及的主要知识点是中缀表达式到逆波兰表达式的转换算法,这通常使用两个栈来实现:一个运算符栈和一个临时结果栈。这个过程主要分为以下步骤: 1. 遍历中缀表达式中的每一个...
逆波兰表达式的这种方法可以很容易地用算法实现,通常使用两个栈:一个用于存储操作数,另一个用于临时存储待处理的操作符。这种方式避免了中缀表达式解析时需要处理的优先级和括号问题,因此在某些计算和编译场景下...
中缀表达式和逆波兰表达式是两种不同的数学表达式表示方式,对于计算和解析有着不同的优势。本文将深入探讨如何将中缀表达式转化为逆波兰表达式,并结合C语言进行实现。 中缀表达式是我们日常生活中最常见的数学...