数据结构（3）：栈（下）
栈在括号匹配中的应用
假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序任意即 ([]()) 或 [([][])] 等均为正确的格式，[(]) 或 ([()) 或 (()] 均为不正确的格式。
考虑下列括号序列：
[ | ( | [ | ] | [ | ] | ) | ] |
|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
分析如下：
- 计算机接收第 1 个括号“[”后，期待与之匹配的第 8 个括号出现。
- 获得了第 2 个括号“(”后，此时第 1 个括号“[”暂时放在一边，而急迫期待与之匹配的第 7 个括号“)”出现。
- 获得了第 3 个括号“[”，此时第 2 个括号“(”暂时放在一边，而急迫与之匹配的第 4 个括号“]”出现。第三个括号的期待得到满足，消解之后，第 2 个括号的期待匹配又成为当前最紧迫的任务。
- 以此类推，可见该处理过程与栈的思想吻合。
算法的思想如下：
- 初始设置一个空栈，顺序读入括号。
- 若是右括号，者或者使置于栈顶的最急迫期待得以消解，或者是不合法的情况（括号序列不匹配，退出程序）。
- 若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的再战中的所有未消解的期待的急迫性降了一级。算法结束时，栈为空，否则括号序列不匹配。 算法的实现如下：
def parentheses_matching(parentheses): # 括号匹配
n = len(parentheses)
if n == 0:
return True
elif n == 1:
return False
stack = Stack()
if parentheses[0] in (')', ']'):
return False
else:
stack.push(parentheses[0])
for bracket in parentheses[1:]:
if stack.get_top() == '(' and bracket == ')':
stack.pop()
elif stack.get_top() == '[' and bracket == ']':
stack.pop()
else:
stack.push(bracket)
return True if stack.stack_empty()else False
栈在表达式求值中的应用
表达式求值是程序设计语言编译中一个最基本的问题，它的实现是栈应用的一个典型范例。中缀表达式不仅依赖运算符的优先级，而且还要处理括号。后缀表达式的运算符在操作数后面，在后缀表达式中已考虑了运算符的优先级，没有括号，只有操作数和操作符。中缀表达式 A+B*(C-D)-E/F 所对应的后缀表达式为 ABCD-*+EF/-。
将中缀表达式转换为后缀表达式的算法思想如下：
从左向右开始扫描中缀表达式；
遇到数字时，加入后缀表达式；
遇到运算符时：
- 若为‘(’，入栈；
- 若为‘)’，则依次把栈中的运算符加入后缀表达式，直到出现‘(’，从栈中删除‘(’；
- 若为出括号外的其他运算符，当其优先级高于除‘(’外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或遇到了一个左括号为止。
当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。
通过后缀表达式求值的过程为：顺序扫描表达式的每一项，然后根据它的类型作如下相应操作：若该项是操作数，则将其压入栈中；若该项是操作符<op>，则连续从栈中退出两个操作数 Y 和 X，形成运算指令 X<op>Y，并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。
算法的实现如下：
def isnumber(string): # 判断为字符串是否可以转换为数，不考虑负数和科学计数法
if string.isdecimal():
return True
strings = string.split('.')
if len(strings) == 2 and strings[0].isdecimal() and strings[1].isdecimal():
return True
return False
def check_priority(o1, o2): # 判断操作符 o2 的优先级是否大于等于操作符 o1 的优先级
return True if o1 in ('+', '-') and o2 in ('*', '/') or o1 in ('+', '-') and o2 in ('+', '-') or o1 in (
'*', '/') and o2 in ('*', '/')else False
def expression_evaluation(infix_expression): # infix_expression：中缀表达式，空格分隔操作数和操作符（含括号），括号全是小括号
infix_expression, postfix_expression, stack = [float(_) if isnumber(
_)else _ for _ in infix_expression.split()], [], Stack()
for e in infix_expression:
if type(e) == float:
postfix_expression.append(e)
elif check_priority(e, stack.get_top()):
while check_priority(e, stack.get_top()):
postfix_expression.append(stack.pop())
stack.push(e)
elif e == ')':
while stack.get_top() != '(':
postfix_expression.append(stack.pop())
stack.pop()
else:
stack.push(e)
while not stack.stack_empty():
postfix_expression.append(stack.pop())
for e in postfix_expression:
if e not in ('+', '-', '*', '/'):
stack.push(e)
else:
y, x = stack.pop(), stack.pop()
if e == '+':
stack.push(x+y)
elif e == '-':
stack.push(x-y)
elif e == '*':
stack.push(x*y)
else:
stack.push(x/y)
return stack.pop()
栈在递归中的应用
递归是一种重要的程序设计方法。简单地说，若一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。
它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。但在通常情况下，它的效率并不是太高。
以斐波那契数列为例，其定义为
这就是递归的一个典型例子，用程序实现时如下：
def fib(n): # 斐波那契数列的实现（递归）
if n == 0: # 边界条件
return 0
elif n == 1: # 边界条件
return 1
return fib(n-1)+fib(n-2) # 递归表达式
必须注意递归模型不能是循环定义的，其必须满足下面的两个条件：
- 递归表达式（递归体）。
- 边界条件（递归出口）。
递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。
在递归调用过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出等。而其效率不高的原因是递归调用过程中包含很多重复的计算。
所以，递归效率低下，但优点是代码简单，容易理解。
可以将递归算法转换为非递归算法，通常需要借助栈来实现这种转换。
总结
关于栈的应用就说到这里，下一回我们看到另一个操作受限的线性表：队列！
当然，我从今年开始已经入驻 B 站了！下面给出 B 站账号：新时代的运筹帷幄，喜欢的可以关注一下，看完视频不要忘记一键三连啊！
本文分享自 Python机器学习算法说书人 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
