【蓝桥杯】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 会增加当前长度，对于 ) 会更新结果并返回，最终得到能接受的最长字符串的长度。

• 首先，步伐从输入中读取一个由 x、(、)、| 组成的正则表达式，并存储在变量 s 中。
  
• 初始化两个变量 pos 和 length，分别体现当前处理的位置和输入字符串的长度。
  
• 定义一个名为 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 中的最大值。
  
• 调用 dfs 函数，并将结果存储在 x 中。
  
• 打印出最闭幕果。
  

代码实现

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

1. import os
2. import sys
4. # 读取输入的正则表达式
5. s = input()
6. # 初始化位置和长度
7. pos, length = 0, len(s)
10. def dfs():
11.     # 声明使用全局变量 pos 和 length
12.     global pos, length
13.     # 存储最终结果和临时结果
14.     ans, temp = 0, 0
15.     while pos < length:
16.         # 遇到左括号，位置加一，递归调用 dfs 函数，并将结果累加到 temp 中
17.         if s[pos] == '(':
18.             pos += 1
19.             temp += dfs()
20.         # 遇到 'x'，位置加一，temp 加一
21.         elif s[pos] == 'x':
22.             pos += 1
23.             temp += 1
24.         # 遇到 '|'，位置加一，更新 ans 为 ans 和 temp 中的最大值，重置 temp
25.         elif s[pos] == '|':
26.             pos += 1
27.             ans = max(ans, temp)
28.             temp = 0
29.         # 遇到右括号，位置加一，更新 ans 为 ans 和 temp 中的最大值，返回 ans
30.         elif s[pos] == ')':
31.             pos += 1
32.             ans = max(temp, ans)
33.             # temp = 0
34.             return ans
35.     # 处理类似 xx|xxxxx 的情况
36.     ans = max(ans, temp)
37.     return ans
40. # 调用 dfs 函数
41. x = dfs()
42. print(x)

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。