确定括号是否平衡的算法

百变鹏仔 4天前 #Python

文章标签括号

我开始发布一系列算法来帮助我们，我学习代码、英语并强化这一点。我希望能够帮助您并为社区做出贡献。

这个算法很容易理解，因为你的问题很简单，但它是一个很好的例子，让我们看看如何通过简单的步骤获得解决方案。

第一步是查看问题：

“我们将利用上一课中定义的堆栈数据结构来确定一组括号是否平衡。

让我们首先了解一组平衡的括号是什么样的。

一组平衡的括号是指左括号和右括号的数量和类型匹配，并且也正确嵌套在括号串内。” (educative.io)

平衡括号示例
{ }
{ } { }
( ( { [ ] } ) )
不平衡括号示例
( ( )
{ { { ) } ]
[ ] [ ] ]

解决这个问题你的第一个想法是什么？

解决此类问题的第二步是用笔在纸上（我喜欢使用简单的图表）我们可能使用的每个变量以及我们拥有的所有数据（这类似于解决物理问题）。

显示这个新示例“}]”

数组 = ["}", "]"]

我们需要比较字符，看例子，很明显可以用数组来比较？

def is_match(p1, p2):    if p1 == "(" and p2 == ")":        return true    elif p1 == "{" and p2 == "}":        return true    elif p1 == "[" and p2 == "]":        return true    else:        return falsedef is_paren_balanced(paren_string):    s = stack()    is_balanced = true    index = 0    while index < len(paren_string) and is_balanced:        paren = paren_string[index]        if paren in "([{":            s.push(paren)        else:            if s.is_empty():                is_balanced = false                break            else:                top = s.pop()                if not is_match(top, paren):                    is_balanced = false                    break        index += 1    if s.is_empty() and is_balanced:        return true    else:        return false

我们声明是否平衡的步骤是验证数组的数量（在 % 2 != 0 中不起作用），并发现数组中是否存在用于输入的左括号，并使用 is_match 查找右括号。
当循环结束时，声明平衡或不平衡。

就是这样！

obs：我们需要使用栈数据结构。这个方法相信你都知道。

class Stack():    def __init__(self):        self.items = []    def push(self, item):        self.items.append(item)                 def pop(self):        return self.items.pop()    def is_empty(self):        return self.items == []    def peek(self):        if not self.is_empty():            return self.items[-1]    def get_stack(self):        return self.items

@vinycxuz

文章推荐

确定括号是否平衡的算法

如何使用Python实现决策树算法？

使用 Python 查找元组列表中的最小值和最大值

如何用Python编写普里姆算法？

Excel 将其提升到新的水平：最新更新中的无缝 Python 集成

在Python中的推荐系统