Python 数据结构之栈和队列 —— （二）应用 (1) 括号匹配及后缀表达式
本帖最后由 zltzlt 于 2020-3-24 13:34 编辑来源于 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：数值转换
数制转换问题其实不用栈也可解决，但其实基本思想仍然是后进先出，看下面这个例子：
200710 = 37278，十进制 2007 转换为八进制。
https://img-blog.csdn.net/20180416102019746?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1dGlhbnRpYW4xNDEy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
可以看出，余数转换成最后的数字是自下向上的，这就是栈的基本特点。
页:
[1]