LeetCode之Reverse Polish Notation

1. 关于Reverse Polish Notation

摘自 维基百科 的解释：

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

2. 题目内容

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

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

[“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9
[“4”, “13”, “5”, “/“, “+”] -> (4 + (13 / 5)) -> 6

3. 解题思路

对于一个合法的字符数组，依次扫描该字符数组：

1. 如果该字符是”+”,”-“,”*”,”/“中的任意一个，则将其放入栈中；
2. 如果该字符是操作符，则从栈中取出两个操作数按照顺序进行运算；
3. 直到扫描完毕，取出栈中的最后一个数，即为结果。

4. 代码实现

public int evalRPN(String[] tokens) {
    List<String> operators = new ArrayList<String>() {{
        add("+");
        add("-");
        add("*");
        add("/");
    }};
    Stack<Integer> tempValue = new Stack<>();
    int number1;
    int number2;
    int result = 0;
    for (String token : tokens) {
        if (!operators.contains(token)) {
            tempValue.push((Integer.valueOf(token)));
        } else {
            number1 = tempValue.pop();
            number2 = tempValue.pop();
            switch (token) {
                case "+":
                    result = number2 + number1;
                    break;
                case "-":
                    result = number2 - number1;
                    break;
                case "*":
                    result = number2 * number1;
                    break;
                case "/":
                    result = number2 / number1;
                    break;
            }
            tempValue.push(result);
        }
    }
    return tempValue.pop();
}