加减乘除

Evaluate Reverse Polish Notation

• RPN 是典型的Stack应用题，Calculator的pre-requisite

public int evalRPN(String[] tokens) {
        Stack<Integer> stk = new Stack<>();
        String operators = "+-*/";
        for(String token : tokens) {
            if (! operators.contains(token)) {
                stk.push(Integer.parseInt(token));
            } else {
                int num2 = stk.pop();
                int num1 = stk.pop();
                int res = 0;
                switch (token) {
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;   
                }
                stk.push(res);
            }
        }
        return stk.pop();
    }

Pow(x, n)

• 如果n < 0, 就x = 1/ x, n = -n

• 注意-n 可能会integer overflow

/*
    x == 0
    n == 0
    n < 0 ---> x = 1/x, n = -n
    */
    public double myPow(double x, int n) {
        if (x == 0) return 1;
        if (n == 0) return 1;
        long m = n;
        if (m < 0) {
            x = 1/x;
            m = -m;
        }
        double res = 1;
        while (m > 0) {
            if (m % 2 != 0) {
                res *= x;
            }
            x *= x;
            m /= 2;
        }
        return res;
    }