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

zltzlt

来源于 CSDN

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

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

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

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

应用 1

题目：括号匹配

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

有效字符串需满足：

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

解析

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

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

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

代码

1. class Solution:
   
2.     def isValid(self, s):
   
3.         stack = []
   
4.         for ch in s:
   
5.             if ch in ['(', '[', '{']:
   
6.                 stack.append(ch)
   
7.             else:
   
8.                 if stack:
   
9.                     left = stack.pop()
   
10.                 else:
    
11.                     return False
    
12.                 if left == '[' and ch == ']' or left == '(' and ch == ')' or left == '{' and ch == '}':
    
13.                     continue
    
14.                 else:
    
15.                     return False
    
16.         if not stack:
    
17.             return True
    
18.         else:
    
19.             return False

复制代码

举一反三：最长括号匹配

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

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

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

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

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

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

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

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

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

应用 2

题目：逆波兰表达式求值

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

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

说明：

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

解析

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

问题不难，代码如下：

1. class Solution:
   
2.     def evalRPN(self, tokens):
   
3.         stack = []
   
4.         for s in tokens:
   
5.             if s in ['+', '-', '*', '/']:
   
6.                 b = stack.pop()
   
7.                 a = stack.pop()
   
8.                 if s == '+':
   
9.                     stack.append(a + b)
   
10.                 elif s == '-':
    
11.                     stack.append(a - b)
    
12.                 elif s == '*':
    
13.                     stack.append(a * b)
    
14.                 else:
    
15.                     stack.append(a // b)
    
16.             else:
    
17.                 stack.append(int(s))
    
18.         ans = int(stack.pop())
    
19.         return ans

复制代码

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

应用 3：数值转换

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

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

                               
登录/注册后可看大图

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