Ac solution code


  • 0

    The basic idea is using Stack to push operands into the stack. Once meet an operator, pop two operands from the stack for the corresponding calculation, then push the calculation result to stack. Keep the above steps, finally, pop the left number in the stack as the result.

    Runtime complexity = O(n)

    O(amount of operands x 2)(1 push, 1 pop) +
    O(amount of operators x 2)(1 for calculation, 1 for push calculation result back to stack)  
    = O(n * 2) = O(n)
    

    JAVA Code:

    public int evalRPN(String[] tokens) {
    	if (tokens == null || tokens.length == 0) return 0;
        Stack<Integer>stack = new Stack<Integer>();
        for (String s : tokens) {           
            switch(s) {
                case "+": stack.push(stack.pop() + stack.pop()); break; 
                case "-": stack.push(-stack.pop() + stack.pop()); break;
                case "*": stack.push(stack.pop() * stack.pop()); break;
                case "/": { 
                    int b = stack.pop(), a = stack.pop();
                    stack.push(a / b); 
                    break;
                }
                default: stack.push(Integer.parseInt(s));                
            }
        }
        return stack.pop();
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.