如何在 Python 中检查有效括号

0 Shares

Python 中验证有效括号的指南

本教程将深入探讨如何在 Python 编程语言中验证字符串中的括号是否有效。这是一个常见的编程面试题，旨在考察您对数据结构和算法的理解。在接下来的内容中，您将掌握解决此类问题的技巧，并能编写出可靠的 Python 函数来执行验证操作。

什么是有效括号问题？

我们首先要明确什么是有效括号问题。简单来说，给定一个包含括号字符（包括小括号()、花括号{}和方括号[]）的字符串，我们需要判断这些括号的组合是否符合规则。

一个有效的括号字符串必须满足以下两个关键条件：

每一个左括号都必须与一个相同类型的右括号相匹配。
括号的闭合顺序必须正确。

下面给出一些示例，以说明有效和无效的括号字符串：

字符串	是否有效	原因
`"{}]"`	无效	右方括号 ‘]’ 没有对应的左方括号开启
`"[{}]"`	有效	所有括号都正确配对且顺序正确
`"[]"`	有效	所有括号都正确配对且顺序正确
`"[]{}"`	有效	所有括号都正确配对且顺序正确
`"[{]}"`	无效	方括号和花括号的闭合顺序错误

在解决这个问题时，我们会发现堆栈这种数据结构起着至关重要的作用。接下来，我们简要回顾一下堆栈的基本概念。

堆栈数据结构回顾

堆栈是一种后进先出（LIFO）的数据结构。就像一叠盘子，最后放入的盘子总是最先被取走。元素只能添加到堆栈的顶部，并且也只能从顶部移除。添加元素的操作称为“压入”（push），移除元素的操作称为“弹出”（pop）。

我们将使用以下两条规则来处理括号字符串：

遍历字符串时，遇到左括号时，将其压入堆栈。
遇到右括号时，从堆栈顶部弹出一个元素。

接下来，我们将详细介绍如何使用这些规则来解决有效括号检查的问题。

如何检查有效括号

结合上述观察，我们得出以下步骤：

字符串长度的初步检查

由于每个左括号都需要一个对应的右括号，因此有效的字符串必须包含偶数个字符。如果字符串长度为奇数，则可以立即判断其为无效的括号组合。

例如：

字符串	长度	是否有效
`"{}]"`	3	无效（长度为奇数，且 ‘]’ 前无 ‘[’）
`"[(]"`	3	无效（长度为奇数，且 ‘(’ 没有对应的 ‘)’）
`"{())}"`	5	无效（长度为奇数，且有多余的 ‘)’）

字符串长度为偶数的情况

如果字符串的长度为偶数，则需要进行更详细的检查：

从左到右遍历字符串，将当前字符记为char。
如果 char 是左括号（即 ‘(‘, ‘{‘, 或 ‘[‘），则将其压入堆栈，并继续处理下一个字符。
检查下一个字符 char 是左括号还是右括号。

如果是左括号，则将其压入堆栈。
如果遇到右括号，则从堆栈顶部弹出一个元素，并进行下一步检查。

根据从堆栈弹出的元素值，分为以下三种情况：

如果弹出的元素是相同类型的左括号，则返回步骤3，继续处理下一个字符。
如果弹出的元素是不同类型的左括号，则字符串为无效的括号组合。
如果堆栈为空，则字符串也是无效的，因为遇到了一个没有对应左括号的右括号。

有效括号字符串示例

接下来，我们通过三个示例来演示以上步骤。

如果你已经理解了工作原理，可以直接跳到下一部分。

示例 1： test_str = "{()"

‘{’ 是第一个字符，它是左括号，因此将其压入堆栈。
下一个字符 ‘(’ 也是左括号，同样压入堆栈。
第三个字符 ‘)’ 是右括号，从堆栈顶部弹出一个元素，得到 ‘(’。
此时字符串已遍历完毕，但堆栈中仍然有 ‘{’，没有被闭合，所以 test_str 是无效的。

示例 2： test_str = "()]"

第一个字符 ‘(’ 是左括号，将其压入堆栈。
第二个字符 ‘)’ 是右括号，从堆栈顶部弹出一个元素，得到 ‘(’，匹配成功。
第三个字符 ‘]’ 是右方括号，再次从堆栈弹出，但是堆栈为空，这意味着没有匹配的左括号，所以字符串是无效的。

示例 3：test_str = "{()}"

前两个字符 ‘{’ 和 ‘(’ 均为左括号，依次压入堆栈。
第三个字符 ‘)’ 是右括号，从堆栈顶部弹出 ‘(’。
下一个字符 ‘}’ 是右花括号，从堆栈顶部弹出 ‘{’，匹配成功。
遍历完整个字符串后，堆栈为空，所以 test_str 是有效的。✅

📌 下图是有效括号检查问题的流程图，可以保存下来以供参考：

接下来，我们将把上述概念转化为 Python 代码。

Python 程序检查有效括号

在 Python 中，我们可以使用列表来模拟堆栈的行为。可以使用 .append() 方法将元素添加到列表的末尾，这相当于向堆栈顶部压入元素；而 .pop() 方法则会移除并返回列表的最后一个元素，这相当于从堆栈顶部弹出元素。

现在我们知道如何在 Python 列表中实现压入和弹出的操作，接下来要解决的问题是如何区分左括号和右括号？可以使用 Python 字典。将左括号 ‘{‘, ‘[‘, ‘(‘ 作为字典的键，对应的右括号 ‘}’, ‘]’, ‘)’ 作为值。可以使用 .keys() 方法访问字典中的键。

现在我们把所学知识综合起来，开始编写 is_valid() 函数的定义。

理解函数定义

请仔细阅读下面的代码，它包含了 is_valid() 函数的定义。其中，我们将流程图中的步骤与上述说明相结合。此外，我们还添加了文档字符串，其中包含：

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

▶ 你可以使用 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，即需要验证的括号字符串。如果字符串有效，则返回 True，否则返回 False。
stack 是一个 Python 列表，用于模拟堆栈的行为。
par_dict 是一个 Python 字典，其中左括号作为键，右括号作为值。
在遍历字符串的过程中，如果遇到任何使括号字符串无效的情况，函数会立即返回 False 并退出。
遍历字符串中的所有字符后，通过 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 函数来检查给定的括号字符串是否有效。

接下来，可以尝试在在线 Python 编辑器上编写本教程中涉及的代码。如果需要帮助，可以随时重新浏览本文的内容！

请查看更多 Python 教程。编码愉快！🎉