这篇文章将使用python实现栈的应用之括号匹配
首先,明确需求,需求是:
1,通过控制台输入一串字符串,判断是否全为括号;
2,将括号分为左括号和右括号;
3,创建一个栈,将左括号入栈,同时从字符串中取出右括号,进行匹配,若匹配成功,则该左括号出栈,否则右括号入新栈;
4,当字符串匹配完成时,对两个栈的长度进行匹配,若长度相等且为零,则表示匹配成功,若长度相等且不为零,则对栈内元素进行匹配,若重新匹配使得双栈长度为零,则表示匹配成功,否则失败
其次,对于括号匹配问题,我们需要创建一个字典以便于进行匹配,示例如下:
match_dict={")":"(","]":"[","}":"{"}
因此,当进行括号匹配时,我们可以使用for循环遍历输入字符串,并使用如下代码段进行匹配判断
get_=stack.pop_()#从定义好的栈中获取已经入栈的左括号
for i in {")","]","}"}:
if match_dict[i] == get_ :
stack.pop()#匹配成功,将该左括号出栈
根据括号匹配的需求,栈的设计需要包含:定义,长度获取,压栈,获取栈顶元素,弹栈
栈的设计完整代码如下:
class Stack:
def __init__(self):
self.items=[]
def pop_(self):
return self.items[-1]
def pop(self):
return self.items.pop()
def get_length(self):
return len(self.items)
def push(self,elem):
return self.items.append(elem)
根据括号匹配的需求,设计匹配函数如下:
def Match_blankets(string):
#实例化两个栈以备用
stack=Stack()
stack2=Stack()
#创建匹配字典,便于匹配
match_dict={")":"(","]":"[","}":"{"}
#遍历括号字符串,匹配开始
for i in string:
#左括号压栈
if i in {"(","[","{"}:
stack.push(i)
#判断右括号是否与左括号栈顶元素匹配,匹配则弹出左括号栈顶元素,不匹配则压入新栈
elif i in {")","]","}"}:
get_=stack.pop_()
if get_ == match_dict[i]:
stack.pop()
else:
stack2.push(i)
else:
print("括号不纯!")
return -1
#判断第一轮匹配是否完全,不完全则进入下一步匹配
if stack.get_length() != stack2.get_length():
print("匹配失败!")
return -1
else:
#进入下一步匹配,重复遍历其中一个栈内的元素,直到其中一个栈空或者遍历完成
for i in stack2.items:
get_new = stack.pop_()
if get_new == match_dict[i]:
stack.pop()
stack2.pop()
#最后进行一次判断,若匹配完全,则双栈长度均为零
if stack.get_length() == 0 and stack2.get_length() == 0:
print("匹配成功!")
return 0
最后,完整代码如下:
class Stack:
def __init__(self):
self.items=[]
def pop_(self):
return self.items[-1]
def pop(self):
return self.items.pop()
def get_length(self):
return len(self.items)
def push(self,elem):
return self.items.append(elem)
def Match_blankets(string):
stack=Stack()
stack2=Stack()
match_dict={")":"(","]":"[","}":"{"}
for i in string:
if i in {"(","[","{"}:
stack.push(i)
elif i in {")","]","}"}:
get_=stack.pop_()
if get_ == match_dict[i]:
stack.pop()
else:
stack2.push(i)
else:
print("括号不纯!")
return -1
if stack.get_length() != stack2.get_length():
print("匹配失败!")
return -1
else:
for i in stack2.items:
get_new = stack.pop_()
if get_new == match_dict[i]:
stack.pop()
stack2.pop()
if stack.get_length() == 0 and stack2.get_length() == 0:
print("匹配成功!")
return 0
if __name__=="__main__":
string=input("请输入括号!")
Match_blankets(string)
文章来源地址https://www.toymoban.com/news/detail-413701.html
文章来源:https://www.toymoban.com/news/detail-413701.html
到了这里,关于栈的应用--括号匹配(python篇)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!