匹配平衡括号但必须检查保留顺序

Question

这是我的测试用例->{(<[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

Answer 1

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

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]>}}")