时间戳

首页 > 解决方案 > 匹配平衡括号，但必须检查是否保留顺序

python - 匹配平衡括号，但必须检查是否保留顺序

问题描述

类似的问题

这是我的测试用例->

{(<[testdata])>}-> 假的

{just{test<of>Unbalanced}String')-> 错误

{(<[ABalancedExample]>)}-> 真

opening = ['[','(','<','{']
closing = [']',')','>','}']

我的代码不适用于 {(<[testdata])>} 因为括号的顺序没有得到照顾

def check(str):
    count = 0
    if not str:
        return None
    for i in str:
        if i in opening:
            count += 1
        elif i in closing:
            count -= 1
        if count < 0:
            return False
    return count == 0

标签： python

解决方案

这是一个堆栈问题。幸运的是，列表默认作为堆栈工作。

def check(s):
    """
    >>> check("{(<[testdata])>}")
    False
    >>> check("{just{test<of>Unbalanced}String')")
    False
    >>> check("{(<[ABalancedExample]>)}")
    True
    """

    bracket_matches = {
        '[': ']',
        '(': ')',
        '<': '>',
        '{': '}',
    }

    opening = set(bracket_matches.keys())
    closing = set(bracket_matches.values())
    stack = []
    
    for ch in s:
        if ch in opening:
            stack.append(bracket_matches[ch])
            continue
        if ch in closing:
            try:
                if ch == stack.pop():
                    continue
                else:
                    return False
            except IndexError:
                # stack is empty
                return False
    return stack == []

请注意，如果您需要允许不匹配的右括号，只要其余括号仍然平衡，这将变得不够，例如，包括以下测试会使此功能不兼容：

>>> check("{{<[test}data]>}}")

推荐阅读