【蓝桥杯】43694.正则问题

题目描述

  考虑一种简单的正则表达式：

  只由 x ( ) | 组成的正则表达式。

  小明想求出这个正则表达式能接受的最长字符串的长度。

  例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是 6。

输入描述

  一个由 x()| 组成的正则表达式。输入长度不超过 100，保证合法。

输出描述

  这个正则表达式能接受的最长字符串的长度。

输入输出样例

示例

输入

((xx|xxx)x|(x|xx))xx

输出

6

题目解析

((xx|xxx)x|(x|xx))xx 该表达式为什么最大可接受的字符串长度是6？

先明白算法规则：
  “|” 代表的是分支，比如 “xx|xxx” 就代表字符串有两种可能性，一种是xx，另外一种是xxx，所以，我们需要判断哪个分支能接受更多的字符串，在每个分支中，每遇到一个"x"，可接受的字符串长度就+1；
  “()”代表的是优先级，也就是深度，每当遇到“(”，我们都需要进行递归调用进入下一层，当遇到“)”，则结束调用返回上一层。

((xx|xxx)x|(x|xx))xx 这个表达式用一个类似于二叉树的结构表示是这样的：

  通过上图明显可以看出，(xx|xxx)x 这一段，最大可接受的字符串长度为4，(x|xx)这一段，最大可接受的字符串长度为2，(xx|xxx)x 和 (x|xx) 处在同一层，用“|” 分开，所以 ((xx|xxx)x|(x|xx)) 取得这两个分支中的最大可接受的字符串长度为4，然后原字符串后面还有两个 “xx”，相加之后，该正则表达式的最大可接受的字符串长度就是 4 + 2 = 6 个。

程序步骤

  这个算法通过深度优先搜索的方式，遍历整个正则表达式，对于每个 ( 会进入新的递归调用，对于 | 会进行分支处理，对于 x 会增加当前长度，对于 ) 会更新结果并返回，最终得到能接受的最长字符串的长度。

1. 首先，程序从输入中读取一个由 x、(、)、| 组成的正则表达式，并存储在变量 s 中。
2. 初始化两个变量 pos 和 length，分别表示当前处理的位置和输入字符串的长度。
3. 定义一个名为 dfs 的深度优先搜索函数：
     函数内部使用 ans 存储最终的最大长度，temp 存储当前正在处理的长度。
     进入 while 循环，只要 pos 小于 length，就会不断进行以下操作：
       当遇到 ( 时，将 pos 加一，然后递归调用 dfs 函数，并将其结果累加到 temp 中。
       当遇到 x 时，将 pos 加一，同时 temp 加一，表示找到了一个 x，长度加一。
       当遇到 | 时，将 pos 加一，更新 ans 为 ans 和 temp 中的最大值，将 temp 重置为 0，意味着开始新的分支处理。
       当遇到 ) 时，将 pos 加一，更新 ans 为 ans 和 temp 中的最大值，将 temp 重置为 0，同时返回 ans。
     循环结束后，处理类似 xx|xxxxx 这样的情况，更新 ans 为 ans 和 temp 中的最大值。
4. 调用 dfs 函数，并将结果存储在 x 中。
5. 打印出最终结果。

代码实现

感谢 @李时城 同学提供的代码，这是添加注释之后的版本。

import os
import sys# 读取输入的正则表达式
s = input()
# 初始化位置和长度
pos, length = 0, len(s)def dfs():# 声明使用全局变量 pos 和 lengthglobal pos, length# 存储最终结果和临时结果ans, temp = 0, 0while pos < length:# 遇到左括号，位置加一，递归调用 dfs 函数，并将结果累加到 temp 中if s[pos] == '(':pos += 1temp += dfs()# 遇到 'x'，位置加一，temp 加一elif s[pos] == 'x':pos += 1temp += 1# 遇到 '|'，位置加一，更新 ans 为 ans 和 temp 中的最大值，重置 tempelif s[pos] == '|':pos += 1ans = max(ans, temp)temp = 0# 遇到右括号，位置加一，更新 ans 为 ans 和 temp 中的最大值，返回 anselif s[pos] == ')':pos += 1ans = max(temp, ans)# temp = 0return ans# 处理类似 xx|xxxxx 的情况ans = max(ans, temp)return ans# 调用 dfs 函数
x = dfs()
print(x)