数据结构 - 栈与后缀表达式

后进先出的栈

栈是一种LIFO(后进先出)表，在Java中可以简单使用Stack或者Deque实现表示。这里主要讨论栈的一个应用—— 处理后缀表达式。

后缀表达式

什么的后缀表达式

简单来说，后缀表达式是把运算符放在操作数后面的表达式，例如：

我们可以观察到后缀表达式有以下特征：

1. 操作数的顺序和中缀表达式相同
2. 不需要考虑优先级，没有括号
3. 存在相同优先级满足交换律的运算符时后缀表达式不唯一

后缀表达式的计算

考虑后缀表达式的原因是因为它没有优先级和括号，可以简化计算程序的编码，下面是一个使用栈计算后缀表达式的简单实现，我们假定：

1. 后缀表达式是合理的
2. 所有操作数都是一位整数
3. 只考虑 + - * 运算

我们的想法是扫描整个字符串，数字入栈，若遇到运算符就取出两个操作数进行运算，结果入栈。

public static int calculatePostfixExpression(String expression) {
    Stack<Integer> stack = new Stack<>();
    for(int i=0;i<expression.length();i++) {
        char c = expression.charAt(i);
        if (c == '*') {
            stack.push(stack.pop() * stack.pop());
        } else if (c == '+') {
            stack.push(stack.pop() + stack.pop());
        } else if (c == '-') {
            // 首先取出减数，然后取出被减数
            stack.push(-stack.pop() + stack.pop());
        } else {
            stack.push(c - '0');
        }
    }
    return stack.pop();
}

中缀表达式转后缀表达式

明白后缀表达式便于计算之后，下一个问题很自然的就是如何将一个数学上习惯的中缀表达式转化为后缀表达式。

注意到后缀表达式的第一个特点，我们只需要将操作数一次输出，然后在合适的地方输出z运算符即可。

我们的想法依旧是扫描整个字符串，我们需要使用一个StringBuilder临时存放输出的结果，一个Stack临时存放运算符。

为了使我们的代码更多地关注如何处理表达式，我们假定：

1. 中缀表达式是合理的
2. 所有操作数都是一位整数
3. 只考虑 + - * 运算和 () 括号

这里解释一下对运算符的处理，当扫描到一个运算符时，当前运算符两边的操作数尚不能确定，但可以确定 Stack中高优先级或相同优先级的运算发应该被计算。

依旧是一个简单实现：

public static String toPostfixExpression(String expression) {
    Stack<Character> stack = new Stack<>();
    StringBuilder result = new StringBuilder(expression.length());
    char c; // 临时储存一个字符
    for(int i=0;i<expression.length();i++) {
        c = expression.charAt(i);
        if (c == '(') {
            // 左括号直接入栈
            stack.push(c);
        } else if (c == ')') {
            // 右括号搜索栈，直到找到左括号
            while((c = stack.pop()) != '(') {
                result.append(c);
            }
        } else if (c == '*') {
            // * 出栈并输出
            while(!stack.empty() && stack.peek() == '*') {
                result.append(stack.pop());
            }
            stack.push(c);  
        } else if (c == '+' || c == '-') {
            // + - * 出栈并输出
            while(!stack.empty() && stack.peek() != '(') {
                result.append(stack.pop());
            }
            stack.push(c);
        } else {
            result.append(c);
        }
    }
    // 扫描完整个字符串，清空栈
    while(!stack.empty()) {
        result.append(stack.pop());
    }
    return result.toString();
}

后记

留一个小小的练习，代码我以后补上，结合中缀表达式转后缀表达式和后缀表达式的计算，写一个程序直接计算中缀表达式。

以下视频给了我很大的帮助，在这里表示感谢：

https://www.bilibili.com/video/BV1vJ411v7xm
https://www.bilibili.com/video/BV1y7411W7Ka