力扣打卡：剑指 Offer II 036. 后缀表达式

解题思路

• 遇到运算符号就将栈中的两个运算因子弹出，而后后弹出的因子 num2 对前弹出的因子 num1 进行运算，运算的结果 res 重新压入栈中
• 遇到非运算符号，就将其压入栈中

计算器的运算实现大致原理也是压栈出栈而后在进行运算

代码

class Solution {
    public int evalRPNA(String[] tokens) {
        // 要么使用栈，要么使用List的remove
        // Java中栈的实现用双向队列来实现，性能更高
        Deque<String> stack = new ArrayDeque<>();
        HashSet<String> set = new HashSet<>();
        set.add("+");set.add("-");set.add("*");set.add("/"); // 可以不写set进行判断，直接用switch即可
        for(String s : tokens){
            if(set.contains(s)){
                // 注意弹出的顺序和运算的因子的前后顺序，后面弹出的数值是前运算因子
                // 计算器的设计实现中也正是这种运算流程，遇到运算符号就开始检查
                int num1 = Integer.valueOf(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                switch(s){
                    case "+":
                        res = num2 + num1;
                        break;
                    case "-":
                        res = num2 - num1;
                        break;
                    case "*":
                        res = num2 * num1;
                        break;
                    case "/":
                        res = num2 / num1;
                        break;
                }
                stack.push(String.valueOf(res)); // 运算完成后，再将结果压进栈中
                continue;
            }
            stack.push(s); // 遇到非运算符号就加入栈中，因为每次遇到了运算符号，都是前两个运算因子进行运算
        }
        return Integer.valueOf(stack.pop());
    }
}

 public int evalRPN(String[] tokens) {
     Deque<String> stack = new ArrayDeque<>();
     for(String s: tokens){
         int res = 0;
         int[] nums = new int[2];
         switch(s){
             case "+":
                 nums = toInteger(stack.pop(),stack.pop());
                 res = nums[1] + nums[0];
                 stack.push(res+"");
                 break;
             case "-":
                 nums = toInteger(stack.pop(),stack.pop());
                 res = nums[1] - nums[0];
                 stack.push(res+"");
                 break;
             case "*":
                 nums = toInteger(stack.pop(),stack.pop());
                 res = nums[1] * nums[0];
                 stack.push(res+"");
                 break;
             case "/":
                 nums = toInteger(stack.pop(),stack.pop());
                 res = nums[1] / nums[0];
                 stack.push(res+"");
                 break;
             default:
                 stack.push(s);
         }
     }
     return Integer.valueOf(stack.pop());
 }
 public int[] toInteger(String a, String b){
     return new int[] {Integer.valueOf(a),Integer.parseInt(b)};
 }