Python数据结构与算法中的栈怎么实现

魁首哥

作者

Python数据结构与算法中的栈怎么实现

这篇文章主要介绍“Python数据结构与算法中的栈怎么实现”，在日常操作中，相信很多人在Python数据结构与算法中的栈怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Python数据结构与算法中的栈怎么实现”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

匹配括号

接下来，我们使用栈解决实际的计算机科学问题。

比如我们都写过这样所示的算术表达式， ( 5 + 6 ) ∗ ( 7 + 8 ) / ( 4 + 3 ) (5 + 6) * (7 + 8) / (4 + 3) (5+6)∗(7+8)/(4+3)，其中的括号用来改变计算顺序，或提升运算优先级。

匹配括号是指每一个左括号都有与之对应的一个右括号，并且括号对有正确的嵌套关系。

正确的嵌套关系： ( ( ) ( ) ( ) ( ) ) (()()()()) (()()()())、 ( ( ( ( ) ) ) ) (((()))) (((())))、 ( ( ) ( ( ( ) ) ( ) ) ) (()((())())) (()((())()))
错误的嵌套关系： ( ( ( ( ( ( ( ) ) ((((((()) ((((((())、 ( ) ) ) ())) ()))

我们的挑战就是编写一个算法，它从左到右读取一个括号串(不包括其他数字与运算符)，然后判断其中的括号是否匹配。

为了解决这个问题，需要注意到一个重要现象。当从左到右处理括号时，最右边的无匹配左括号必须与接下来遇到的第一个右括号相匹配。并且，在第一个位置的左括号可能要等到处理至最后一个位置的右括号时才能完成匹配。而且右括号的出现顺序，与其相匹配的左括号的出现顺序相反。这一规律暗示着能够运用栈来解决括号匹配问题。

一旦认识到用栈来保存括号，算法编写起来就会十分容易。

由一个空栈开始，从左往右依次处理括号。如果遇到左括号，便通过栈的push操作将其加入栈中，以此表示稍后需要有一个与之匹配的右括号。

反之，如果遇到右括号，就调用栈的pop操作。只要栈中的所有左括号都能遇到与之匹配的右括号，那么整个括号串就是匹配的；如果栈中有任何一个左括号找不到与之匹配的右括号，则括号串就是不匹配的。在处理完匹配的括号串之后，栈应该是空的。

用简单的话说就是：扫描括号串，左括号入栈，遇见右括号，从栈顶取出来一个左括号配对儿，互相抵消，直到最后。如果括号匹配，那么栈最后就该是空的，并且括号串刚好扫描完毕。

代码实现如下：

classStack:def__init__(self):self.items=[]defisEmpty(self):returnself.items==[]defpush(self,item):self.items.append(item)defpop(self):returnself.items.pop()defparChecker(symbolString):s=Stack()#构造栈balanced=True#匹配标志默认为True表示匹配index=0#索引用来取字符#当索引小于字符串的长度并且匹配标志为True时whileindex

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