使用Python查找平衡括号字符串的最小插入次数

背景和问题

在编程中，经常需要处理括号序列。例如，判断一个括号序列是否“平衡”，即左右括号匹配且左右括号数量相同。

例如，以下括号序列都是平衡的：

()
(())
({[]})

而以下括号序列不平衡：

((()
)()
{[}]

对于不平衡括号序列，可以通过在其中插入一些括号使其变为平衡。例如，对于括号序列 (()，可以插入一个右括号 )，变为平衡序列 ()。对于括号序列 ())，则需要插入两个左右括号，变为平衡序列 ()()。

给定一个不平衡的括号序列，如何计算最少需要插入几个括号才能使其变为平衡的？

方法：栈

对于括号序列问题，栈可能是最自然的数据结构选取。一个基本的思路是：从左到右扫描括号序列，在扫描过程中通过栈来维护左右括号的匹配关系。

具体来说，遍历括号序列，对于每个括号，有以下两种情况：

• 如果是一个左括号，将其压入栈中。
• 如果是一个右括号，尝试从栈中弹出一个左括号。若弹出失败（即栈为空），则需要插入一个左括号来匹配当前右括号。若弹出成功，则当前括号已经匹配成功，继续扫描下一个括号。

下面是实现这个过程的Python代码：

def min_insertions(s: str) -> int:
    stack = []  # 用列表模拟栈
    count = 0   # 记录需要插入的括号数量

    for c in s:
        if c == '(':
            stack.append(c)
        elif c == ')':
            if not stack:   # 栈为空，需要插入左括号
                count += 1
            else:           # 匹配成功，弹出左括号
                stack.pop()

    count += len(stack)  # 如果栈中还有左括号，需要插入右括号使其匹配

    return count

这里用Python中的列表来模拟栈。代码中的 if not stack 语句相当于判断栈是否为空，如果为空则为真。

示例

以下是测试代码：

assert min_insertions("(()") == 1
assert min_insertions("))()(") == 3
assert min_insertions("(((((())") == 4
assert min_insertions(")))))))") == 6

结论

本文介绍了一种使用栈来处理不平衡括号序列的方法，并给出了Python代码实现。这种方法的时间复杂度为 O(n)，其中 n 是括号序列的长度。这种方法简单有效，适用于绝大多数情况。