`
zha_zi
  • 浏览: 581909 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

逆波兰表达式

 
阅读更多

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

 

 

 算法实现

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]

分享到:
评论
3 楼 zha_zi 2012-02-05  
cguang 写道
运算结果  [5, 1, 2, +, 4, *, 3]少了减号,应该是[5, 1, 2, +, 4, *, 3,-]吧
public void scanExpress(String express) {
        for (char c : express.toCharArray()) {
            if (c == ' ')
                continue;
            executeOperator(c);
        }
        if(!operatorStack.empty()) {
            String s = operatorStack.pop();
            calculateStack.push(s);
        }
    }
这样貌似可以,不知道是不是

程序没怎么优化,当时随便写的就验证了一下算法,你的应该也是可以的
2 楼 cguang 2012-01-18  
运算结果  [5, 1, 2, +, 4, *, 3]少了减号,应该是[5, 1, 2, +, 4, *, 3,-]吧
public void scanExpress(String express) {
        for (char c : express.toCharArray()) {
            if (c == ' ')
                continue;
            executeOperator(c);
        }
        if(!operatorStack.empty()) {
            String s = operatorStack.pop();
            calculateStack.push(s);
        }
    }
这样貌似可以,不知道是不是
1 楼 stin 2011-11-24  
讲的很清楚,谢谢

相关推荐

Global site tag (gtag.js) - Google Analytics