数据结构与算法python栈的应用介绍

栈的应用

简单括号匹配

• 类似于这样的表达式：(5+6)*(7+8)/(4+3)
• 有些函数语言,如Lisp,在函数定义的时候会用到大量的括号
  比如: (defun square(n)
  (* n n))
  这个语句定义一个计算平方值的函数
• 括号遵循“平衡”规则
• 对括号是否正确匹配的识别是很多语言编译器的基础算法

构造括号匹配识别算法

• 从左到右扫描括号串，最新打开的左括号，应该匹配最先遇到的右括号
• 次序反转识别，符合栈的特性
  

from pythonds.basic.stack import Stack def parChecker(symbolString): s = Stack
    balanced = True index = 0 while index < len(symbolString) and balanced: #索引小于象征字符串并且平衡 symbol = symbolString[index] #象就等于字符串带索引 if symbol == "(": #左括号匹配 s.push(symbol) #进栈操作 else: if s.isEmpty(): #检查栈是否为空 balanced = False #就没达到平衡 else: s.pop() #删除 index = index + 1 if balanced and s.isEmpty(): #如果平衡而且是空栈 return True else: return False print(parChecker('((()))')) print(parChecker('(((()))')) 

更多括号匹配

• （）、{}、[],分别是列表、字典、元组和表达式
• 混合使用，注意开闭

from pythonds.basic.stack import Stack def parChecker(symbolString): s = Stack
    balanced = True index = 0 while index < len(symbolString) and balanced: #索引小于象征字符串并且平衡 symbol = symbolString[index] #象就等于字符串带索引 if symbol == "([{": #左括号匹配 s.push(symbol) #进栈操作 else: if s.isEmpty(): #检查栈是否为空 balanced = False #就没达到平衡 else: s.pop() #删除 if not matches(top, symbol): balanced = False index = index + 1 if balanced and s.isEmpty(): #如果平衡而且是空栈 return True else: return False def matches(open, close): opens = "([{" #matches匹配 closer = ")]}" return opens.index(open) == closers.index(close) print(parChecker('{{([][])}()}')) print(parChecker('[{()]')) 

通用括号匹配算法

• HTML/XML文档有类似于括号的开闭标记，这种层次结构化文档的校验、操作也可以通过栈来实现
  

计算机领域的任何问题都可以通过增加一个间接的中间层来解决

本文地址：https://blog.csdn.net/QWERTYULILINHAI/article/details/108875962