当前位置：首页 > article >正文

最长正则括号序列算法详解

article 2024/12/25 14:09:39

一、引言

在计算机科学中，处理括号序列的问题是一个常见且有趣的领域。本文将深入探讨如何寻找最长正则括号序列这一问题，包括问题的详细描述、解决该问题的算法思路、代码实现以及通过示例对算法进行深入剖析。

二、问题详细描述

（一）正则括号序列的定义

一个括号序列被认定为正则的，当且仅当通过合理地插入 “+” 和 “×” 操作符能够形成一个正确的数学表达式。例如：

“(())()” 是正则的，因为可以写成类似 “( ( ) ) × ( )” 这样的数学表达式。
“()” 本身就是一个简单的正则括号序列。
“(((())))” 也是正则的，能够形成有效的数学表达式。
然而，像 “(”（左括号单独出现）、“())”（右括号多于左括号且不匹配）和 “((())(”（括号匹配不完整）这些都不是正则括号序列。

（二）输入与输出要求

输入
- 输入为一个非空字符串，该字符串仅由 “(” 和 “)” 字符组成，并且字符串长度不超过 10⁶。例如：“)((())())((()))” 或者 “))((” 等都是可能的输入形式。
输出
- 需要输出两个值：一是最长正则括号子序列的长度；二是这种最长正则括号子序列的数量。如果不存在正则括号子序列，则按照要求输出 “0 1”。

三、算法思路与实现

（一）核心算法函数`longest_regular_bracket_sequence`

数据结构初始化
- 首先，我们使用一个栈stack来辅助记录左括号的位置。栈在处理括号匹配问题中是非常有效的数据结构。
- 同时，创建一个列表dp，其长度与输入字符串s相同，并且初始化为 0。dp列表的作用是存储以每个字符位置结尾的最长正则括号子序列的长度。
- 代码如下：
```
stack = []
dp = [0] * len(s)
```
遍历字符串进行括号匹配与长度计算
- 然后，对输入字符串s进行逐字符遍历：
```
for i in range(len(s)):
```
- 当遇到左括号 “(” 时：
  - 将当前左括号的索引位置i压入栈stack中。因为这个左括号可能在后续会与右括号匹配，通过栈可以方便地找到对应的左括号。
  - 代码为：if s[i] == '(': stack.append(i)
- 当遇到右括号 “)” 时：
  - 首先要检查栈是否为空。如果栈为空，说明当前右括号没有与之匹配的左括号，这种情况下无法形成正则括号子序列（以当前位置结尾），所以不进行任何操作。
  - 如果栈不为空，说明找到了一对匹配的括号。此时，弹出栈顶元素，这个栈顶元素就是与当前右括号匹配的左括号的索引，记为matching_index。
  - 接着，计算以当前右括号结尾的最长正则括号子序列的长度。其计算公式为dp[i] = dp[matching_index - 1] + i - matching_index + 1。这里的dp[matching_index - 1]表示匹配左括号前一个位置的最长正则括号子序列长度，i - matching_index + 1是当前匹配括号对本身的长度。通过将这两部分相加，就得到了以当前右括号结尾的最长正则括号子序列长度。
  - 代码为：
```
elif s[i] == ')' and stack:
    matching_index = stack.pop()
    dp[i] = dp[matching_index - 1] + i - matching_index + 1
```
计算最终结果
- 在遍历完整个字符串后，我们需要从dp列表中找出最大值，这个最大值就是最长正则括号子序列的长度max_length，通过max(dp)即可获取。
- 接下来，计算最长长度出现的次数。如果max_length大于 0，那么通过dp.count(max_length)来统计；如果max_length等于 0，说明不存在正则括号子序列，按照要求数量为 1。
- 代码如下：
```
max_length = max(dp)
count = dp.count(max_length) if max_length > 0 else 1
return max_length, count
```

（二）输入读取、问题解决与输出部分

输入读取
- 使用input().strip()简单地读取输入的字符串s，这里的strip()方法用于去除字符串可能存在的首尾空白字符。
问题解决与输出
- 调用longest_regular_bracket_sequence函数，传入读取到的字符串s，得到最长正则括号子序列的长度length和数量count：
```
length, count = longest_regular_bracket_sequence(s)
```
- 最后，按照要求输出结果：
```
print(length, count)
```

四、示例深度剖析

（一）示例一

输入：)((())())((()))
- 当算法开始执行时：
  - 初始化stack为空栈，dp为长度与输入字符串相同的全 0 列表。
  - 开始遍历字符串：
    - 第一个字符是 “)”，此时栈为空，不进行操作，dp[0]保持为 0。
    - 第二个字符是 “(”，将索引 1 压入栈，stack = [1]。
    - 第三个字符是 “(”，将索引 2 压入栈，stack = [1, 2]。
    - 第四个字符是 “)”，栈不为空，弹出栈顶元素 2，计算dp[3] = dp[2 - 1] + 3 - 2 + 1 = 0 + 2 = 2（这里dp[1]为 0）。
    - 第五个字符是 “)”，栈不为空，弹出栈顶元素 1，计算dp[4] = dp[1 - 1] + 4 - 1 + 1 = 0 + 4 = 4（这里dp[0]为 0）。
    - 以此类推，继续遍历和计算。
- 最终计算得到dp列表的值（假设从 0 开始索引）：[0, 0, 0, 2, 4, 0, 4, 6, 0, 2, 4, 6]。
- 从dp中找到最大值max_length = 6，dp中值为 6 的元素有 2 个，所以count = 2。
- 输出为6 2。

（二）示例二

输入：))((
- 初始化stack和dp后开始遍历：
  - 第一个字符是 “)”，栈为空，不操作，dp[0]为 0。
  - 第二个字符是 “)”，栈为空，不操作，dp[1]为 0。
  - 第三个字符是 “(”，将索引 2 压入栈，stack = [2]。
  - 第四个字符是 “(”，将索引 3 压入栈，stack = [2, 3]。
- 最终dp列表的值为[0, 0, 0, 0]。
- 最大值max_length = 0，按照规则count = 1。
- 输出为0 1。