栈

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {

        /**
         * 逆波兰表达式
         * 遇到数字压入栈，遇到算符就弹出最后两个数进行计算，将结果再压入栈
         * 最后剩下一个数字，就是最终结果
         */
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {

            String string = tokens[i];

            /**
             * 比较两个字符串是否相等，需要用equals()方法
             */
            if (string.equals("+")){

                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 + num2);
            }
            else if (string.equals("-")){

                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 - num2);
            }
            else if (string.equals("*")){

                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 * num2);
            }
            else if (string.equals("/")){

                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 / num2);
            }
            else {

                /**
                 * Integer.parseInt()方法将字符串转换为整形
                 */
                stack.push(Integer.parseInt(string));
            }
        }

        return stack.pop();
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 */