Evaluate Reverse Polish Notation

https://leetcode.com/problems/evaluate-reverse-polish-notation/description/

Evaluate the value of an arithmetic expression inReverse Polish Notation.

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

Thoughts

stack的又一经典应用。

Code

class Solution {
    private boolean isNum(String token) {
        if ("+-*/".contains("" + token.charAt(0)) && token.length() == 1) {
            return false;
        }  
        return true;
    } 

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String str : tokens) {
            if (isNum(str)) {
                stack.push(Integer.parseInt(str));
            } else {
                int op2 = stack.pop(), op1 = stack.pop();
                switch (str) {
                    case "+":
                        stack.push(op1 + op2);
                        break;
                    case "-":
                        stack.push(op1 - op2);
                        break;
                    case "*":
                        stack.push(op1 * op2);
                        break;
                    default:
                        stack.push(op1 / op2);
                }
            }
        }

        return stack.pop();
    }
}

Analysis

做题耗时: 8min

Errors:

1. op1和op2顺序弄反了

2. -和负数没分清

时空复杂度都是O(n).