Python 数据结构之栈和队列 —— （二）应用 (1) 括号匹配及后缀表达式

zltzlt

来源于 CSDN

Python 数据结构之栈和队列 —— （二）应用 (1) 括号匹配及后缀表达式

在学习了栈和队列的基本实现后，我们依次学习二者在实际问题中的应用。

都是最典型的应用，基本以 LeetCode 的题目为例。

由于栈的后进先出的特点，栈的应用主要有括号匹配、后缀表达式计算、数制转换等。

应用 1

题目：括号匹配

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。
  

解析

遍历字符串，考察每一个字符 c。如果 c 为左括号，记录下来，希望c  能够与后面出现的同类型最近右括号匹配。

如果 c 为右括号，考察它能否与缓冲区中的（前一个）左括号匹配。

这个匹配过程，明显是后进先出 —— 栈。

代码

class Solution:
    def isValid(self, s):
        stack = []
        for ch in s:
            if ch in ['(', '[', '{']:
                stack.append(ch)
            else:
                if stack:
                    left = stack.pop()
                else:
                    return False
                if left == '[' and ch == ']' or left == '(' and ch == ')' or left == '{' and ch == '}':
                    continue
                else:
                    return False
        if not stack:
            return True
        else:
            return False

举一反三：最长括号匹配

给定字符串，可能不是完全匹配的，要求你找出最长的匹配的括号子串，返回其长度。可以简化为只包含 ‘(’、‘)’ 的问题尝试一下。

其基本思想仍然是栈，算法思想如下：

初始位置 p = -1 (-1 方便计算长度)，manlen=0。

遍历字符串，对于第 i 位字符 c，如果 c 为左括号，压栈（由于都是左圆括号，我们将位置 i 压栈）；

如果 c 为右括号，它一定与栈顶（如果栈不空）左括号匹配。

如果栈为空，以此为分界，该位置左边处理完毕（即后边再有匹配的长度也不叠加），将 p 设置为 i;

如果栈不空，出栈一个元素。出栈后栈空，i-p 为当前匹配成功的长度；栈仍不空，栈顶的元素记录上一次的位置 t，i-t 是当前匹配成功的长度。

当然有最大的长度的话更新 maxlen 。

此题不再贴代码，可自行尝试。

应用 2

题目：逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

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

说明：

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

解析

后缀表达式的计算是栈的重要应用，看下面的图理解一下运算符与二叉树的关系，因此栈与二叉树的遍历也是息息相关（后面学习树的时候还会用到）。

问题不难，代码如下：

class Solution:
    def evalRPN(self, tokens):
        stack = []
        for s in tokens:
            if s in ['+', '-', '*', '/']:
                b = stack.pop()
                a = stack.pop()
                if s == '+':
                    stack.append(a + b)
                elif s == '-':
                    stack.append(a - b)
                elif s == '*':
                    stack.append(a * b)
                else:
                    stack.append(a // b)
            else:
                stack.append(int(s))
        ans = int(stack.pop())
        return ans

后缀表达式在计算机中应用十分方便，是不需要带括号的优先级的。

应用 3：数值转换

数制转换问题其实不用栈也可解决，但其实基本思想仍然是后进先出，看下面这个例子：

2007₁₀ = 3727₈，十进制 2007 转换为八进制。

                               
登录/注册后可看大图

可以看出，余数转换成最后的数字是自下向上的，这就是栈的基本特点。