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

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):&nbsp; &nbsp; """&nbsp; &nbsp; >>> check("{(<[testdata])>}")&nbsp; &nbsp; False&nbsp; &nbsp; >>> check("{just{test<of>Unbalanced}String')")&nbsp; &nbsp; False&nbsp; &nbsp; >>> check("{(<[ABalancedExample]>)}")&nbsp; &nbsp; True&nbsp; &nbsp; """&nbsp; &nbsp; bracket_matches = {&nbsp; &nbsp; &nbsp; &nbsp; '[': ']',&nbsp; &nbsp; &nbsp; &nbsp; '(': ')',&nbsp; &nbsp; &nbsp; &nbsp; '<': '>',&nbsp; &nbsp; &nbsp; &nbsp; '{': '}',&nbsp; &nbsp; }&nbsp; &nbsp; opening = set(bracket_matches.keys())&nbsp; &nbsp; closing = set(bracket_matches.values())&nbsp; &nbsp; stack = []&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; for ch in s:&nbsp; &nbsp; &nbsp; &nbsp; if ch in opening:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; stack.append(bracket_matches[ch])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; if ch in closing:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; try:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ch == stack.pop():&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return False&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; except IndexError:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # stack is empty&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return False&nbsp; &nbsp; return stack == []请注意，如果您需要允许不匹配的右括号，只要其余的括号仍然平衡，这就不够了，例如，包括以下测试会使此功能不兼容：>>> check("{{<[test}data]>}}")