如何在 Python 中检查有效括号

在本教程中,您将学习在 Python 中检查有效括号。

给定一串括号,检查括号组合是否有效是一个流行的编码面试问题。 在接下来的几分钟内,您将学习解决这个问题的技术,并编写一个 Python 函数来验证给定的字符串。

什么是有效括号问题?

让我们通过回答这个问题开始我们的讨论,什么是有效括号问题?

给定一个包含简单括号、花括号和方括号字符的字符串: () [] {},您必须检查给定的括号组合是否有效。

有效的括号字符串满足以下两个条件:

  • 每个左括号必须有一个相同类型的匹配右括号。
  • 括号应以正确的顺序闭合。
  • 以下是一些有效和无效括号字符串的示例。

    test_str = "{}]" --> INVALID, ] was never opened
    test_str = "[{}]" --> VALID
    test_str = "[]" --> VALID
    test_str = "[]{}" --> VALID
    test_str = "[{]}" --> INVALID, brackets closed incorrectly!

    在我们解决问题的方法中,堆栈是将发挥关键作用的数据结构。 让我们在下一节中回顾堆栈的基础知识。

    重新审视堆栈数据结构

    堆栈是一种后进先出 (LIFO) 数据结构,您可以在其中将元素添加到堆栈顶部,也可以将它们从堆栈顶部移除。

    当你将一个元素添加到栈顶时,你执行一个推送操作,当你从栈顶移除一个元素时,你执行一个弹出操作。

    我们将使用以下两个规则来提出一组可以对括号字符串执行的操作。

    • 将所有开口支架推到堆栈上。
    • 如果遇到右括号,请从堆栈顶部弹出。

    让我们继续解决有效括号检查问题。

    如何检查有效括号

    将上述示例中的所有观察结果汇总在一起,我们得出以下结论。

    检查括号字符串的长度:如果奇数,则字符串无效

    由于每个左括号都必须有一个右括号,因此有效的字符串应该包含偶数个字符。 如果字符串的长度是奇数,您可以立即断定它的括号组合无效。

    # len(test_str) = 3 (odd); ] does not have an opening [
    test_str = "{}]"
    
    # len(test_str) = 3 (odd); ( does not have a closing )
    test_str = "[(]"
    
    # len(test_str) = 5 (odd); there's a spurious )
    test_str = "{())}"

    接下来看看当字符串中的字符数为偶数时如何处理

    括号字符串的长度是偶数:接下来呢?

    第一步:从左到右遍历字符串。 我们将字符串称为 test_str,并将字符串中的各个字符称为 char。

    第 2 步:如果第一个字符 char 是左括号 (、{ 或 [, push it to the top of the stack and proceed to the next character in the string.

    Step 3: Now, check if the next character (char) is an opening or a closing bracket.

    Step 3.1: If it’s an opening bracket, push it again onto the stack.

    Step 3.2: If you encounter a closing bracket instead, pop off the stack top, and proceed to step 4.

    Step 4: Here again, there are 3 possibilities based on the value popped off the stack:

    Step 4.1: If is an opening bracket of the same type, loop back to step 3.

      使用新的 Imgur GIF Creator 从视频创建 GIF 并添加文本

    Step 4.2: If it is an opening bracket of a different type, you can again conclude that it is not a valid parentheses string.

    Step 4.3: The final possibility is that the stack is empty. Again, this is the case of an invalid string, as you’ve run into a closing bracket that doesn’t have a matching opening bracket.

    Valid Parentheses String Examples Walkthrough

    Now let’s take three examples and walk through the above steps.

    📑 If you’ve already gotten the hang of how this works, feel free to skip to the next section.

    #1. As a first example, let test_str = “{()”.

    • { is the first character, and it’s an opening bracket, so you push it to the stack.
    • The next character ( is also an opening bracket, so go ahead and push it onto the stack as well.
    • The third character in the string ) is a closing bracket, so you have to pop off the stack top, which returns (.
    • At this point, you’ve reached the end of the string. But the stack still contains the opening { , which was never closed. So the given parentheses string test_str is invalid.

    #2. In this second example, let test_str = “()]”

    • 第一个字符 ( 是左括号;将其推入堆栈。
    • 第二个字符 ) 是右括号; 从堆栈顶部弹出,恰好是 ) – 相同类型的左括号。 继续下一个字符。
    • 第三个字符 ]是一个右方括号,你应该再次从栈顶弹出。 但是,如您所见,堆栈是空的——这意味着没有匹配的左括号 [. Hence, this string is invalid.
      如何在非智能电视上观看 Netflix(完整指南)

    #3. In this final example, test_str = “{()}”.

    • The first two characters {( are opening brackets, so push them onto the stack.
    • The third character is a closing ), so pop off the stack top – (.
    • The next character } is a closing curly brace, and when you pop the stack top, you get { – an opening curly brace.
    • After you have traversed the entire string, the stack is empty and test_str is valid! ✅

    📌 I’ve put together the following flowchart outlining the steps in the valid parentheses checking problem. You may save it for quick reference!

    In the next section, let’s see how to translate our concept to Python code.

    Python Program to Check for Valid Parentheses

    In Python, you can use the list to emulate a stack.

    You can use the .append() method to add elements to the end of the list. This is similar to pushing to the top of the stack.

    The .pop() method returns the last element from the list, and this is similar to the popping off the top of the stack – to remove the last-added element.

    So you now know how to implement the push and pop operations on a Python list, emulating the stack.

    As a next step, let’s answer the question: how to differentiate between opening and closing brackets?

      用于增长和参与的 13 大内容营销工具

    Well, you can use a Python dictionary – with the opening brackets ‘{‘, ‘[‘, ‘(‘ as the keys of the dictionary and the corresponding closing brackets ‘}’, ‘]’, ‘)’ 作为值。 您可以使用 .keys() 方法访问字典中的各个键。

    让我们用我们学到的所有知识来编写 is_valid() 函数的定义。

    理解函数定义

    通读以下包含函数定义的代码单元。 您可以看到我们已经将流程图中的步骤与上述说明结合使用。

    此外,我们还添加了一个 文档字符串 包含:

    • 函数的简短描述
    • 函数调用中的参数
    • 函数的返回值

    ▶ 您可以使用 help(is_valid) 或 is_valid.__doc__ 来检索文档字符串。

    def isValid(test_str):
      '''Check if a given parentheses string is valid.
    
      Args:
        test_str (str): The parentheses string to be validated
      
      Returns:
        True if test_str is valid; else False 
      '''
      # len(test_str) is odd -> invalid!
      if len(test_str)%2 != 0:
        return False
      # initialize parentheses dict
      par_dict = {'(':')','{':'}','[':']'}
      stack = []
      for char in test_str:
        # push opening bracket to stack
        if char in par_dict.keys():
          stack.append(char)
        else:
          # closing bracket without matching opening bracket
          if stack == []:
              return False
          # if closing bracket -> pop stack top
          open_brac = stack.pop()
          # not matching bracket -> invalid!
          if char != par_dict[open_brac]:
            return False
      return stack == []

    Python 函数 is_valid 检查括号字符串是否有效,其工作原理如下。

    • 函数 is_valid 接受一个参数 test_str,它是要验证的括号字符串。 它根据字符串 test_str 是否有效返回 True 或 False。
    • 在这里,stack 是模拟堆栈的 Python 列表。
    • par_dict 是 Python 字典,左括号作为键,右括号作为对应的值。
    • 在遍历字符串时,如果我们遇到任何使括号字符串无效的条件,该函数将返回 False 并退出。
    • 遍历字符串中的所有字符后,stack == [] 检查堆栈是否为空。 如果是,则 test_str 有效,并且函数返回 True。 否则,函数返回 False。

    现在,让我们继续进行一些函数调用来验证我们的函数是否正常工作。

    str1 = '{}[]'
    isValid(str1)
    # Output: True
    
    str2 = '{((}'
    isValid(str2)
    # Output: False
    
    str3 = '[{()}]'
    isValid(str3)
    # Output: True
    
    str4 = '[{)}]'
    isValid(str4)
    # Output: False
    
    str5 = '[[]}'
    isValid(str5)
    # Output: False

    从上面的代码片段中,我们可以得出结论,该函数按预期工作!

    结论🧑‍💻

    这是您所学内容的快速摘要。

    • 首先,向您介绍了有效括号检查的问题。
    • 接下来,您学习了一种使用堆栈作为选择的数据结构来解决问题的方法。
    • 然后,您学习了如何使用 Python 字典验证括号组合:使用左括号、键和相应的右括号作为值。
    • 最后,您定义了 Python 函数来检查给定的括号字符串是否有效。

    下一步,尝试在 techblik.com 的在线 Python 编辑器上编写问题代码。 如果您需要帮助,请随时重新访问本指南!

    查看更多 Python 教程。 编码快乐!🎉