我正在用Python解决HackerRank“堆栈：平衡的括号”。


括号被认为是以下任意一个字符：(，
)，{，} ，[或]。

如果在闭合括号的左侧出现一个开口
括号（即(，[或{），则将两个括号视为配对。完全相同类型的
（即)，]或}）。共有三种
匹配的托槽对类型：[]，{}和()。

如果没有匹配的托槽对对，则
不平衡。匹配。例如，{[(])}不平衡，因为
{和}之间的内容不平衡。一对方括号
包围着一个不平衡的开口方括号(，而
括号对则包围着一个不平衡的方括号
方括号]。

按照这种逻辑，我们说如果满足以下条件，则认为括号序列是平衡的：

它不包含不匹配的括号。匹配的一对括号内的括号子集
也是匹配的一对
括号。给定括号，确定每个括号序列是否平衡。如果字符串是平衡的，则在新行上打印YES
；否则，在新行上打印NO。


我的代码：

def is_matched(expression):
    if len(expression) % 2 != 0:
        return False

    opening = ("(", "[", "{")
    closing = (")", "]", "}")
    mapping = {opening[0]:closing[0],
               opening[1]:closing[1],
               opening[2]:closing[2]}

    if expression[0] in closing:
        return False

    if expression[-1] in opening:
        return False

    closing_queue = []
    for letter in expression:
        if letter in opening:
            closing_queue.append(mapping[letter])
        elif letter in closing:
            if not closing_queue:
                return False

            if closing_queue[-1] == letter:
                closing_queue.pop()
            else:
                return False

    return True

t = int(input().strip())
for a0 in range(t):
    expression = input().strip()
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")


这里可以改进什么？如何使我的代码更惯用（Python代码）？

我的实现不好吗？为什么呢？

#1 楼

回顾

您的实现还不错，但是当然总有一些可以改进的地方。


使用if __name__ == '__main__'防护罩，看看它们在做什么。

opening和closing可以做得更简单


您可以在值上使用mapping来创建列表，
您可以list那些使用zip关键字的字典中的代码。


如果您需要添加很多极端情况，则您的算法可能不在其他地方。
考虑添加Testcases，Docstrings，或两者都以Doctest的形式出现。为了更轻松地测试算法。

替代代码

def is_matched(expression):
    """
    Finds out how balanced an expression is.
    With a string containing only brackets.

    >>> is_matched('[]()()(((([])))')
    False
    >>> is_matched('[](){{{[]}}}')
    True
    """
    opening = tuple('({[')
    closing = tuple(')}]')
    mapping = dict(zip(opening, closing))
    queue = []

    for letter in expression:
        if letter in opening:
            queue.append(mapping[letter])
        elif letter in closing:
            if not queue or letter != queue.pop():
                return False
    return not queue

if __name__ == '__main__':
    import doctest
    doctest.testmod()


评论

\ $ \ begingroup \ $
开幕=元组（'（{['）可能是开幕='（{['，和类似的关闭
\ $ \ endgroup \ $
–埃里克·威尔逊（Eric Wilson）
17年11月16日在21:42
\ $ \ begingroup \ $
还可以考虑编写映射= dict（（'（）'，'{}'，'[]'））。
\ $ \ endgroup \ $
– 200_success
17年11月17日在19:20
\ $ \ begingroup \ $
@SolomonUcko：在构造大小为3的常数字典的两种方式中，性能的差异为零。在这种情况下，选择一个可读性较低的选项是因为它“效率更高”。
\ $ \ endgroup \ $
– wchargin
17年11月18日在1:02
\ $ \ begingroup \ $
@SolomonUcko：更快。但是区别没有意义。这是一个耗时数秒的操作，仅执行一次；它离瓶颈还很遥远。这就是为什么人们说不要过早优化的原因。写出好的代码并写出可读的代码；只有这样，您才可以分析和优化热点。
\ $ \ endgroup \ $
– wchargin
17年11月18日在19:10
\ $ \ begingroup \ $
@Sigur是的，它将忽略表达式中不包含括号的所有其他字符，因此，如果您的表达式是一个很长的字符串，则可能有效
\ $ \ endgroup \ $
–处置不良
18年6月8日在12:01


#2 楼


如果输入的不是方括号怎么办？目前您忽略了这一点，也许您想出错。
您不需要制作opening和closing。您可以只使用mapping。

def is_matched(expression):
    mapping = dict(zip('({[', ')}]'))
    queue = []
    for letter in expression:
        if letter in mapping:
            queue.append(mapping[letter])
        elif letter not in mapping.values():
            raise ValueError('Unknown letter {letter}'.format(letter=letter))
        elif not (queue and letter == queue.pop()):
            return False
    return not queue



如果您不想忽略它或出错，则可以删除该支票，然后代码返回False：

def is_matched(expression):
    mapping = dict(zip('({[', ')}]'))
    queue = []
    for letter in expression:
        if letter in mapping:
            queue.append(mapping[letter])
        elif not (queue and letter == queue.pop()):
            return False
    return not queue


评论

\ $ \ begingroup \ $
现在我明白，您不需要打开和关闭什么意思。只需遍历映射即可。
\ $ \ endgroup \ $
–处置不良
17年11月16日在10:17
\ $ \ begingroup \ $
@Ludisposed起初，我的意思是因为您可以只使用一个字符串。但随后发现您根本不需要它们... :)
\ $ \ endgroup \ $
– Peilonrayz
17年11月16日在10:21
\ $ \ begingroup \ $
为了进一步增加您的答案，映射可以是一个常数
\ $ \ endgroup \ $
–立陶宛语
17年11月16日在11:42

#3 楼

