下面看看如何构造括号匹配识别算法

从左到右扫描括号串,最新打开的左括号,应该匹配最先遇到的右括号这样,第一个左括号(最早打开),就应该匹配最后一个右括号(最后遇到)这种次序反转的识别,正好符合栈的特性!

在这里插入图片描述

在这里插入图片描述

def parCheck(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
print(parCheck('((()))'))
print(parCheck('(()'))

自己实现的代码:

def parCheck2(symbolString):
    s = Stack()
    for i in symbolString:
        if i == "(":
            s.push(i)
        else:
            if s.isEmpty():
                return False
            s.pop()
    if s.isEmpty():
        return True
    else:
        return False
print(parCheck2('((()))'))
print(parCheck2('(()'))

在实际的应用里, 我们会碰到更多种括号

如python中列表所用的方括号“[]”字典所用的花括号“{}”元组和表达式所用的圆括号“()”

这些不同的括号有可能混合在一起使用,

因此就要注意各自的开闭匹配情况

更多种括号的匹配

下面这些是匹配的

{ { ( [ ] [ ] ) } ( ) }
[ [ { { ( ( ) ) } } ] ]
[ ] [ ] [ ] ( ) { }

下面这些是不匹配的

( [ ) ] ( ( ( ) ] ) )
[ { ( ) ]

通用括号匹配算法:代码

需要修改的地方

碰到各种左括号仍然入栈
碰到各种右括号的时候需要判断栈顶的左括号是否跟右同一种类

def matches(open, close):
    opens = '([{'
    closes = ')]}'
    return opens.index(open) == closes.index(close)

def parCheck(symbolString):
    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 matches(top, symbol):
                    balanced = False
        index = index + 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

自己的代码实现:

def matches(open, close):
    opens = '([{'
    closes = ')]}'
    return opens.index(open) == closes.index(close)

def parCheck2(symbolString):
    s = Stack()
    for i in symbolString:
        if i in "([{":
            s.push(i)
        else:
            if s.isEmpty():
                return False
            else:
                top = s.pop()
                if not matches(top, i):
                    return False
    if s.isEmpty():
        return True
    else:
        return False
print(parCheck2('{{([][])}()}'))
print(parCheck2('[{()]'))

HTML/XML文档也有类似于括号的开闭标记, 这种层次结构化文档的校验、 操作也可以通过栈来实现

在这里插入图片描述

原文链接:https://blog.csdn.net/weixin_39020133/article/details/106870720

最后修改日期:2020年6月21日