检查支架是否正确配对

Question

我有很多括号，比如

li1 = ['{','[','(',')',']','}' ]  # correctly paired
li2 = ['[','(',')',']']           # correctly paired
li3 = ['{','[','}',']',')','}']   # incorrectly paired

如何使用for循环比较第一个元素和最后一个元素，然后比较下一个元素和最后一个元素？你知道吗

我的解决办法是

if len(li) %2 == 0:
    for i in range(len(li)):
         if li[0] == li[-1]: #and          if li[1] == li[-2]: and so on.....
           return True
        else:
           return False
else:
    return False

但是这会为li3返回错误的结果。你知道吗

Answer 1

你的错误是：

• 使用索引0和-1代替i
• 比较左括号和右括号

所以，我的解决方案是：

def check(li):
  length = len(li)
  if length % 2 == 0:
    pairs = {'}': '{', ']': '[', ')': '('}
    stack = []
    for i in range(length):
      if li[i] in pairs.values():
        stack.append(li[i])
      elif li[i] in pairs.keys() and stack[-1] == pairs[li[i]]:
        stack.pop()
    return len(stack) == 0
  else:
    return False

我使用堆栈作为开始括号，如果它找到结束括号，它将弹出堆栈。最后，检查堆栈是否被清除。你知道吗

使用测试用例测试结果

li1 = ['{','[','(',')',']','}' ]
check(li1)
>>> True
li2 = ['[','(',')',']']
check(li2)
>>> True
li3 = ['{','[','(',']',')','}']
check(li3)
>>> False

Answer 2

您在代码中犯了3个错误：

• 您总是返回进行第一次检查；您需要推迟判断，直到您测试了所有对。你知道吗
• 您没有使用i计数器，因此循环只测试第一个和最后一个元素
• 您需要将左括号映射到右括号；'[' == ']'永远不会是真的，但是配对是正确的。你知道吗

我不需要使用计数器，使用^{}和^{}从开始到结束对元素进行配对；您只需要测试li的前半部分：

def test_pairs(li, _map={'(': ')', '[': ']', '{': '}'}):
    l = len(li)
    if l % 2 == 1:
        # odd length list, can't be paired
        return False

    # pair up the first half with the second half, reversed
    for first, second in zip(li[:l // 2], reversed(li)):
        if _map.get(first) != second:
            # Either first is not a left bracket, or right bracket is not a match
            return False

    # everything tested, so everything matched
    return True

演示：

>>> test_pairs(['{', '[', '(', ')', ']', '}'])
True
>>> test_pairs(['[', '(', ')', ']'])
True
>>> test_pairs(['{', '[', '(', ']', ')', '}'])
False

然而，对嵌套的单个维度进行测试通常是不够的。大多数实际情况都包含多个分组，比如['(', '{', '}', '[', ']', ')']（注意{、}和[，]对不是嵌套的！）。如果需要匹配这种情况，则需要使用堆栈：

def test_groupings(li, _map={'(': ')', '[': ']', '{': '}'}):
    stack = []
    for el in li:
        if el in _map:
            # opening element, add to stack to look for matching close
            stack.append(el)
        elif not stack or _map[stack[-1]] != el:
            # not an opening element; is the stack is empty?
            # or is this element not paired with the stack top?
            return False
        else:
            # closing element matched, remove opening element from stack
            stack.pop()

    # if the stack is now empty, everything was matched
    return not stack

这样仍然可以正确地检测您的案例，*但也会返回True作为我的反例：

>>> test_groupings(['{', '[', '(', ')', ']', '}'])
True
>>> test_groupings(['[', '(', ')', ']'])
True
>>> test_groupings(['{', '[', '(', ']', ')', '}'])
False
>>> test_groupings(['(', '{', '}', '[', ']', ')'])
True