150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Idea:

maintain a stack to store the operands
push the elements into the stack until meets a operator.Once we saw a operator, pop out two elements from the stack and evaluate two elements, push the result into the stack.

 public static final HashSet<String> operators = new HashSet<String>(Arrays.asList("*","/","-","+"));
 public int evaluationPostfix(List<String> postfix) {
  Stack<Integer> stack = new Stack<Integer>();
  for(String token : postfix) {
   if(operators.contains(token)) {
    int op1 = stack.pop();
    int op2 = stack.pop();
    stack.push(eval(op1,op2,token));
   }else {
    stack.push(Integer.parseInt(token));
   }
  }
  return stack.pop();
 }
 
 private int eval(int op1, int op2, String operator) {
  switch(operator) {
  case "*":
   return op1 * op2;
  case "/":
   return op1 / op2;
  case "+":
   return op1 + op2;
  default:
   return op1 - op2;
  }
 }