[数据结构与算法]leetCode-栈类型详解

在刷题的时候遇到一个后缀表达式的题目，然后感觉该题是比较经典的栈应用类型的题目，正好借着该题，给大家聊一聊栈的用法，顺便解决了这道题。

众所周知，栈是是一个先进后出的数据结构，利用该特性，在程序的设计中十分常见，如：括号匹配、表达式求值、在递归中的应用等都离不开栈这一数据结构。

我下面一一给大家简单说一下。（PS：栈的数据结构我就不再此处赘述，大家可以自行了解）

1.栈在括号匹配中的应用

假设表达式中允许包含两种括号 ：｜直｜括号和方括号 ，其嵌套 的顺序任意 即（［］（））或［（［］[ ]）］等均为正确的格式，［（］）或（［（））或（（）］均为不正确的格式 。

我们考虑下列括号序列：

我们简单分析一下：

• 计算机接收第1个括号“ ［ ” 后 ，期待与之匹配的第 8 个括号“ ］” 出现 。
• 获得了第 2 个括号 “（”，此时第1 个括号“［” 暂时放在一边，而急迫期待与之匹配的第7 个括号“）”出现 。
• 获得了第 3 个括号“ ［ ”，此时第 2 个括 号“（” 暂时放在一边，而急迫期待与之匹配的第4 个括号“］”出现 。第 3 个括号 的期待得到满足，消解之后 ，第 2 个括号 的期待匹配又成为 当前最急迫的任务。
• 以此类推，可见该处理过程与栈的思想、吻合。

我们就按照上面的过程，可以给出以下设计思想：

• 初始化一个堆栈stack，开始依次扫描括号字符串string，当遇到[ ’ 、 ( ’ 左括号时将其压入栈中。
• 当遇到右括号时将检查栈顶元素是否为与此右括号对应的左括号，若对应，则将其对应左括号出栈，若不对应，则表达式有误，返回false。
• 在过程中只有左括号才会压入栈内，当表达式正确时，最后栈将一次次左括号出栈而变为空栈。
• 扫描完所有字符后，检查堆栈是否为空栈，若是，返回true，否则返回false。

题目来源：20. 有效的括号
答案：(PS:Java版)

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char topChar = stack.pop();
                if (c == ')' && topChar != '(') return false;
                if (c == ']' && topChar != '[') return false;
                if (c == '}' && topChar != '{') return false;
            }
        }
        //判断是否栈空
        if (stack.isEmpty()) return true;
        return false;
    }

2.栈在表达式求值中的应用

表达式求值是程序设计语言编译 中 一个最基本 的问题，它的实现是找应用的一个典型范例 。

中缀表达式不仅依赖运算符的优先级，而且还要处理括号 。后缀表达式的运算符在操作数后面，在后缀表达式中己考虑了运算符的优先级，没有括号，只有操作数和运算符。

中缀表达式A+B*(C-D)-E/F所对应的后缀表达式为ABCD-*EF/-。

里面就涉及到一个知识点，中缀即我们正常的运算顺序如何变为后缀表达式呢？如果你数据结构学的还不错可以跳过该节。

2.1 中缀表达式转化为后缀表达式

我直接举个例子吧。
中缀表达式 a+b - a* ( (c+d) /e- f) + g
这个式子应该相对比较有代表性了，我们就看看怎么把它变成后缀的。

我们先确定好运算符的优先级，即 ‘*,/’ > ‘±’>‘()’
对于()，左括号只有在遇到右括号则表示括号匹配成功，直接退栈，左括号遇到其他字符，直接进栈。
右括号，在遇到其他字符，会让其他字符一直退栈，一直退到左括号为止，和左括号一同出栈，不进行输出。

下面我们的操作步骤就是：遇到优先级大的,直接进栈，遇到优先级小的或者相等的就退栈（PS:如果符号一样，无需操作，直接进栈），同时让优先级进栈。

同时，如果遇到数值则直接输出
下面我们看看：a+b - a* ( (c+d) /e- f) + g这个式子的后缀是怎么一步步实现的

最后将输出元素依次连接起来：

ab+acd+e/f-*-g+

这个式子就是我们的后缀表达式

2.2 后缀表达式的计算

最后开始进行计算，而我们最经常使用的便是通过后缀表达式计算最终结果，计算过程如下：

最终的结果即为栈中的最后一个元素。

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<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));
    }

参考题目：剑指 Offer II 036. 后缀表达式