[Python知识库]python使用栈实现括号匹配

首先我们使用类定义一个栈(后进先出）

class Stack():   #定义一个栈
    def __init__(self) :   #类实例初始化
        self.items = []
    
    def isEmpty(self):    #判断栈是否为空
        return self.items == []
    
    def push(self,item):  #入栈
        return self.items.append(item)
    
    def pop(self):    #出栈
        return self.items.pop()
    
    def peek(self): #打印最后一个元素
        return self.items[len(self.items)-1]
    
    def size(self):   #栈包含元素的数目
        return len(self.items)

''' 简单的测试
s= Stack()
print(s.isEmpty())
s.push(4)
s.push("dog")
print(s.peek())
print(s.size())
print(s.pop())
print(s.size())
'''

其次，我们定义一个只能匹配“()”的函数

def parChecker(symbolString):    #实现简单的括号匹配 包括"()"
    s= Stack()
    balanced = True
    index = 0
    while index <len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index = index +1
    if balanced and s.isEmpty():
        return True
    else:
        return False

接着，我们定义可以匹配"( )" 、"[ ]" 、"{ }"的函数

def parChecker1(symbolString):    #实现复杂的括号匹配，包括"()"  "[]"  "{}"
    str1 = ['(','[','{']
    str2 = [')',']','}']
    s= Stack()
    balanced = True
    index = 0
    while index <len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()
                if not (str1.index(top)==str2.index(symbol)):
                    balanced = False
        index = index +1
    if balanced and s.isEmpty():
        return True
    else:
        return False

最后我们可以进行简单的测试

print(parChecker1('{((([])))}'))
print(parChecker1('((())'))

整体实现

class Stack():   #定义一个栈
    def __init__(self) :   #类实例初始化
        self.items = []
    
    def isEmpty(self):    #判断栈是否为空
        return self.items == []
    
    def push(self,item):  #入栈
        return self.items.append(item)
    
    def pop(self):    #出栈
        return self.items.pop()
    
    def peek(self): #打印最后一个元素
        return self.items[len(self.items)-1]
    
    def size(self):   #栈包含元素的数目
        return len(self.items)

''' 简单的测试
s= Stack()
print(s.isEmpty())
s.push(4)
s.push("dog")
print(s.peek())
print(s.size())
print(s.pop())
print(s.size())
'''

def parChecker(symbolString):    #实现简单的括号匹配 包括"()"
    s= Stack()
    balanced = True
    index = 0
    while index <len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index = index +1
    if balanced and s.isEmpty():
        return True
    else:
        return False


def parChecker1(symbolString):    #实现复杂的括号匹配，包括"()"  "[]"  "{}"
    str1 = ['(','[','{']
    str2 = [')',']','}']
    s= Stack()
    balanced = True
    index = 0
    while index <len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()
                if not (str1.index(top)==str2.index(symbol)):
                    balanced = False
        index = index +1
    if balanced and s.isEmpty():
        return True
    else:
        return False

print(parChecker1('{((([])))}'))
print(parChecker1('((())'))

主要思想

1、将’{((([])))}’ 从左到右依次匹配，如果遇到"([{" ，那么入栈，如果遇到")]}" ，出栈，出来的是“( [ {”中的一个，和此时的从左到右扫描得到的" ) ] } "进行对比，如果相同则没啥大毛病，继续匹配。

2、
3、如果不能理解可以观看视频：数据结构栈实现括号匹配讲解