36：后缀表达式

:::info 题目：后缀表达式是一种算术表达式，它的操作符在操作数的后面。输入一个用字符串数组表示的后缀表达式，请输出该后缀表达式的计算结果。假设输入的一定是有效的后缀表达式。例如，后缀表达式[“2”，”1”，”3”，”“，”+”]对应的算术表达式是“2+13”，因此输出它的计算结果5。 :::

  1. // evaluate Reverse Polish Notation
  2. public class evalRPN {
  3.     public static int evalRPN(String[] arr) {
  4.         Stack<Integer> stack = new Stack<>();
  5.         List<String> operators = Arrays.asList("+", "-", "*", "/");
  7.         for(String str : arr) {
  8.             if(operators.contains(str)) {
  10.                 // 先pop的元素在operator右侧
  11.                 int num2 = stack.pop();
  12.                 // 后pop的元素在operator左侧
  13.                 int num1 = stack.pop();
  14.                 int rs = calculate(num1, num2, str);
  15.                 stack.push(rs);
  17.             } else {
  18.                 stack.push(Integer.parseInt(str));
  19.             }
  20.         }
  22.         return stack.pop();
  24.     }
  26.     private static int calculate(int num1, int num2, String operator) {
  27.         switch(operator) {
  28.             case "+":
  29.                 return num1 + num2;
  30.             case "-":
  31.                 return num1 - num2;
  32.             case "*":
  33.                 return num1 * num2;
  34.             case "/":
  35.                 return num1 / num2;
  36.             default:
  37.                 throw new UnsupportedOperationException();
  38.         }
  39.     }
  41.     public static void main(String[] args) {
  42.         String[] arr = {"2", "1", "3", "*", "+"};
  43.         System.out.println(evalRPN(arr) == 5);
  44.     }
  46. }

37：小行星碰撞

:::info 题目：输入一个表示小行星的数组，数组中每个数字的绝对值表示小行星的大小，数字的正负号表示小行星运动的方向，正号表示向右飞行，负号表示向左飞行。如果两颗小行星相撞，那么体积较小的小行星将会爆炸最终消失，体积较大的小行星不受影响。如果相撞的两颗小行星大小相同，那么它们都会爆炸消失。飞行方向相同的小行星永远不会相撞。求最终剩下的小行星。例如，有6颗小行星[4，5，-6，4，8，-5]，如图6.2所示（箭头表示飞行的方向），它们相撞之后最终剩下3颗小行星[-6，4，8]。 :::

  1. public class AsteroidCollision() {
  3.     public static int[] asteroidCollision(int[] asteroids) {
  4.     }
  5. }