如何在Python中检查有效的括号

在这个教程中，你将学习如何在Python中检查有效的括号。

给定一个括号字符串，检查括号组合是否有效是一个常见的面试题。在接下来的几分钟里，你将学习解决这个问题的技巧，并编写一个验证给定字符串的功能以供使用。

什么是有效的括号问题？

让我们开始讨论，回答问题：什么是有效的括号问题？

给定一个包含简单括号、花括号和方括号的字符串： () [] {}，你需要检查给定的括号组合是否有效。

一个有效的括号字符串需要满足以下两个条件：

1. 每个开括号必须有一个相匹配的闭括号。
2. 括号必须以正确的顺序关闭。

下面是一些有效和无效括号字符串的示例。

test_str = "{}]" --> 无效，]没有被打开
test_str = "[{}]" --> 有效
test_str = "[]" --> 有效
test_str = "[]{}" --> 有效
test_str = "[{]}" --> 无效，括号关闭错误！

在我们的问题解决方法中，栈是一个关键的数据结构。接下来我们将回顾栈的基础知识。

栈数据结构回顾

栈是一种后进先出（LIFO）的数据结构，你可以将元素添加到栈顶，也可以从栈顶移除元素。

当你将元素添加到栈顶时，你执行的是一个push操作；当你从栈顶移除元素时，你执行的是一个pop操作。

我们将使用以下两个规则来得到一个可以应用于括号字符串的操作集。

• 将所有开括号推入栈中。
• 如果遇到闭括号，弹出栈顶元素。

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

如何检查有效的括号

将上面示例的所有观察结果结合起来，我们有以下内容。

检查括号字符串的长度：如果是奇数，则字符串无效

由于每个开括号都必须有一个闭括号，一个有效的字符串应该包含偶数个字符。如果字符串的长度为奇数，你可以立即得出它包含无效的括号组合。

# len(test_str) = 3 (奇数)；] 没有被打开
test_str = "{}]"

# len(test_str) = 3 (奇数)；( 没有被关闭
test_str = "[(]"

# len(test_str) = 5 (奇数)；多出一个 )
test_str = "{())}"

接下来，让我们看看当字符串中的字符数是偶数时我们如何解决这个问题。

括号字符串的长度是偶数：接下来做什么？

步骤1：从左到右遍历字符串。我们将字符串称为test_str，字符串中的个别字符称为char。

步骤2：如果第一个字符char是开括号(，{，或[，将其推入栈顶并继续处理字符串的下一个字符。

步骤3：现在，检查下一个字符（char）是开括号还是闭括号。

步骤3.1：如果是开括号，再次将其推入栈中。

步骤3.2：如果遇到闭括号，弹出栈顶元素，并继续执行步骤4。

步骤4：这里根据从堆栈中弹出的值有3种可能性：

步骤4.1：如果是相同类型的开括号，回到步骤3。

步骤4.2：如果是不同类型的开括号，你可以再次得出它不是有效的括号字符串。

步骤4.3： 最后一种可能性是堆栈为空。同样，这是一个无效的字符串，因为你遇到了一个没有匹配的开括号的闭括号。

有效的括号字符串示例演示

现在让我们举三个例子，按照上述步骤进行演示。

📑 如果你已经掌握了这个方法的工作原理，可以跳过下一节。

#1。首先让test_str = "{()"。

• {是第一个字符，它是一个开括号，所以将其推入堆栈。
• 下一个字符(也是一个开括号，所以继续将其推入堆栈。
• 字符串中的第三个字符)是一个闭括号，所以你必须弹出堆栈的顶部，返回(。
• 此时，你已经到达字符串的末尾。但是堆栈仍然包含未关闭的开括号{。因此，给定的括号字符串test_str是无效的。

#2。在第二个例子中，让test_str = "()]"

• 第一个字符(是一个开括号；将其推入堆栈。
• 第二个字符)是一个闭括号；弹出堆栈的顶部，这恰好是）—一个相同类型的开括号。继续下一个字符。
• 第三个字符]是一个闭方括号，你应该再次弹出堆栈的顶部。然而，正如你所看到的，堆栈是空的——这意味着没有匹配的开括号[。因此，这个字符串是无效的。

#3。在最后一个例子中，test_str = "{()}"。

• 前两个字符{(是开括号，所以将它们推入堆栈。
• 第三个字符是一个闭圆括号)，所以弹出堆栈的顶部——(。
• 接下来的字符}是一个闭花括号，当你弹出堆栈的顶部时，你得到{——一个开花括号。
• 在遍历整个字符串之后，堆栈是空的，而且test_str是有效的！ ✅

📌我制作了以下流程图，概述了有效括号检查问题中的步骤。你可以保存它以供快速参考！

在下一节中，让我们看看如何将我们的概念转化为Python代码。

Python程序检查有效的括号

在Python中，你可以使用列表来模拟堆栈。

你可以使用.append()方法将元素添加到列表的末尾。这类似于将元素推入堆栈的顶部。

.pop()方法从列表中返回最后一个元素，这类似于从堆栈中弹出顶部元素——删除最后添加的元素。

所以现在你知道如何在Python列表上实现推入和弹出操作，模拟堆栈。

作为下一步，让我们回答一个问题：如何区分开括号和闭括号？

好吧，你可以使用一个Python字典——以开括号'{', '[', '('作为字典的键，相应的闭括号'}', ']', ')'作为值。你可以使用.keys()方法访问字典中的各个键。

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

理解函数定义

阅读下面的包含函数定义的代码单元格。你可以看到我们将流程图中的步骤与上面的解释结合在一起使用。

此外，我们还添加了一个docstring，其中包括：

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

▶ 你可以使用help(is_valid)或is_valid.__doc__来获取文档字符串。

def isValid(test_str):
  '''检查给定的括号字符串是否有效。

  参数：
    test_str（str）：要验证的括号字符串
  
  返回值：
    如果test_str有效，则返回True；否则返回False
  '''
  # len(test_str)是奇数 -> 无效！
  if len(test_str)%2 != 0:
    return False
  # 初始化括号字典
  par_dict = {'(':')','{':'}','[':']'}
  stack = []
  for char in test_str:
    # 将开括号推入堆栈
    if char in par_dict.keys():
      stack.append(char)
    else:
      # 没有匹配的开括号的闭括号
      if stack == []:
          return False
      # 如果是闭括号 -> 弹出堆栈顶部
      open_brac = stack.pop()
      # 不匹配的括号 -> 无效！
      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 == []检查stack是否为空。如果是，则test_str有效，函数返回True。否则，函数返回False。

现在，让我们进行几次函数调用，以验证我们的函数是否正确工作。

str1 = '{}[]'
isValid(str1)
# 输出：True

str2 = '{((}'
isValid(str2)
# 输出：False

str3 = '[{()}]'
isValid(str3)
# 输出：True

str4 = '[{)}]'
isValid(str4)
# 输出：False

str5 = '[[]}'
isValid(str5)
# 输出：False

从上面的代码片段中，我们可以得出结论，该函数的工作正常！

结论

以下是你学到的内容的简要总结。

• 首先，你了解了有效括号检查的问题。
• 接下来，你学习了使用堆栈作为数据结构的解决方法。
• 然后，你学会了使用Python字典验证括号组合：将开括号作为键，相应的闭括号作为值。
• 最后，你定义了Python函数以检查给定的括号字符串是否有效。

作为下一步，尝试在Geekflare’s online Python editor上编写该问题的代码。如果需要帮助，随时回顾本指南！

查看更多Python tutorials。祝你编程愉快！