确定括号是否平衡的算法

发布日期： 2024-09-25 阅读量： 作者： 网络

确定括号是否平衡的算法

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

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

第一步是查看问题：

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

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

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

上一篇: linux中at和crontab有什么区别

下一篇: linux文件夹复制怎么实现目录结构不变

确定括号是否平衡的算法

随便看看