逆波兰式与表达式求值

• 何为波兰式？何为逆波兰式？
• 如何与表达式求值联系起来？

波兰式、逆波兰式是数据结构和编译原理里面提到的知识点，我们平时的运算式都是这样的 2 + 3 * (5 - 1)-10（中缀表达式），这样表达式易于阅读和计算，但是对于计算机这样就有点懵逼了。

前缀表达式： 比如2 + 3 * (5 - 1)这个表达式的前缀表达式为+ 2 * 3 - 5 1来表示  波兰表达式

中缀序表达式：比如 2 + 3 * (5 - 1)-10

后缀表达式：比如2 + 3 * (5 - 1)用逆波兰式来表示则是：2 3 5 1 - * +  逆波兰表达式

求表达式值：

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

问题可以转换为遍历表达式用一个堆来存数字，当遇见操作符的时候，弹出两个数字执行相应的运算，再压入堆里面，最后返回出来的就是运算表达式的结果。

public class Test {

	public static void main(String[] args) throws IOException {
		String[] tokens = new String[] { "2", "1", "+", "3", "*" };
		System.out.println(evalRPN(tokens));
	}

	public static int evalRPN(String[] tokens) {
		int returnValue = 0;
		String operators = "+-*/";

		Stack<String> stack = new Stack<String>();

		for (String t : tokens) {
			if (!operators.contains(t)) { //push to stack if it is a number
				stack.push(t);
			} else {//pop numbers from stack if it is an operator
				int a = Integer.valueOf(stack.pop());
				int b = Integer.valueOf(stack.pop());
				switch (t) {
				case "+":
					stack.push(String.valueOf(a + b));
					break;
				case "-":
					stack.push(String.valueOf(b - a));
					break;
				case "*":
					stack.push(String.valueOf(a * b));
					break;
				case "/":
					stack.push(String.valueOf(b / a));
					break;
				}
			}
		}

		returnValue = Integer.valueOf(stack.pop());

		return returnValue;
	}
}

参考：http://www.programcreek.com/2012/12/leetcode-evaluate-reverse-polish-notation/