1. 从一道竞赛题看正则表达式与搜索算法的交汇

第一次看到“正则问题”这个题目名，很多人会以为要手写一个正则表达式引擎，或者调用语言内置的 regex 库去匹配字符串。实际上这道题的核心根本不是正则匹配，而是用深度优先搜索去解析一个带有嵌套结构的表达式，并求出它能匹配的最长字符串长度。换句话说，它考的是“把嵌套的括号结构翻译成一棵搜索树，然后在树上做最优决策”的能力。

这道题在蓝桥杯历届试题里属于比较经典的一类：题目给出一段只包含x、|、(、)四种字符的“正则表达式”，其中x表示一个字符，|表示或运算，括号表示分组。要求你求出这个表达式所能表示的字符串集合中，最长字符串的长度。比如xx|xxx的最长匹配长度是 3，(xx|xxx)x的最长匹配长度是 4，((xx|xxx)x|(x|xx))xx的最长匹配长度是 6。

它适合谁来参考？如果你正在准备蓝桥杯、ACM 类算法竞赛，或者想系统理解 DFS 在“表达式解析”类问题中的落地方式，这道题是一个非常好的练手素材。它不需要复杂的动态规划状态设计，也不需要图论建模，核心就是递归下降 + 分情况取最优。但恰恰因为结构简单，它能把 DFS 的几个关键细节——递归边界、状态传递、分支合并——暴露得非常清楚。

我当年第一次做这道题时，卡在了“或运算怎么在递归里合并结果”这个点上，后来才想明白：整个表达式本质上是一棵以|为分支节点、以x为叶子、以括号为子树的树，DFS 的任务就是自底向上地计算每个子树能贡献的最大长度。下面我把这道题从思路到实现完整拆一遍，包括我踩过的坑和实测有效的调试方法。

2. 题目结构拆解与核心思路选型

2.1 表达式语法规则到底在说什么

先把题目给出的语法用最朴素的话翻译一遍。表达式由四种符号组成：

• x：代表一个普通字符，贡献长度 1。
• |：代表“或”，左右两边任选其一，最终长度取两边中较大的那个。
• (和)：代表分组，括号内部的整体作为一个单元参与外层运算。
• 表达式可以嵌套，也可以连续拼接，比如xx表示两个字符依次出现，长度累加。

这里有一个容易被忽略的点：拼接是隐式的。题目里没有专门的连接符号，两个相邻的单元放在一起就表示它们要连起来。比如(xx)x表示先匹配xx再匹配x，总长度是 3。这一点和很多正则引擎的写法一致，但在代码里需要特别处理，因为你在扫描字符串时，遇到x或(就意味着一新单元的开始，而不是等待某个分隔符。

理解了语法，就能明白这道题要求的东西：给定一个表达式，求它所有可能匹配结果中长度最大的那个值。注意是“最大长度”，不是“匹配某个具体字符串”，所以不需要真的生成字符串，只需要在解析过程中维护长度信息即可。

2.2 为什么选 DFS 而不是栈或动态规划

这类嵌套结构的问题，常见解法有三种：显式栈模拟、递归下降、动态规划区间 DP。我选 DFS 递归下降，理由有三条。

第一，结构天然递归。括号的嵌套和|的分支，本质上就是一棵树的递归定义。用递归函数去处理，代码结构和问题结构是一一对应的，可读性最高。你写一个dfs()函数，它的职责就是“从当前位置开始解析一个完整单元，返回它能贡献的最大长度”，然后遇到括号就递归调用自己，遇到|就分别求两边取最大。

第二，栈模拟容易出错。如果用显式栈，你需要手动维护当前层的最大值、当前累计值、遇到|时怎么回退、遇到)时怎么合并到上一层。这些状态在栈里交错，调试时非常痛苦。我试过用栈写一版，结果在((xx|xxx)x|(x|xx))xx这种多层嵌套上卡了很久，最后还是换回递归。

第三，区间 DP 属于杀鸡用牛刀。区间 DP 需要枚举分割点，时间复杂度 O(n³)，而这道题 n 最多几百，虽然也能过，但代码量和思维负担都更大。DFS 递归下降是 O(n) 的，每个字符只被访问一次，效率更高，写起来也更直接。

提示：递归下降的核心假设是“表达式合法且括号匹配”。这道题题目保证输入合法，所以不需要做错误处理。如果是在实际工程里解析用户输入，必须加上括号匹配检查和非法字符过滤。

2.3 递归函数的设计契约

在动手写代码之前，先把递归函数的“契约”定清楚，这是整个解法最关键的一步。我定义的函数签名是：

def dfs(s, i): # 从下标 i 开始解析一个单元，返回 (最大长度, 下一个待处理位置)

为什么返回两个值？因为解析完一个单元后，你不知道后面还有没有内容，需要把“解析到哪了”这个信息传回给调用方。比如解析(xx)x时，内层递归处理完xx遇到)返回，外层需要知道)后面还有一个x要继续处理。

函数内部的逻辑分三层：

