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.

Some examples:

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

Solution1: stack
Run time complexity is O(n).

public class Solution {
    public int evalRPN(String[] tokens) {
        if(tokens == null || tokens.length == 0)
            return 0;
        
        LinkedList stack = new LinkedList();
        
        for(int i = 0; i < tokens.length; i++) {
            if(tokens[i].equals("+")) {
                stack.push(stack.pop() + stack.pop());
            }else if(tokens[i].equals("-")) {
                stack.push(-stack.pop() + stack.pop());
            }else if(tokens[i].equals("*")) {
                stack.push(stack.pop() * stack.pop());
            }else if(tokens[i].equals("/")) {
                int n1 = stack.pop();
                int n2 = stack.pop();
                stack.push(n2 / n1);
            }else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.pop();
    }
}

Solution2: stack
We can loop through each element in the given array. When it is a number, push it to the stack. When it is an operator, pop two numbers from the stack, do the calculation, and push back the result.

public class Solution {
    public int evalRPN(String[] tokens) {
        int returnValue = 0;
 
        String operators = "+-*/";
 
        Stack stack = new Stack();
 
        for(String t : tokens){
            if(!operators.contains(t)){
                stack.push(t);
            }else{
                int a = Integer.valueOf(stack.pop());
                int b = Integer.valueOf(stack.pop());
                int index = operators.indexOf(t);
                switch(index){
                    case 0:
                        stack.push(String.valueOf(a+b));
                        break;
                    case 1:
                        stack.push(String.valueOf(b-a));
                        break;
                    case 2:
                        stack.push(String.valueOf(a*b));
                        break;
                    case 3:
                        stack.push(String.valueOf(b/a));
                        break;
                }
            }
        }
 
        returnValue = Integer.valueOf(stack.pop());
 
        return returnValue;
    }
}

============================================================================ 以下这种写法在leetcode里面过不了，因为switch string statement is only available from JDK 1.7，leetcode版本比这个低

public static int evalRPN(String[] tokens) {
  int returnValue = 0;
  String operators = "+-*/";
 
  Stack stack = new Stack();
 
  for (String t : tokens) {
   if (!operators.contains(t)) {
    stack.push(t);
   } else {
    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;
 }

Solution3: create an interface called Operator and map each operator string to an implementation of the Operator interface.
This makes the code more clean and easy to add new operators later.

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class EvaluateReversePolishNotation {
 
 /*
  * Further Thoughts:
  * 
  * The above code contains duplication. For example, if we decide to add a
  * new operator, we would need to update the code in two places – in the
  * set’s initialization and the switch statement. Could you refactor the
  * code so it is more extensible? 
  * You are probably not expected to write this refactored code during an 
  * interview session. However, it will make
  * you a stronger candidate if you could make this observation and point
  * this out, as it shows to the interviewer that you care about clean code.
  * In Java, create an interface called Operator and map each operator string
  * to an implementation of the Operator interface. For other languages such
  * as C++, each operator will be mapped to a function pointer instead.
  */

    interface Operator {
        int eval(int x, int y);
    }
 
    private static Map OPERATORS = new HashMap() {
        {
            put("+", new Operator() {
                public int eval(int x, int y) {
                    return x + y;
                }
            });
            put("-", new Operator() {
                public int eval(int x, int y) {
                    return x - y;
                }
            });
            put("*", new Operator() {
                public int eval(int x, int y) {
                    return x * y;
                }
            });
            put("/", new Operator() {
                public int eval(int x, int y) {
                    return x / y;
                }
            });
        }
   };

   public int evaluate(String[] tokens) {
       Stack stack = new Stack();
       for(String token : tokens) {
           if(OPERATORS.containsKey(token)) {
               int y = stack.pop();
               int x = stack.pop();
               stack.push(OPERATORS.get(token).eval(x, y));
           }else {
               stack.push(Integer.parseInt(token));
           }
       }
       return stack.pop();
   }
}

From Frank