数据结构和算法(Python版):利用栈(Stack)实现括号的匹配问题
2023-09-11 14:21:08 时间
在平时写程序当中,我们会经常遇到程序当中括号的匹配问题,也就是在程序当中左括号的数量和右括号的数量必须相等。如果不相等的话则程序必然会报错。Hint:在读取程序的时候,读取的结果肯定是左边的全是左括号,右边的全是右括号,也就是一定是“(((( )))))”或者“((((((((((((( )))))))))))))))))”的形式,不可能是左右括号互相交互的形式,比如这种:“()()()()))((())((”, 编写过程序的同学就能够很轻松的知道这是为什么,因为先有左后有右,正好这个特性和栈的特性相符合,因此我们使用栈来解决这个问题,首先定义一个栈的类class:
class Stack(): def __init__(self): # 初始化一个空的列表 self.__list=[] # 压栈,也就是把元素从上方添加上去,但是这里我咋感觉是从下方添加进去的,顺序反了? def push(self,item): self.__list.append(item) def pop(self): return self.__list.pop()# 弹出栈顶的元素,同时删除栈顶的元素 # 返回栈顶的元素 def peek(self): return self.__list[len(self.__list)-1]# 也就是获取列表当中的最后一个元素 # 判断栈是否为空 def is_empty(self): return self.__list == [] # 计算栈的大小 def size(self): return len(self.__list) #返回当前栈的列表 def what(self): return self.__list
这也是栈最常见的定义,已经约定俗成了。现在则是算法的实现过程,我们可以用程序首先读取括号,比如已经给定了括号的字符串“((((( )))))”,我们将这个字符串传入进行括号匹配的函数当中。如果在循环读取括号当中,读取到了左括号,那么就进行入栈操作。之后左括号读取完毕,再进行右括号的读取操作,每读取到一次右括号,则进行出栈操作,也就是将之前进栈的左括号删除。如果左括号比右括号多,那么栈无论如何也无法为空,则括号不匹配,返回false。如果右括号比左括号更多,那么栈如果已经为空,程序还在读取右括号,说明右括号比左括号更多,这样程序则也返回false。在左括号和右括号的数量相等的时候,程序返回True,思路就是这样的,因此程序的代码如下:
def pipei(string): stack = Stack() i=0 while i<len(string): if string[i]=="(": stack.push(string[i]) elif string[i]==")": if stack.is_empty(): return False elif not stack.is_empty(): stack.pop() i=i+1 if stack.is_empty(): return True else: return False print("开始括号的匹配问题:") print(pipei("(((())))")) print(pipei("(((()))))))))))"))
输出为:
开始括号的匹配问题
True
False
那么真实的程序还需要我们自己写一个读取程序的文件,让我们过滤掉其他符号,只提取出保留括号的字符串,我们这里再写一个函数类实现这个功能:
def tiqukuohao(string): i=0 ls=[] while i<len(string): if string[i]=="(": ls.append(string[i]) elif string[i]==")": ls.append(string[i]) else: pass i=i+1 new_string="".join(ls)#将拿到的列表变成字符串,十分常规的操作 return new_string
然后调用函数,将一个括号匹配的放入函数,和另一个括号不匹配的字符串放入函数:
print(pipei(tiqukuohao("(sdvcsadc(asdasd(a)sdfsdf)asd)asdfas"))) print(pipei(tiqukuohao("sdvcsadc(asdasd(a)sdfsdf)asd)asdfas")))
最后输出为:
True
False
得解!
相关文章
- 小姐姐带你一起学:如何用Python实现7种机器学习算法(附代码)
- 【python cookbook】【数据结构与算法】12.找出序列中出现次数最多的元素
- 【python cookbook】【数据结构与算法】10.从序列中移除重复项且保持元素间顺序不变
- 【python cookbook】【数据结构与算法】9.在两个字典中寻找相同点
- 【python cookbook】【数据结构与算法】2 从任意长度的可迭代对象中分解元素
- 【python cookbook】【数据结构与算法】1将序列分解为单独的变量
- 【python cookbook】【数据结构与算法】14.对不原生支持比较操作的对象排序
- 【python cookbook】【数据结构与算法】6.在字典中将键映射到多个值上
- 【python cookbook】【数据结构与算法】2 从任意长度的可迭代对象中分解元素
- Python的IDE:基于Eclipse/MyEclipse软件的PyDev插件配置python的开发环境(不同python项目加载不同版本的python)—从而实现Python编程图文教程之详细攻略
- Python之ffmpeg-python:ffmpeg-python库的简介、安装、使用方法之详细攻略
- Python:python语言中与时间有关的库函数简介、安装、使用方法(获取当前时间/计算程序块前后运行时间/模型训练时间或耗费时间)之详细攻略
- Python的IDE:基于Eclipse/MyEclipse软件的PyDev插件配置python的开发环境(不同python项目加载不同版本的python)—从而实现Python编程图文教程之详细攻略
- 零基础学Python(第八章 for循环·超重点,本章会有几个简单的单层循环练习,后续会有针对算法的单独章节)
- 已解决2. Set PROTOCOL_BUPFERS_PYTHON_iMPLEMENTATION=python (but this will use pure-Python parsing and w
- 已解决(Python安装报错)Visit python.org to download an earlier version of Python.
- 智能优化算法——模拟退火法(Python实现)
- Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
- 【数据结构与算法Python实践系列】0 序
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-快速排序
- 推荐系统协同过滤-python实现(基于用户的协同过滤算法,基于物品的协同过滤算法,附数据集)
- python基础===八大排序算法的 Python 实现
- 【Leetcode刷题Python】改进的算法,高效求一个数的因子
- 【异常】前端ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- 【Python】1.python 删除文件夹和文件
- 【Python】蒙特卡洛模拟 | PRNG 伪随机数发生器 | LCG 线性同余算法 | 马特赛特旋转算法 | Python Random 模块