• 当前层累计值cur：记录当前分支下已经拼接的长度。
• 当前层最大值best：记录遇到|时，之前所有分支里的最大长度。
• 循环扫描：遇到x让cur加一，遇到|把cur归入best并重置cur，遇到(递归求子单元长度并累加到cur，遇到)或字符串结束就收尾返回。

这个契约一旦定好，代码就是水到渠成的事。下面我把完整实现和每一步的意图拆开讲。

3. 递归下降的完整实现与逐行拆解

3.1 核心代码框架

先给出完整可运行的 Python 版本，然后逐段解释。

import sys def dfs(s, i): cur = 0 # 当前分支累计长度 best = 0 # 当前层历史最大长度 while i < len(s): ch = s[i] if ch == 'x': cur += 1 i += 1 elif ch == '|': # 遇到或运算，把当前分支结算进 best，重新开始累计 best = max(best, cur) cur = 0 i += 1 elif ch == '(': # 递归解析括号内部，返回子单元长度和新的位置 sub_len, i = dfs(s, i + 1) cur += sub_len elif ch == ')': # 当前层结束，结算并返回 best = max(best, cur) return best, i + 1 # 字符串扫描完毕，结算最后一分支 best = max(best, cur) return best, i def solve(): s = sys.stdin.readline().strip() ans, _ = dfs(s, 0) print(ans) if __name__ == "__main__": solve()

这段代码不到 40 行，但每一行都对应一个明确的语义。下面拆开说。

3.2 遇到 x 为什么直接加一

x是叶子节点，它不产生分支，只贡献长度 1。所以在当前分支的累计值cur上加一即可。这里不需要做任何判断，因为题目保证x就是单个字符。

但有一个细节值得注意：连续多个 x 是累加关系。比如xxx的cur会依次变成 1、2、3，最后best取 3。这符合“拼接”的语义。

3.3 遇到 | 时的结算与重置

|是这道题的分支点。它的语义是“左边和右边任选其一”，所以当前分支到此为止，需要把cur结算进best，然后重置cur为 0，开始统计右边分支。

这里有一个容易写错的地方：结算时用的是max(best, cur)，而不是直接赋值。因为一个单元里可能有多个|，比如x|xx|xxx，你需要取所有分支的最大值。我第一次写的时候用了best = cur，结果只能拿到最后一个分支的长度，调试了半天才发现。

另外，|后面的分支可能不是简单字符，而是括号或更复杂的结构，所以重置cur后继续循环即可，后续遇到(会递归处理，遇到x会继续累加。

3.4 括号递归的进入与返回

遇到(时，调用dfs(s, i + 1)，意思是“从括号内部的下一个字符开始，解析一个完整单元”。子递归会在遇到匹配的)时返回，返回值有两个：子单元的最大长度，以及)之后的下一个位置。

外层拿到子单元长度后，直接累加到cur上。这体现了括号的语义：括号内部整体作为一个单元参与外层拼接。比如(xx|xxx)x，子递归返回 3，外层cur变成 3，然后继续处理后面的x，最终cur变成 4。

这里的关键是位置传递。子递归返回的i已经跳过了)，外层循环直接从新位置继续，不会重复处理括号内的字符。

3.5 遇到 ) 或字符串结束的收尾

遇到)时，说明当前层解析完毕。需要做两件事：把当前cur结算进best，然后返回(best, i + 1)，其中i + 1是跳过)后的位置。

如果循环自然结束（i到达字符串末尾），说明没有遇到)，但当前层也要收尾，同样结算best并返回(best, i)。

这两种收尾逻辑本质相同，只是返回的位置不同。我在代码里把它们分开写，是为了让)的处理更直观。你也可以合并成一个收尾函数，但分开写调试时更容易定位问题。

3.6 手动模拟一遍执行过程

拿(xx|xxx)x这个例子，手动走一遍递归栈，能帮你彻底理解状态流转。