要解决的另一件事是列表变量的误导性名称。物品按LIFO顺序进出，使它成为堆栈，而不是队列。

#4 楼

其他答案已经涵盖了可以在脚本中进行哪些改进，因此我将不再重复。只是想添加一个我发现有趣的选择。

基于消除的方法：

def f(my_string):
    brackets = ['()', '{}', '[]']
    while any(x in my_string for x in brackets):
        for br in brackets:
            my_string = my_string.replace(br, '')
    return not my_string


在每次迭代中，最里面的括号都被消除（替换为空字符串）。如果我们以空字符串结尾，那么我们最初的字符串是平衡的；

示例和注释：




最佳情况：s = '[](){}{}()[]'->在一次while迭代中减少为零。

最坏的情况：s = '({[[{()}]]})'->相同长度的字符串需要进行6次迭代（由内向外破坏）

您可以添加一些短路功能，以快速捕获具有打开和关闭支架的数量不均匀，这样您就不会浪费时间消除...

评论

\ $ \ begingroup \ $
@Cimbali尝试像这样编写它，看看是否最终得到了比上面的代码更简单，更容易理解的东西。
\ $ \ endgroup \ $
– Ma0
17年11月20日在8:42
\ $ \ begingroup \ $
@Cimbali我看不到任何
\ $ \ endgroup \ $
– Ma0
17年11月20日在8:48
\ $ \ begingroup \ $
@辛巴利辛苦了。因为它是“颠倒的”，所以只有收益被改变了
\ $ \ endgroup \ $
– Ma0
17年11月20日在9:21

#5 楼

此站点上最频繁的评论之一也适用于此：确保您的代码中有注释，不仅可以解释其所做的工作，还可以解释该注释与之相关的代码背后的原因。.下一位需要维护的人您的代码将对此表示感谢，并且如果您不得不在半年左右的时间内再次查看您的代码，您将很感激您立即付出了努力。

评论

\ $ \ begingroup \ $
您真的认为评论至关重要吗？我认为代码必须是不言自明的。如果需要大量评论，则可能是不好的或多余的。
\ $ \ endgroup \ $
– Vinicius巴西
17年11月19日，0：54


\ $ \ begingroup \ $
@vnbrs自从发明了程序设计以来，关于编写完备的代码与不言自明的代码之间的争论一直是激烈的。问题的核心在于，即使您认为自己的代码现在对自己来说是不言自明的，但在三年之内，刚从学校毕业，经验很少的受雇于维护您的代码的人至少也会很高兴从注释中了解代码中发生了什么。例如，我非常希望有注释来解释问题中的算法。不是解释代码，而是代码正在实现的算法。
\ $ \ endgroup \ $
– Nzall
17年11月19日在14:02
\ $ \ begingroup \ $
虽然代码可读性强，但注释应说明代码为什么要执行其工作，因为读者可能不熟悉算法或特殊情况。
\ $ \ endgroup \ $
–简单用户
18年5月6日在2:58

#6 楼

我正在测试这些算法，并且效果很好，但是在某些情况下，它们会失败。我将其视为使用堆栈的字符串，因为它可以用于编译器，并且可能不止括号，方括号和键。

测试这些情况，以及在所有情况下均可以工作，您做得很好：

string = "[]{}()[][][]"
print "Should be true"
print str(is_matched(string))

string = "([()][][{}])"
print "Should be true"
print str(is_matched(string))

string = "[(])"
print "Should be false"
print str(is_matched(string))

string = "[([])()({})]"
print "Should be true"
print str(is_matched(string))

string = "[(,,),(,,[])]"
print "Should be true but it fails"
print str(is_matched(string))

string = "[(,,,(,,[])]"
print "Should be false"
print str(is_matched(string))

string = "]"
print "Should be false"
print str(is_matched(string))

string = "["
print "Should be false"
print str(is_matched(string))

string = "{[{}][][({})]}"
print "Should be true"
print str(is_matched(string))

string = """
    public static void main(String args[])
    {
        System.out.println("Hello world");
    }
"""

print "Should be true"
print str(is_matched(string))

string = "[[[((({{{}}})))]]]"
print "Should be true"
print str(is_matched(string))


这是我的工作解决方案，适用于所有情况：

def pairs_stack(string, pairs = {'[': ']', '{': '}', '(': ')'}):

    opening = pairs.keys()

    closing = pairs.values()

    match = list()

    for s in string:
        if s in opening:
            match.insert(0, s)
        elif s in closing:
            if len(match) == 0:
                return False
            if match[0] == opening[closing.index(s)]:
                match.pop(0)
            else:
                return False

    if len(match) == 0:
        return True

    return False


测试：

import time

millis = float(time.time() * 1000)

string = "[]{}()[][][]"
print "Should be true"
print str(pairs_stack(string))

string = "([()][][{}])"
print "Should be true"
print str(pairs_stack(string))

string = "[(])"
print "Should be false"
print str(pairs_stack(string))

string = "[([])()({})]"
print "Should be true"
print str(pairs_stack(string))

string = "[(,,),(,,[])]"
print "Should be true"
print str(pairs_stack(string))

string = "[(,,,(,,[])]"
print "Should be false"
print str(pairs_stack(string))

string = "]"
print "Should be false"
print str(pairs_stack(string))

string = "["
print "Should be false"
print str(pairs_stack(string))

string = "{[{}][][({})]}"
print "Should be true"
print str(pairs_stack(string))

string = """
    public static void main(String args[])
    {
        System.out.println("Hello world");
    }
"""

print "Should be true"
print str(pairs_stack(string))

string = "[[[((({{{}}})))]]]"
print "Should be true"
print str(pairs_stack(string))

millis = float(time.time() * 1000) - millis
print "Result " + str(millis)