面试算法36：后缀表达式

题目

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

分析

后缀表达式又叫逆波兰式（Reverse Polish Notation，RPN），是一种将操作符放在操作数后面的算术表达式。通常用的是中缀表达式，即操作符位于两个操作数的中间，如“2+1*3”。使用后缀表达式的好处是不需要使用括号。例如，中缀表达式的“2+1*3”和“（2+1）*3”不相同。它们的后缀表达式分别为“213*+”和“21+3*”。后缀表达式不使用括号也能无歧义地表达这两个不同的算术表达式。

下面以["2"，"1"，"3"，"*"，"+"]为例分析计算过程。从左到右扫描这个数组。首先遇到的是操作数"2"，由于这是后缀表达式，操作符还在后面。不知道操作符就不能做计算，于是先将"2"保存到某个数据容器中。接下来的两个还是操作数，"1"和"3"，由于缺少操作符，因此还是不知道如何计算，只好也将它们先后保存到数据容器中。接下来遇到了一个操作符"*"。按照后缀表达式的规则，这个操作符对应的操作数是"1"和"3"，于是将它们从数据容器中取出来。此时容器中有先后保存的"2"、"1"和"3"这3个操作数，此时取出的是后保存的两个，最先保存的"2"仍然留在数据容器中。这看起来是“后入先出”的顺序，所以可以考虑用栈来实现这个数据容器。

由于当前的操作符是"*"，因此将两个操作数"1"和"3"相乘，得到结果"3"。这个结果可能会成为后面操作符的操作数，因此仍然将它入栈。最后遇到的是操作符"+"，此时栈中有两个操作数，即"2"和"3"，分别将它们出栈，然后计算它们的和，得到"5"，再将结果"5"入栈。此时整个后缀表达式已经计算完毕，留在栈中的唯一的操作数"5"就是结果。

解

public class Test {
    public static void main(String[] args) {
        String[] tokens = {"2", "1", "3", "*", "+"};
        int result = evalRPN(tokens);
        System.out.println(result);
    }

    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                case "-":
                case "*":
                case "/":
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    stack.push(calculate(num2, num1, token));// 注意num2和num1顺序
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }

    private static int calculate(int num1, int num2, String operator) {
        switch (operator) {
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "*":
                return num1 * num2;
            case "/":
                return num1 / num2;
            default:
                return 0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42