Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Analysis:
Use a stack to save the numbers, once an operator is found, pop two numbers from stack, and push the result back to stack. Note: make sure the order of the operands.
1 public class Solution { 2 /** 3 * @param tokens The Reverse Polish Notation 4 * @return the value 5 */ 6 public int evalRPN(String[] tokens) { 7 if (tokens == null || tokens.length == 0) return 0; 8 Stack<Integer> stack = new Stack<Integer>(); 9 10 for (int i = 0; i < tokens.length; i++) { 11 if (!(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/"))) { 12 stack.push(Integer.parseInt(tokens[i])); 13 } else { 14 if (stack.size() < 2) return 0; 15 int value1 = stack.pop(); 16 int value2 = stack.pop(); 17 if (tokens[i].equals("+")) { 18 stack.push(value1 + value2); 19 } else if (tokens[i].equals("-")) { 20 stack.push(value2 - value1); 21 } else if (tokens[i].equals("*")) { 22 stack.push(value1 * value2); 23 } else { 24 if (value1 == 0) { 25 return Integer.MAX_VALUE; 26 } 27 stack.push(value2 / value1); 28 } 29 } 30 } 31 return stack.pop(); 32 } 33 }
Evaluate Reverse Polish Notation
原文：http://www.cnblogs.com/beiyeqingteng/p/5679265.html