逆波兰表达式
逆波兰表达式又叫做后缀表达式。在通常的表达式
中,运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家
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
算法实现
package arithmetic.rpn;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* 逆波兰算法实现
* @author ty93
*
*/
public class RPN {
public Stack<String> operatorStack = new Stack<String>();
public Stack<String> calculateStack = new Stack<String>();
private Map<Character, Character> mapOperator = null;
public RPN() {
mapOperator = new HashMap<Character, Character>();
mapOperator.put('+', '1');
mapOperator.put('-', '1');
mapOperator.put('*', '2');
mapOperator.put('/', '2');
mapOperator.put('(', '0');
mapOperator.put(')', '0');
mapOperator.put('{', '0');
mapOperator.put('}', '0');
mapOperator.put('[', '0');
mapOperator.put(']', '0');
}
public int getLevelByChar(char c) {
return Integer.parseInt(String.valueOf(mapOperator.get(c)));
}
public void scanExpress(String express) {
for (char c : express.toCharArray()) {
if (c == ' ')
continue;
executeOperator(c);
}
}
public void executeOperator(String s) {
}
@SuppressWarnings("static-access")
public void executeOperator(Character c) {
if (c.isDigit(c)) {
calculateStack.add(String.valueOf(c));
} else {
switch (c) {
case '(':
operatorStack.push(String.valueOf(c));
break;
case ')':
while (true) {
String operator = operatorStack.pop();
if (operator.equals("(")) {
return;
} else {
calculateStack.push(operator);
}
}
case '{':
operatorStack.push(String.valueOf(c));
break;
case '}':
while (true) {
String operator = operatorStack.pop();
if (operator.equals("{")) {
return;
} else {
calculateStack.push(operator);
}
}
case '[':
operatorStack.push(String.valueOf(c));
break;
case ']':
while (true) {
String operator = operatorStack.pop();
if (operator.equals("]")) {
return;
} else {
calculateStack.push(operator);
}
}
case '+':
while (true) {
if (operatorStack.isEmpty()) {
operatorStack.push("+");
return;
}
String operator = operatorStack.peek();
if (getLevelByChar(operator.toCharArray()[0]) >= getLevelByChar('+')) {
calculateStack.push(operatorStack.pop());
} else {
operatorStack.push("+");
return;
}
}
case '-':
while (true) {
if (operatorStack.isEmpty()) {
operatorStack.push("-");
return;
}
String operator = operatorStack.peek();
if (getLevelByChar(operator.toCharArray()[0]) >= getLevelByChar('-')) {
calculateStack.push(operatorStack.pop());
} else {
operatorStack.push("-");
return;
}
}
case '*':
while (true) {
if (operatorStack.isEmpty()) {
operatorStack.push("*");
return;
}
String operator = operatorStack.peek();
if (getLevelByChar(operator.toCharArray()[0]) >= getLevelByChar('*')) {
calculateStack.push(operatorStack.pop());
} else {
operatorStack.push("*");
return;
}
}
case '/':
while (true) {
if (operatorStack.isEmpty()) {
operatorStack.push("/");
return;
}
String operator = operatorStack.peek();
if (getLevelByChar(operator.toCharArray()[0]) >= getLevelByChar('/')) {
calculateStack.push(operatorStack.pop());
} else {
operatorStack.push("/");
return;
}
}
default:
break;
}
}
}
public int getResult() {
return 0;
}
public static void main(String[] args) {
RPN rpn = new RPN();
String str = "5 + ( ( 1+2)*4)−3";
rpn.scanExpress(str);
System.out.println(rpn.calculateStack);
}
}
运算结果 [5, 1, 2, +, 4, *, 3]
分享到:
相关推荐
C语言:设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达式的值。数据结构实验
逆波兰表达式_课程设计.doc 逆波兰表达式_课程设计.doc
易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言...
逆波兰表达式的C++实现,用类封装,用于计算逆波兰表达式
以字符串的形式输入一个算术表达式,转换为逆波兰表达式,并求取其数值。
逆波兰表达式及其算法实现 很好的资料 里面分析很全面
C语言之逆波兰表达式完整代码(附算法),详细讲解其实现
是个人上数据结构课后,通过4天努力写出的代码文章,可能不是很好,但可用来参考参考!
逆波兰表达式的长 度不超过一行,以 "$"作为输入结束,操作数之间用空格分隔,操作符只可能有+、—、*、/四种 运算。例如: 23434 + 2*$。 数据结构作业
【数据结构与算法】逆波兰表达式完整版,使用java语言编写。逆波兰表达式又叫做后缀表达式,是一种没有括号,并严格遵循“从左到右”运算的后缀式表达方法
基于c语言的将算术中缀表达式转化为逆波兰表达式,注释清晰且代码打头有写好的思想。
中缀表达式转换成逆波兰表达式、c语言编写、用栈来实现
使用c语言实现,将给定的运算表达式翻译成逆波兰表达式的形式
对逆波兰表达式的解释与求解方法,运行平台支持c/c++或者是Linux系统都可以。
表达式求值,逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好
根据逆波兰表达式将各序表达式显示出来,并且将二叉树输出
计算字符串形式的逆波兰表达式(即两个操作数在前,计算符在后)。本题内,保证每个操作数均为1位数。操作符有'+','-','*','/'四种。且保证计算过程中除法运算全部为整数除法,结果为整数。 如23+4*,,结果20
将任意字符串转换为其逆波兰表达式,然后打印出来。
表达式求值 逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好