python中栈的标准实现方法,python数据分析栈

　　本文主要详细介绍Python中的堆栈。本文中的示例代码非常详细，具有一定的参考价值。感兴趣的朋友可以参考一下，希望能帮到你。

　　00-1010匹配括号匹配符号摘要

　　为了解决这个问题，我们需要注意一个重要的现象。当从左向右处理括号时，右不匹配左括号必须匹配下一个遇到的第一个右括号。此外，在最后一个位置的右括号被处理之前，第一个位置的左括号的匹配可能不会完成。此外，右括号的顺序与匹配的左括号的顺序相反。这个规则暗示着栈可以用来解决括号匹配的问题。

　　一旦你意识到栈是用来保存括号的，这个算法就很容易写了。

　　从一个空的堆栈开始，从左到右处理括号。如果遇到左括号，它将是堆栈的push操作的加入栈，这意味着后面需要一个匹配的右括号。

　　相反，如果遇到右括号，就调用栈的pop操作。只要栈中所有的左括号能满足匹配的右括号，则整个括号串匹配；如果堆栈中的左括号找不到匹配的右括号，则括号字符串不匹配。处理完匹配的括号字符串后，堆栈应该为空。

　　简单来说就是：扫描括号串，把左括号放入栈中，遇到右括号，从栈顶取出一对左括号，互相抵消，直到最后。如果括号匹配，那么堆栈最后应该是空的，括号字符串刚刚完成扫描。

　　代码实现如下：

　　类别堆栈：

　　def __init__(self):

　　self.items=[]

　　def isEmpty(self):

　　return self.items==[]

　　定义推送(自身，项目):

　　self.items.append(项目)

　　def pop(自身):

　　返回self.items.pop()

　　def parChecker(符号字符串):

　　S=Stack() #构建堆栈

　　Balanced=True #默认情况下，匹配标志为True，表示匹配。

　　Index=0 # Index用于提取字符

　　#当索引小于字符串长度并且匹配标志为真时

　　而索引len(symbolString)和balanced:

　　#取字符串当前位的字符

　　symbol=symbolString[index]

　　#如果当前字符是左括号，则堆栈

　　if symbol==(:

　　s.push(符号)

　　#如果当前字符不是左括号(则当前字符是右括号)

　　else:

　　#堆栈是空的

　　if s.isEmpty():

　　#匹配标志设置为False，表示匹配失败(右括号)。

　　 balanced = False

　　 # 栈不是空的抵消栈顶的左括号

　　 else:

　　 s.pop()

　　 # 索引向后移动一位

　　 index = index + 1

　　 # 循环结束如果匹配成功并且栈空了

　　 if balanced and s.isEmpty():

　　 return True

　　 else:

　　 return False

　　注意，balanced 的初始值是True，这是因为一开始没有任何理由假设其为False 。如果当前的符号是左括号，它就会被压入栈中（第27行）。注意第36行，仅通过pop()将一个元素从栈顶移除。由于移除的元素一定是之前遇到的左括号，因此并没有用到pop()的返回值。在第42~45行，只要所有括号匹配并且栈为空，函数就会返回True ，否则返回False。

匹配符号

　　符号匹配是许多编程语言中的常见问题，括号匹配问题只是它的一个特例。我们已经会了匹配括号的方法，那么现在我们来试试匹配符号。

　　匹配符号是指正确地匹配和嵌套左右对应的符号。

　　例如，在Python中，方括号[和]用于列表；花括号{和}用于字典；括号(和)用于元组和算术表达式。只要保证左右符号匹配，就可以混用这些符号。以下符号串是匹配的，其中不仅每一个左符号都有一个右符号与之对应，而且两个符号的类型也是一致的。

{ { ( [ ] [ ] ) } ( ) }
[ [ { { ( ( ) ) } } ] ]
[ ] [ ] [ ] ( ) { }

　　以下符号则是不匹配的：

( [ ) ]
( ( ( ) ] ) )
[ { ( ) ]

　　要处理新类型的符号，我们扩展上面的括号匹配检测代码。

　　即每一个左符号都将被压入栈中，以待之后出现对应的右符号。

　　唯一的区别在于，当出现右符号时，必须先检测其类型是否与栈顶的左符号类型相匹配。如果两个符号不匹配，那么整个符号串也就不匹配。同样，如果整个符号串处理完成并且栈是空的，那么就说明所有符号正确匹配。

　　代码实现如下：

class Stack:
　　 def __init__(self):
　　 self.items = []
　　 def isEmpty(self):
　　 return self.items == []
　　 def push(self, item):
　　 self.items.append(item)
　　 def pop(self):
　　 return self.items.pop()
　　def parChecker(symbolString):
　　 s = Stack() # 构造栈
　　 balanced = True # 匹配标志 默认为True 表示匹配
　　 index = 0 # 索引 用来取字符
　　 # 当 索引小于字符串的长度 并且 匹配标志为True 时
　　 while index < len(symbolString) and balanced:
　　 # 取字符串当前位的字符
　　 symbol = symbolString[index]
　　 # 如果当前字符属于 左括号集 则入栈
　　 if symbol in ([{:
　　 s.push(symbol)
　　 # 如果当前字符 不是左括号(那当前就是右括号)
　　 else:
　　 # 并且栈是空的
　　 if s.isEmpty():
　　 # 匹配标志设置为 False 表示匹配失败(孤零零的右括号)
　　 balanced = False
　　 # 栈不是空的 拿出栈顶的左括号进行类型匹配
　　 else:
　　 top = s.pop()
　　 # 类型匹配失败
　　 if not matches(top, symbol):
　　 balanced = False
　　 # 索引向后移动一位
　　 index = index + 1
　　 # 循环结束 如果匹配成功 并且 栈空了
　　 if balanced and s.isEmpty():
　　 return True
　　 else:
　　 return False
　　def matches(left, right):
　　 lefts = "([{"
　　 rights = ")]}"
　　 # 调用字符串的index方法，index() 方法查找指定值的首次出现，并返回索引。
　　 # 左右索引对应，表明符号匹配
　　 return lefts.index(left) == rights.index(right)

　　测试结果如下图所示：

　　以上两个例子说明，在处理编程语言的语法结构时，栈是十分重要的数据结构。几乎所有记法都有某种需要正确匹配和嵌套的符号。除此之外，栈在计算机科学中还有其他一些重要的应用场景，让我们继续探索。

总结

　　本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注盛行IT软件开发工作室的更多内容!

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

python中栈的标准实现方法,python数据分析栈

目录

匹配符号

总结

相关文章阅读