欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-01-13 10:59:34
栈的应用简单括号匹配类似于这样的表达式:(5+6)*(7+8)/(4+3)有些函数语言,如Lisp,在函数定义的时候会用到大量的括号比如: (defun square(n)(* n n))这个语句定义一个计算平方值的函数括号遵循“平衡”规则对括号是否正确匹配的识别是很多语言编译器的基础算法构造括号匹配识别算法从左到右扫描括号串,最新打开的左括号,应该匹配最先遇到的右括号次序反转识别,符合栈的特性from pythonds.basic.stack import Stack...

栈的应用

简单括号匹配

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

构造括号匹配识别算法

  • 从左到右扫描括号串,最新打开的左括号,应该匹配最先遇到的右括号
  • 次序反转识别,符合栈的特性
    数据结构与算法python栈的应用介绍
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文档有类似于括号的开闭标记,这种层次结构化文档的校验、操作也可以通过栈来实现
    数据结构与算法python栈的应用介绍

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

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