Python 中的括号平衡 | Python 中的平衡括号问题

在本教程中，我们将学习如何在 Python 中检查给定括号的平衡。这是一个基本的面试问题，您被要求查找给定的字符串（括号）是否平衡。这是产品型公司中经常问到的技术面试问题。一个字符串可以包含不同类型的括号，例如 ()、[]、{}。

在计算机科学中，括号主要用于简化表达式。如果每个左括号都有一个右括号，则该括号被认为是平衡的。换句话说，括号应该成对出现；否则，它们是不平衡的。

让我们来理解有效的括号问题以及如何使用 Python 解决这个问题。

什么是平衡括号问题？

首先，我们以包含字符 **(、)、{、}、[ 和 ]** 的字符串作为输入，以检查给定字符串是否有效。

如果输入字符串遵循以下约束，则该字符串有效：

• 左括号必须有相应的右括号。
• 开括号必须按正确的顺序关闭。

让我们来理解解决这个问题的思路。

检查有效括号

我们可以使用以下方法解决这个问题。

方法一：使用暴力破解法

在暴力破解算法中，我们可以使用条件语句、递归和循环来匹配括号。如果括号平衡，则返回 true，否则返回 false。

让我们看下面的代码片段。

代码 -

输出

Is {[()]}} valid ? : False
Is {[()]}{]{}} valid ? : False

解释 -

在上面的代码中，我们使用了 while 循环来检查给定的序列。while 循环将执行，直到给定的字符串变空或没有元素为止。首先，我们检查是否出现 () 括号，然后替换为空字符串，接着检查 [] 括号并替换为空字符串，对其他括号执行相同的操作。如果没有出现一对括号，则返回 True，否则返回 False。

让我们尝试用不同的方法来解决这个问题。

方法二：使用 For 循环

在这个程序中，我们将使用 for 循环和计数器值来检查给定的括号字符串是否有效。

让我们来理解以下代码。

示例 -

输出

Enter a string of brackets: {[()]}
Given string is balanced : True
Enter a string of brackets: {[()]}]
Given string is balanced : False

解释 -

在上面的代码中，我们初始化了一个计数变量为零。在 if 条件中，如果给定的字符串中有开括号，则计数加一；如果对应的有闭括号，则计数减一。最后，我们检查计数是否等于零，然后返回 True，否则返回 False。

方法三：使用堆栈

堆栈是一种线性数据结构，以 LIFO（后进先出）的方式存储数据。我们遍历字符串并将开括号压入堆栈。我们持续进行此过程，直到所有开括号都压入堆栈，然后将指针向前移动。

当指针遇到闭括号时，检查堆栈的顶部，看它是否与开括号匹配。如果匹配，则从堆栈中弹出开括号，重复此过程直到指针访问完所有闭括号。

如果所有元素都从括号中弹出，则表示给定的字符串包含有效的括号，如果还有任何一个括号留在括号中，则给定的字符串不平衡。

示例 -

输出

The given string is balanced

时间复杂度

检查括号的时间复杂度是最佳的 O(n)。其中 n 是字符串中括号的总数。由于我们需要大小为 'n' 的堆栈来存储表达式的字符，因此在给定字符串中搜索括号的每次搜索都是线性的，空间复杂度为 0(n)。

结论

Python 中的括号主要不用于定义块，但在其他编程语言中起着至关重要的作用。在 Python 中，它们用于定义字典、元组、集合、列表和许多其他数据结构。面试官提出这个问题是为了测试候选人对解决问题的知识。在本教程中，我们讨论了检查给定字符串是否为有效括号的三种重要方法。我们还使用 Python 代码实现了解决方案。如果您正在为产品型公司寻找高薪工作，强烈建议您练习此类问题。