知识拓展练习（经典面试题） / 55. 逆波兰表达式求值

一、题目

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：
有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是向零截断。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位整数表示。

二、示例

示例 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 <= tokens.length <= 10^4
tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

四、逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

①平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

②该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

①去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

②适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

五、参考题解

1、前言

逆波兰表达式由波兰的逻辑学家卢卡西维兹提出。逆波兰表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后。因此，逆波兰表达式也称后缀表达式。

2、方法一：栈

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

①如果遇到操作数，则将操作数入栈；

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

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

//Java
class Solution {
  public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new LinkedList<Integer>();
    int n = tokens.length;
    for (int i = 0; i < n; i++) {
      String token = tokens[i];
      if (isNumber(token)) {
        stack.push(Integer.parseInt(token));
      } else {
        int num2 = stack.pop();
        int num1 = stack.pop();
        switch (token) {
          case "+":
            stack.push(num1 + num2);
            break;
          case "-":
            stack.push(num1 - num2);
            break;
          case "*":
            stack.push(num1 * num2);
            break;
          case "/":
            stack.push(num1 / num2);
            break;
          default:
        }
      }
    }
    return stack.pop();
  }
  public boolean isNumber(String token) {
    return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
  }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组 tokens 的长度。需要遍历数组 tokens 一次，计算逆波兰表达式的值。

空间复杂度：O(n)，其中 n 是数组 tokens 的长度。使用栈存储计算过程中的数，栈内元素个数不会超过逆波兰表达式的长度。

3、方法二：数组模拟栈

方法一使用栈存储操作数。也可以使用一个数组模拟栈操作。

如果使用数组代替栈，则需要预先定义数组的长度。对于长度为 n 的逆波兰表达式，显然栈内元素个数不会超过 n，但是将数组的长度定义为 n 仍然超过了栈内元素个数的上界。那么，栈内元素最多可能有多少个？

对于一个有效的逆波兰表达式，其长度 n 一定是奇数，且操作数的个数一定比运算符的个数多 1 个，即包含 (n+1)/2 个操作数和 (n−1)/2 个运算符。考虑遇到操作数和运算符时，栈内元素个数分别会如何变化：

①如果遇到操作数，则将操作数入栈，因此栈内元素增加 1 个；

②如果遇到运算符，则将两个操作数出栈，然后将一个新操作数入栈，因此栈内元素先减少 2 个再增加 1 个，结果是栈内元素减少 1 个。

由此可以得到操作数和运算符与栈内元素个数变化的关系：遇到操作数时，栈内元素增加 1 个；遇到运算符时，栈内元素减少 1 个。

最坏情况下，(n+1)/2 个操作数都在表达式的前面，(n−1)/2 个运算符都在表达式的后面，此时栈内元素最多为 (n+1)/2 个。在其余情况下，栈内元素总是少于 (n+1)/2 个。因此，在任何情况下，栈内元素最多可能有 (n+1)/2 个，将数组的长度定义为 (n+1)/2 即可。

具体实现方面，创建数组 stack 模拟栈，数组下标 0 的位置对应栈底，定义 index 表示栈顶元素的下标位置，初始时栈为空，index=−1。当遇到操作数和运算符时，进行如下操作：

①如果遇到操作数，则将 index 的值加 1，然后将操作数赋给 stack[index]；

②如果遇到运算符，则将 index 的值减 1，此时 stack[index] 和 stack[index+1] 的元素分别是左操作数和右操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数赋给 stack[index]。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，因此 index=0，此时 stack[index] 即为逆波兰表达式的值。

//Java
class Solution {
  public int evalRPN(String[] tokens) {
    int n = tokens.length;
    int[] stack = new int[(n + 1) / 2];
    int index = -1;
    for (int i = 0; i < n; i++) {
      String token = tokens[i];
      switch (token) {
        case "+":
          index--;
          stack[index] += stack[index + 1];
          break;
        case "-":
          index--;
          stack[index] -= stack[index + 1];
          break;
        case "*":
          index--;
          stack[index] *= stack[index + 1];
          break;
        case "/":
          index--;
          stack[index] /= stack[index + 1];
          break;
        default:
          index++;
          stack[index] = Integer.parseInt(token);
      }
    }
    return stack[index];
  }
}