第一层dfs(s, 0)，s[0]是(，进入子递归dfs(s, 1)。

子递归从i=1开始，s[1]='x'，cur=1；s[2]='x'，cur=2；s[3]='|'，best=max(0,2)=2，cur=0；s[4]='x'，cur=1；s[5]='x'，cur=2；s[6]='x'，cur=3；s[7]=')'，best=max(2,3)=3，返回(3, 8)。

外层拿到sub_len=3，cur=3，i=8。s[8]='x'，cur=4，i=9。循环结束，best=max(0,4)=4，返回(4, 9)。最终答案 4。

这个过程里，best在子递归里经历了 0→2→3 的变化，最终取 3；外层cur从 0→3→4，最终取 4。每一步都对应一个明确的语义，没有多余的状态。

4. 实操中的关键细节与避坑经验

4.1 输入读取的坑：换行与空格

这道题输入只有一行字符串，但实际比赛中输入可能带有首尾空格或多余换行。我用sys.stdin.readline().strip()读取，strip()会去掉首尾空白，但不会影响中间的字符。注意不要用input()，因为input()在某些环境下会把\r也读进来，导致字符串末尾多一个不可见字符，循环时多走一轮。

如果你用 C++ 写，建议用getline(cin, s)而不是cin >> s，因为cin >> s遇到空格会截断，虽然这道题输入没有空格，但养成习惯更稳妥。

4.2 递归深度与栈溢出

题目中括号嵌套层数最多可能达到几百层。Python 默认递归深度是 1000，一般够用，但如果嵌套特别深，可能触发RecursionError。保险起见，可以在开头加：

sys.setrecursionlimit(10000)

C++ 的栈空间通常更大，但极端情况下也可能溢出。如果不想用递归，可以改写成显式栈，但代码复杂度会上升不少。我的建议是：竞赛环境下优先用递归，加一行提高递归深度即可。

4.3 或运算的优先级问题

这道题的语法里，|的优先级低于拼接，但高于括号的“分组”语义。换句话说，xx|xxx应该理解为(xx)|(xxx)，而不是x(x|x)xx。我的递归实现天然满足这个优先级，因为|在循环里遇到就结算当前cur，而拼接是隐式累加，括号是递归处理。

但如果你用其他方式实现，比如先做词法分析再做语法分析，就需要显式定义优先级。这也是我推荐递归下降的原因之一：优先级直接体现在代码结构里，不需要额外维护优先级表。

4.4 空表达式与边界情况

题目保证输入合法，但实际写代码时最好考虑一下边界。比如输入只有一个x，答案是 1；输入是()，理论上不合法，但如果不小心遇到，我的代码会返回 0。再比如输入是x|，末尾的|后面没有内容，我的代码会在循环结束后结算best，结果是 1，也算合理。

这些边界情况在竞赛里通常不会出现，但如果你想把代码改成通用解析器，就需要加上合法性检查。我的建议是：竞赛代码以过题为目标，不要过度设计；工程代码才需要考虑健壮性。

4.5 调试技巧：打印递归树

递归代码最难的地方是“看不见执行过程”。我调试时会在dfs入口和出口加打印：

def dfs(s, i): print(f"enter dfs at {i}, char={s[i] if i < len(s) else 'END'}") # ... 原有逻辑 ... print(f"exit dfs at {i}, return {best}") return best, i

这样能看到递归的进入和返回顺序，配合手动模拟，很快就能定位问题。实测下来，这道题最常见的 bug 是|结算时忘了取max，或者括号返回后位置没有跳过)，打印一下就能发现。

5. 常见问题排查与扩展思考

5.1 常见问题速查表

5.2 如果题目改成求最短长度怎么办

把max全部换成min就行，但要注意初始值。best初始应该设为一个很大的数，cur初始为 0。遇到|时best = min(best, cur)，收尾时同样取最小。这个改动很小，但能帮你理解“或运算”在最大和最小语义下的对称性。

5.3 如果题目改成输出具体字符串怎么办

那就不能只维护长度了，需要在每个节点记录“当前最优字符串”。递归返回时，把子串拼接起来。这会增加内存开销，但思路不变。实际比赛中很少这么考，因为输出字符串的判定比较麻烦。

5.4 如果表达式里加入*和+怎么办

*表示重复零次或多次，+表示重复一次或多次。这时候问题就复杂了，因为重复次数会影响长度，需要引入动态规划或贪心策略。对于*，如果内部单元能贡献正长度，就无限重复取最大；如果贡献 0，就取 0。对于+，至少重复一次。这类扩展在竞赛里属于进阶题，核心还是递归下降，但状态设计要更细致。

5.5 这道题对实际工作的启发

虽然这是一道竞赛题，但它背后的“递归下降解析”思想在实际工作里非常有用。比如解析配置文件、处理嵌套的 JSON 结构、实现简单的模板引擎，都会用到类似的思路。我后来在一个日志分析工具里，就用几乎相同的递归结构去解析带括号的过滤表达式，代码量很少，但可读性和扩展性都很好。

注意：实际工程里的表达式解析通常需要处理错误输入、支持更多运算符、考虑性能优化。竞赛题的解法是一个很好的起点，但不要直接照搬到生产环境。

6. 我个人在这道题上的调试体会

这道题我前前后后写了三版。第一版用栈模拟，卡在多层嵌套的合并逻辑上，写了 80 多行还是过不了。第二版改用递归，但|结算时用了赋值，导致x|xx|xxx只能拿到最后一个分支的长度。第三版才把max和位置传递这两个点理顺，最终 30 多行搞定。

我的体会是：递归下降的关键不在于代码多复杂，而在于把函数契约定清楚。只要明确“函数从哪开始、返回什么、位置怎么传递”，剩下的就是按语法规则填逻辑。另外，手动模拟一遍执行过程比盯着代码看半小时都管用，尤其是括号嵌套和|分支交错的时候，画个简单的递归树，状态流转一目了然。

最后分享一个小技巧：如果你在比赛里遇到类似的嵌套结构题，先别急着写代码，拿纸笔把输入串的递归树画出来，标出每个节点的返回值和位置。树画清楚了，代码就是翻译工作。这个方法我在好几道 DFS 题上都用过，实测很稳。