问题

根据逆波兰表示法，求表达式的值
有效的算符包括 +、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式

说明：
整数除法只保留整数部分
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况

示例 1：
输入：tokens = [“2”,”1”,”+”,”3”,”“]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) 3) = 9

示例 2：
输入：tokens = [“4”,”13”,”5”,”/“,”+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：
输入：tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,”“,”/“,”“,”17”,”+”,”5”,”+”]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
((10 (6 / ((9 + 3) -11))) + 17) + 5
= ((10 (6 / (12 -11))) + 17) + 5
= ((10 (6 / -132)) + 17) + 5
= ((10 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

思路

逆波兰表达式严格遵循从左到右的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

  • 如果遇到操作数，则将操作数入栈；
  • 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值

其实逆波兰表达式相当于是二叉树中的后序遍历。把运算符作为中间节点，按照后序遍历的规则画出一个二叉树
但我们没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后续遍历的方式把二叉树序列化了，就可以了
进一步看，本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，类似于删除字符串中所有相邻的重复项操作

自解

  1. class Solution {
  2.     public static int evalRPN(String[] tokens) {
  3.         Stack<Integer> numStack = new Stack<>();
  4.         int op1, op2;
  5.         for (String s : tokens) {
  6.             switch (s) {
  7.             case "+":
  8.                 op2 = numStack.pop();
  9.                 op1 = numStack.pop();
  10.                 numStack.push(op1 + op2);
  11.                 break;
  12.             case "-":
  13.                 op2 = numStack.pop();
  14.                 op1 = numStack.pop();
  15.                 numStack.push(op1 - op2);
  16.                 break;
  17.             case "*":
  18.                 op2 = numStack.pop();
  19.                 op1 = numStack.pop();
  20.                 numStack.push(op1 * op2);
  21.                 break;
  22.             case "/":
  23.                 op2 = numStack.pop();
  24.                 op1 = numStack.pop();
  25.                 numStack.push(op1 / op2);
  26.                 break;
  27.             default:
  28.                 numStack.push(Integer.valueOf(s));
  29.                 break;
  30.             }
  31.         }
  32.         return numStack.pop();
  33.     }
  34. }

官方题解

注意：Java堆栈Stack类已经过时，Java官方推荐使用Deque替代Stack使用。Deque堆栈操作方法：push()、pop()、peek()

  1. class Solution {
  2.     public int evalRPN(String[] tokens) {
  3.         Deque<Integer> stack = new LinkedList<Integer>();
  4.         int n = tokens.length;
  6.         for (int i = 0; i < n; i++) {
  7.             String token = tokens[i];
  8.             if (isNumber(token)) {
  9.                 stack.push(Integer.parseInt(token));
  10.             } else {
  11.                 int num2 = stack.pop();
  12.                 int num1 = stack.pop();
  13.                 switch (token) {
  14.                     case "+":
  15.                         stack.push(num1 + num2);
  16.                         break;
  17.                     case "-":
  18.                         stack.push(num1 - num2);
  19.                         break;
  20.                     case "*":
  21.                         stack.push(num1 * num2);
  22.                         break;
  23.                     case "/":
  24.                         stack.push(num1 / num2);
  25.                         break;
  26.                     default:
  27.                 }
  28.             }
  29.         }
  30.         return stack.pop();
  31.     }
  33.     public boolean isNumber(String token) {
  34.         return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
  35.     }
  36. }