Python中的平衡Parentheses检查器

Question

我希望得到关于代码本身(风格、性能优化(空间和时间))以及算法的反馈(因为我认为这通常是使用堆栈实现的)。

我在这里提出的假设是，使用平衡括号只有两个限制；一个是有相同数量的开括号和结束括号，另一个是在任何时候都不存在比开括号更多的结束括号。

考虑到这一点，我使用一个简单的计数器来实现我的平衡括号检查器，它在每个打开的paren中递增，在每个结束的paren中递减。

函数中的两个“检查”是计数器永远不会变成负值(如果在任何一点上返回False )，并且在结束时计数器为0。

def paren_checker(string):
    counter = 0
    for c in string:
        if c == '(':
            counter += 1
        elif c == ')':
            counter -= 1
        if counter < 0:
            return False

    if counter == 0:
        return True
    return False

Answer 1

下面是允许以下三种类型的算法的改进版本：

def add_vectors(a, b):
    for i, x in enumerate(b):
        a[i] += x  # a is a list, so it supports item assignment

    return a


def is_balanced(string):
    #         (  [  {
    counts = [0, 0, 0]

    # dict of tuples to add based on char (like a switch statement)
    d = {'(': ( 1, 0, 0), '[': ( 0, 1, 0), '{': ( 0, 0, 1),
         ')': (-1, 0, 0), ']': ( 0,-1, 0), '}': ( 0, 0,-1)}

    for char in string:
        try:
            counts = add_vectors(counts, d[char])
        except KeyError:  # char is not in dict, so it isn't '(', '{', etc.
            continue

        if -1 in counts:  # close without open
            return False

    return counts == [0, 0, 0]  # will resolve to initial state if correct

当然，这仍然不包括{[}]的情况，这在非堆栈实现中是常见的。

Answer 2

我将用return counter == 0替换最后一行，因为它更紧凑，更易于阅读。

Answer 3

我根据纸上的几个例子检查了你的算法，如果我没有漏掉任何东西的话，它实际上应该能工作。尽管如此，它还是有一个缺点。如果您想引入新类型的括号(如大括号、{}或平方括号[] )，它可能不能正常工作，扩展它可能不容易。当您使用堆栈数据结构时，它将在没有重大问题的情况下得到处理。