150. Evaluate Reverse Polish Notation.md

Solution1

class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            return 0;
        }
        int res = 0;
        String signs = "+-*/";
        Stack<Integer> stack = new Stack<>();
        for (String s : tokens) {
            if (s.length() == 1 && signs.contains(s)) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                stack.push(calculate(operand1, operand2, s));
            }
            else {
                stack.push(Integer.valueOf(s));
            }
        }
        return (int)stack.pop();
    }
    private int calculate(int operand1, int operand2, String s) {
        int res = 0;
        switch (s) {
            case "+": 
                res = operand1 + operand2;
                break;
            case "-": 
                res = operand1 - operand2;
                break;
            case "*": 
                res = operand1 * operand2;
                break;
            default:
                res = operand1 / operand2;
                break;
        }
        return res;
    }
}

note

• time O(n) space O(n)
• The idea is to use stack. Whenever we encounter non-sign strings, we convert them to integers and store them into our stack. Once we meet a sign, we pop two integers from stack and eval them and push the result back to the stack for future calculation. After traversing all elements, the last element in the stack is the result.