我要评论栈的应用
简单括号匹配
- 类似于这样的表达式：(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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论