150. Evaluate Reverse Polish Notation

• Reverse Polish Notation 계산기를 구현한다.

• 스택을 이용하여 숫자들을 저장하고 연산자가 나올 때 마다 스택에서 숫자를 2개 꺼내서 특정 연산자를 적용하면 된다.
• 스택의 길이는 token의 수를 넘을 수 없으므로 동일한 길이의 integer array로 선언하여 stack을 대신할 수 있다.
• int[]를 사용하면 Stack<Integer> 으로 구현했을 때 보다 1.5 ~ 2배 가량 빠르다.

class Solution {
    public int evalRPN(String[] tokens) {
        int[] stack = new int[tokens.length];
        int top = -1;
        for (String token : tokens) {
            char c = token.charAt(0);
            int value = 0, lhs, rhs;
            if (token.length() == 1 && (c < '0' || c > '9')) {
                rhs = stack[top--];
                lhs = stack[top--];
                switch (c) {
                    case '+': value = lhs + rhs; break;
                    case '-': value = lhs - rhs; break;
                    case '*': value = lhs * rhs; break;
                    case '/': value = lhs / rhs; break;
                }
                stack[++top] = value;
            } else if (c == '-') {
                stack[++top] = -Integer.parseInt(token.substring(1));
            } else {
                stack[++top] = Integer.parseInt(token);
            }
        }
        return stack[top];
    }
}