[LeetCode]Evaluate Reverse Polish Notation

根据逆波兰式来算出表达式的值。首先说明一下逆波兰式，逆波兰式是巴普通表达式的中缀表达方法，例如，3 + 5 * 4， （3 + 5）* 4 替换成后缀表达式，逆波兰式不需要括号，且不会产生歧义。
例如，之前的两个表达式用逆波兰式表达就是，3 5 4 * +， 3 5 + 4 *。普通式子转换成逆波兰式就要注意两点：第一，由于涉及的运算符都是双目的（不包括括号），运算符要放在第二个操作数后面；第二， 如果第二个操作数，由于运算符号的优先性，是一个表达式，就先写出表示第二个操作数的逆波兰式，之后加上操作符。这一题不需要涉及到普通的表达式转换成逆波兰式，所以我们只考虑如何算出，逆波兰式的值，计算逆波兰式的值十分简单，每次碰到一个操作符，就把对应的操作数的值算出来，也就是两个操作数经过计算变成一个操作数，直到计算完所有的操作符。值得注意的一点事，操作符永远比操作数少1。基本的思路就是维护一个操作数的栈，每次遇到一个操作符，弹出栈顶的两个元素，计算完入栈，直到计算完所有，栈里最后一个就是表达式的值。代码如下：

	public class Solution {
	public int evalRPN(String[] tokens) {
	if (tokens == null)
	return 0;
	Stack<Integer> stack = new Stack<Integer>();
	int len = tokens.length;
	for (int i = 0; i < len; i++) {
	String str = tokens[i];
	if (isOperator(str)) {
	int num2 = stack.pop();
	int num1 = stack.pop();
	switch(str.charAt(0)) {
	case '+':
	stack.push(num1 + num2);
	break;
	case '-':
	stack.push(num1 - num2);
	break;
	case '*':
	stack.push(num1 * num2);
	break;
	case '/':
	stack.push(num1 / num2);
	break;
	}
	}
	else
	stack.push(Integer.parseInt(str));
	}
	return stack.pop();
	}
	private boolean isOperator(String str) {
	return str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/");
	}
	}

view raw Evaluate Reverse Polish Notation.java hosted with ❤ by GitHub

 Follow up：如何把表达式转换成逆波兰表达式