确定括号是否平衡的算法-Python教程-PHP中文网

确定括号是否平衡的算法

心靈之曲

发布： 2024-09-25 14:29:18

转载

442人浏览过

确定括号是否平衡的算法

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

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

第一步是查看问题：

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

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

一组平衡的括号是指左括号和右括号的数量和类型匹配，并且也正确嵌套在括号串内。” (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 false


def 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

以上就是确定括号是否平衡的算法的详细内容，更多请关注php中文网其它相关文章！