使用Python实现一个栈判断括号是否平衡
栈（Stack）在计算机领域是一个被广泛应用的集合，栈是线性集合，访问都严格地限制在一段，叫做顶（top）。 举个例子，栈就想一摞洗干净的盘子，你每次取一个新盘子，都是放在这一摞盘子的最上头，当你往里面添加盘子的时候，也是放在最上面，处在底部的盘子，你可能永远也用不到。 栈的最常见操作，有如下两个：
push(a) # 压入，将a压入的栈中 pop(） # 弹出，将栈的最后一个元素弹出
可是使用Python的列表数据结构，来模拟栈的操作，使用 append 来模拟 push ，使用列表的 pop 来模拟栈的 pop ，但是这样做有一个弊端，那就是列表原本自带的操作方法同样能够使用，可能会造成混乱。
栈的实现 下面就通过借助Python的列表，来自定义一个栈类：
class Stack(object):
"""使用数组实现一个栈"""
def __init__(self):
self.data = []
def push(self, num):
"""压栈操作"""
self.data.append(num)
def pop(self):
"""返回从栈中弹出的元素, 当栈为空的时候, 抛出IndexError"""
return self.data.pop()
def peek(self):
"""查看当前栈顶的元素, 当栈为空的时候, 抛出IndexError"""
return self.data[-1]
def __len__(self):
"""返回栈的长度, 调用len(obj)时会自动调用obj对象的__len__方法"""
return len(self.data)
def isEmpty(self):
"""判断栈是否为空"""
return True if len(self.data)==0 else False
def clear(self):
"""清空栈"""
self.data = []
def __repr__(self):
"""当前对象的表现形式, 在终点直接键入对象时会调用"""
return 'Stack_' + str(self.data)
def __str__(self):
"""当前对象的字符串表示, 使用print(obj)时会调用"""
return 'Stack_' + str(self.data)
以上代码实现了一个简单的基于列表的栈。
栈的应用 栈应用的一个很典型的例子，就是检查括号是否匹配。 例如： 每一个开始的 [ 后面，都应该跟着一个位置正确的 ] ，并且每一个 ( 后面，也应该跟着一个位置正确的结束的 ) .
(...)...(...)
(...)...(...
)...((...)
def isBalance(text):
"""栈的应用,检查括号是否平衡"""
result_stack = Stack()
for i in text:
if i in ['{', '[', '(']:
result_stack.push(i)
elif i in ['}', ']', ')']:
# 遇到结束括号的情况
if result_stack.isEmpty():
# 如果当前栈为空, 不匹配,返回False
return False
chFromStack = result_stack.pop()
if not ((chFromStack == '{' and i == '}' )
or (chFromStack == '[' and i == ']')
or (chFromStack == '(' and i == ')')):
# 如果不满足匹配条件, 则返回False
return False
# 遍历结束后, 如果结果栈为空, 则代表括号匹配, 栈不为空, 括号不匹配
return result_stack.isEmpty()
补充：Python中的栈
在python中，个人理解为栈可以用列表来代替
服从FILO：First In Last Out
其中入栈为（利用append函数）
stack = [] stack.append(<item>)
出栈为（利用pop函数）
stack.pop(-1) #stack.pop()也可
服从FIFO：First In First Out
入栈为：
stack = [] stack.append(<item>)
出栈为：
stack.pop(0)
总结
以上所述是小编给大家介绍的使用Python实现一个栈判断括号是否平衡，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！
相关推荐
-
python正则表达式中的括号匹配问题
问题: m = re.findall('[0-9]*4[0-9]*', '[4]') 可以匹配到4. m = re.findall('([0-9])*4([0-9])*', '[4]') 匹配不到4. 这是为什么呢?PS,这个是一个简化的说明,我要用的正则比这个复杂,所以要用到(),表示一个序列的匹配. 补充一点,我放在notepad++中用的时候,两种写法都能匹配出来,不知道为什么python中就不行了. 答案: python的正则中用()会进行匹配,所以返回结果是['',''],就是两个()
-
python用户评论标签匹配的解决方法
我们观察用户评论发现:属性词往往和情感词伴随出现,原因是用户通常会在描述属性时表达情感,属性是情感表达的对象.还发现:属性词和专用情感词基本都是名词或形容词(形谓词). 算法流程图如下: 评论数据如下: 代码如下: #encoding=utf-8 ############################# # # 功能:给定一些中文的产品评论,希望从中找到评价对象及评价词. # # @author:licl # ############################## fdata = ope
-
Python实现求解括号匹配问题的方法
本文实例讲述了Python实现求解括号匹配问题的方法.分享给大家供大家参考,具体如下: 这个在本科学习数据结构的时候已经接触很多了,主流的思想是借助栈的压入.弹出来进行匹配,至于python的话可以使用列表来完成这个操作,因为列表的append方法相当于栈的push方法,列表的pop方法相当于栈的pop方法. 主要的思路: 首先设置两个列表分别存放的是各种括号的开括号和闭括号,然后遍历给定的字符串,分如下几种情况: 1.字符串首字符出现在闭括号列表中,直接结束,输出错误 2.字符串长度不为偶数,
-
Python 匹配任意字符（包括换行符）的正则表达式写法
想使用正则表达式来获取一段文本中的任意字符,写出如下匹配规则: (.*) 结果运行之后才发现,无法获得换行之后的文本.于是查了一下手册,才发现正则表达式中,"."(点符号)匹配的是除了换行符"\n"以外的所有字符. 以下为正确的正则表达式匹配规则: ([\s\S]*) 同时,也可以用 "([\d\D]*)"."([\w\W]*)" 来表示. Web技术之家_www.waweb.cn 在文本文件里, 这个表达式可以匹配所有的英文
-
python实现括号匹配的思路详解
1.用一个栈[python中可以用List]就可以解决,时间和空间复杂度都是O(n) # -*- coding: utf8 -*- # 符号表 SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': '<'} SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.keys() def check(s): arr = [] for c in s: if c in SYMBOLS_L: # 左符号入栈 arr.appe
-
Python正则表达式实现截取成对括号的方法
本文实例讲述了Python正则表达式实现截取成对括号的方法.分享给大家供大家参考,具体如下: strs = '1(2(3(4(5(67)6)7)8)9)0' reg1 = re.compile('([()])∗') #一对括号 reg2 = re.compile('([()]|\([()]∗)*\)') #两对括号 reg3 = re.compile('([()]|\([()]∗|([()]|\([()]∗)*\))*\)') #三层 函数 #匹配成对括号正则表达式 def getReg(sel
-
Python实现的括号匹配判断功能示例
本文实例讲述了Python实现的括号匹配判断功能.分享给大家供大家参考,具体如下: 1.用一个栈[python中可以用List]就可以解决,时间和空间复杂度都是O(n) # -*- coding: utf8 -*- # 符号表 SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': '<'} SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.keys() def check(s): arr = [] for c
-
python使用正则表达式替换匹配成功的组
正则表达式简介 正则表达式,又称正规表示式.正规表示法.正规表达式.规则表达式.常规表示法(英语:Regular Expression,在代码中常简写为regex.regexp或RE),计算机科学的一个概念.正则表达式使用单个字符串来描述.匹配一系列符合某个句法规则的字符串.在很多文本编辑器里,正则表达式通常被用来检索.替换那些符合某个模式的文本. 许多程序设计语言都支持利用正则表达式进行字符串操作.例如,在Perl中就内建了一个功能强大的正则表达式引擎.正则表达式这个概念最初是由Unix中的工
-
使用Python实现一个栈判断括号是否平衡
栈(Stack)在计算机领域是一个被广泛应用的集合,栈是线性集合,访问都严格地限制在一段,叫做顶(top). 举个例子,栈就想一摞洗干净的盘子,你每次取一个新盘子,都是放在这一摞盘子的最上头,当你往里面添加盘子的时候,也是放在最上面,处在底部的盘子,你可能永远也用不到. 栈的最常见操作,有如下两个: push(a) # 压入,将a压入的栈中 pop() # 弹出,将栈的最后一个元素弹出 可是使用Python的列表数据结构,来模拟栈的操作,使用 append 来模拟 push ,使用列表的 pop
-
Python 输入一个数字判断成绩分数等级的方法
成绩分数等级为: 100-90 A 90-80 B 80-70 C 70-60 D 60以下 F 实现判断分数等级是一个很简单的数学问题,只要你输入的这个数字介于两个数字之间既可以判断出这个分数的等级. 代码如下: a=eval(input()) if a>=90: print("A") elif 90>a>=80: print("B") elif 80>a>=70: print("C") elif 70>a&
-
python数据结构之栈、队列及双端队列
目录 1.线性数据结构的定义 2.栈 2.1 栈的定义 2.2 栈的数据类型 2.3 用python实现栈 2.4 栈的应用 3. 队列 3.1 队列的定义 3.2 队列抽象数据类型 3.3 用python实现队列 3.3 队列的应用 4. 双端队列 4.1 双端队列的定义 4.2 双端队列抽象数据类型 4.3 用python实现双端队列 4.3 双端队列的应用 5.链表 5.1 链表定义 5.2 用python实现链表 前文学习: python数据类型: python数据结构:数据类型. py
-
Python算法之栈（stack）的实现
本文以实例形式展示了Python算法中栈(stack)的实现,对于学习数据结构域算法有一定的参考借鉴价值.具体内容如下: 1.栈stack通常的操作: Stack() 建立一个空的栈对象 push() 把一个元素添加到栈的最顶层 pop() 删除栈最顶层的元素,并返回这个元素 peek() 返回最顶层的元素,并不删除它 isEmpty() 判断栈是否为空 size() 返回栈中元素的个数 2.简单案例以及操作结果: Stack Operation Stack Contents Return
-
C++中用栈来判断括号字符串匹配问题的实现方法
本文实例主要实现:输入一个括号字符串,依次检验,若为左括号则入栈,若为右括号则出栈一个字符判断是否与之相对应,在最后还需判断栈是否为空,如果不为空则不匹配. 首先回顾栈的基本知识: 1.定义栈的结构体并初始化一个新栈: struct stack { char strstack[stacksize]; int top; }; void InitStack(stack &s) { s.top=-1; } 2.出栈和入栈操作: char Push(stack &s,char a) { if(s.
-
Python实现的栈（Stack）
前言 Python本身已有顺序表(List.Tupple)的实现,所以这里从栈开始. 什么是栈 想象一摞被堆起来的书,这就是栈.这堆书的特点是,最后被堆进去的书,永远在最上面.从这堆书里面取一本书出来,取哪本书最方便?肯定是最上面那本.栈这种数据结构的特点就是如此:后进先出(Last In First Out - LIFO),即最后被堆进去的数据,最先被拿出来. 栈的Python实现 栈可以用顺序表方式实现,也可以用链表方式实现.我大Python的内建数据结构太强大,可以用list直接实现栈,简
-
使用python制作一个解压缩软件
python实现解压缩的重要模块就是--zipfile,其次是os 安装zipfile模块 首先得安装zipfile模块,打开cmd输入一下命令即可安装 pip install zipfile os是python自带的库,所以无需另外安装,直接 import 即可 编写核心代码 压缩文件核心代码: def zip_file(): zip_name = path.get() +'.zip' # 获取绝对路径然后给压缩文件加上.zip结尾 z = zipfile.ZipFile(zip_name,'
-
Python可以实现栈的结构吗
栈(stack)又名堆栈,它是一种运算受限的线性表.在Python中可使用列表进行实现. 什么是栈? 栈(stack)又名堆栈,它是一种运算受限的线性表.其限制是仅允许在表的一端进行插入和删除运算.这一端被称为栈顶,相对地,把另一端称为栈底.向一个栈插入新元素又称作进栈.入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素:从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素. 如何实现? 在Python中使用列表来实现: #!/usr/bin/en
-
Python数据结构之栈详解
目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.2链栈的实现 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 0. 学习目标 栈和队列是在程序设计中常见的数据类型,从数据结构的角度来讲,栈和队列也是线性表,是操作受限的线性表,它们的基本操作是线性表操作的子集,但从数据类型的角度来讲,它们与线性表又有着巨大的不同.本节将首先介绍
-
python 中的条件判断语句的使用介绍
目录 1. 避免多层分支嵌套 2. 封装过于复杂的逻辑判断 3. 不同分支下的重复代码 4. 合理使用三元表达式 5. 常见技巧 5.1德摩根定律 5.2自定义类的魔法方法 5.3在条件判断中使用 all() / any() 5.4使用 try/while/for 中 else 分支 6. 常见陷阱 6.1与 None 值得比较 5.2and 和 or 的运算优先级 1. 避免多层分支嵌套 Python中利用缩进来替代 { }.如果多个 if 嵌套, 堪称 ” 嵌套 if 地狱 “ 下面的代码直