蓝桥杯正则问题：DFS递归解嵌套表达式求最长匹配-北京尧图网络

1. 从一道蓝桥杯真题说起正则表达式也能用DFS解第一次看到正则问题这道题的时候我下意识地以为是要写一个正则表达式解析器或者实现某种模式匹配算法。结果读完题才发现这其实是一道披着正则外衣的深度优先搜索题而且它的核心逻辑比想象中要简单得多——简单到你会怀疑自己是不是想复杂了。这道题在蓝桥杯历届试题里算是比较经典的一道DFS应用题。它的题目描述大致是这样的给定一个由字符x、|、(、)组成的字符串这个字符串表示一个正则表达式其中x表示一个字符|表示或运算()表示分组。要求你求出这个表达式能够匹配的字符串中最长的那个字符串的长度是多少。说白了就是让你在这个表达式所代表的所有可能字符串里找出长度最大的那个。比如xx|xxx能匹配xx或者xxx那答案就是3。再比如x(xx|xxx)x能匹配xxxx或者xxxxx答案就是5。这道题之所以值得拿出来单独讲是因为它完美地展示了DFS在表达式求值类问题中的通用套路遇到括号就递归遇到操作符就分治遇到基础元素就返回。掌握了这个套路你不仅能秒杀这道题还能把类似的嵌套结构问题一并解决。我当年第一次做这道题的时候卡在了怎么处理嵌套括号上写了一堆栈操作代码又长又容易出错。后来看了别人的思路才恍然大悟——原来递归才是这道题的最优解而且代码量少得惊人。这篇文章就把我踩过的坑、想通的逻辑、以及最终打磨出来的代码完整地分享给你。2. 题目到底在问什么把正则翻译成人话2.1 三种操作符的实际含义题目里虽然用了正则表达式这个词但它和我们平时用的正则引擎完全不是一回事。这里的规则被极度简化了只有三种操作x表示一个普通字符它匹配的字符串就是x长度为1。|表示或运算A|B表示可以匹配 A 或者 B取两者中较长的那个。()表示分组括号内的内容作为一个整体参与运算。没有*、、?这些量词没有字符集没有转义什么都没有。就是这么纯粹。所以这道题的本质是给你一个由这三种元素构成的表达式让你计算它所能表示的最长字符串的长度。2.2 几个例子帮你建立直觉光说规则可能还是有点抽象我们来看几个具体的例子表达式能匹配的字符串最长长度xx1xxxx2xxx或xxxxxxxx或xxxx(xxxxx)xxx或xxxx(xxxxx)xxxx或xxxx((xxxxx)xxx)x注意最后一个例子它展示了嵌套括号的情况。((xx|xxx)x|xx)x这个表达式最外层是一个括号后面跟着一个x括号里面是(xx|xxx)x|xx而这个括号里面又嵌套了一个(xx|xxx)。这种多层嵌套正是DFS要处理的核心场景。2.3 为什么不能用简单的字符串替换有些同学可能会想我能不能从左到右扫描遇到|就比较两边遇到括号就展开理论上可以但实际操作起来非常麻烦。因为括号可以无限嵌套而且|的优先级和括号的作用范围需要精确判断。你如果用迭代的方式写就需要维护一个栈来记录当前处理到哪一层代码会变得又长又容易出错。而DFS的天然递归结构恰好和括号的嵌套结构一一对应。每遇到一个左括号就递归进入下一层每遇到一个右括号就结束当前层返回结果。这种结构对应让代码变得极其简洁。3. 递归函数的返回值设计这道题最关键的一步3.1 为什么返回值不能只是长度很多人写DFS的时候第一反应是让函数返回当前表达式能匹配的最大长度。这个思路方向是对的但有一个致命问题当函数遇到|或者)的时候它需要知道当前这一段已经处理到哪里了。举个例子对于表达式xx|xxx如果你只返回长度那么处理完xx之后返回2然后遇到|你需要继续处理xxx但你怎么知道xxx从哪里开始你需要一个额外的变量来记录当前扫描位置。所以正确的做法是让递归函数同时返回两个信息——当前能匹配的最大长度以及处理结束后的位置。或者更常见的做法是用一个全局变量或引用参数来记录当前扫描位置函数只返回长度。3.2 两种常见的实现方式对比我见过两种主流的写法各有优劣方式一全局指针返回长度def dfs(): global pos max_len 0 current_len 0 while pos len(s): if s[pos] x: current_len 1 pos 1 elif s[pos] |: max_len max(max_len, current_len) current_len 0 pos 1 elif s[pos] (: pos 1 # 跳过左括号 current_len dfs() elif s[pos] ): pos 1 # 跳过右括号 break max_len max(max_len, current_len) return max_len这种写法的优点是代码简洁逻辑清晰。缺点是依赖全局变量如果在多线程环境下会有问题但在竞赛中完全够用。方式二传递位置参数返回元组def dfs(start): max_len 0 current_len 0 i start while i len(s): if s[i] x: current_len 1 i 1 elif s[i] |: max_len max(max_len, current_len) current_len 0 i 1 elif s[i] (: sub_len, i dfs(i 1) current_len sub_len elif s[i] ): max_len max(max_len, current_len) return max_len, i 1 max_len max(max_len, current_len) return max_len, i这种写法不依赖全局变量更加函数式但代码稍微冗长一些。3.3 我个人的选择和建议在竞赛场景下我强烈推荐第一种写法。原因很简单代码短不容易出错调试方便。全局变量在单线程竞赛程序里没有任何问题而且pos这个变量的语义非常明确——它就是当前扫描到的位置。不过有一点需要注意全局变量的初始化。每次调用dfs()之前一定要确保pos被重置为0。我见过有同学在多次测试用例之间忘记重置导致第二个用例从第一个用例结束的位置开始扫描结果全错。提示如果你用的是Python可以用nonlocal或者把pos放在一个列表里来避免global关键字但在竞赛中直接global就完事了没必要过度设计。4. 逐字符扫描的逻辑拆解四种情况分别怎么处理4.1 遇到x累加当前长度这是最简单的情况。每遇到一个x就说明当前这一段能匹配的字符串长度增加了1。所以直接current_len 1然后pos 1继续往后扫描。这里有一个容易忽略的点x是可以连续出现的。比如xxx表示三个连续的字符长度是3。所以你不能遇到x就返回而是要继续累加直到遇到|、)或者字符串结束。4.2 遇到|结算当前段重置计数器|是或运算的分隔符。当你遇到|的时候说明前面那一段已经处理完了你需要把current_len和max_len做一次比较取较大值存入max_len然后把current_len重置为0准备处理|后面的内容。为什么是重置为0而不是其他值因为|表示或者前后两段是独立的各自从0开始计算长度。比如xx|xxx处理完xx后current_len2遇到|后max_len2current_len重置为0然后处理xxx得到current_len3最后循环结束时再比较一次max_len3。4.3 遇到(递归进入下一层这是整个算法的核心。遇到左括号时说明接下来要处理一个子表达式而这个子表达式的处理逻辑和当前层完全一样。所以直接递归调用dfs()让子调用去处理括号内的内容返回子表达式的最大长度然后把这个长度累加到current_len上。注意在递归调用之前你需要先把pos加1跳过左括号本身。否则子调用会再次遇到左括号导致无限递归。4.4 遇到)结算并返回遇到右括号时说明当前层的子表达式处理完毕了。你需要做两件事第一把current_len和max_len做最后一次比较第二把pos加1跳过右括号然后返回max_len。这里有一个细节返回之前一定要做最后一次max比较。因为循环可能在遇到)时直接break如果不做这次比较最后一段的长度就会丢失。比如xx|xxx在括号内的情况处理完xxx后遇到)如果不比较就直接返回max_len还是2答案就错了。4.5 循环结束后的收尾当while循环因为pos到达字符串末尾而结束时同样需要做一次max比较。这和遇到)的情况类似都是为了防止最后一段的长度被遗漏。整个逻辑可以用下面这个表格来总结遇到字符操作注意事项xcurrent_len 1; pos 1连续x要累加|max_len max(max_len, current_len); current_len 0; pos 1重置计数器(pos 1; current_len dfs()先跳过左括号再递归)max_len max(max_len, current_len); pos 1; return max_len返回前必须比较结束max_len max(max_len, current_len); return max_len防止遗漏最后一段5. 完整代码实现与逐行注释5.1 Python版本import sys def solve(): s sys.stdin.readline().strip() pos 0 n len(s) def dfs(): nonlocal pos max_len 0 current_len 0 while pos n: if s[pos] x: current_len 1 pos 1 elif s[pos] |: max_len max(max_len, current_len) current_len 0 pos 1 elif s[pos] (: pos 1 # 跳过左括号 current_len dfs() elif s[pos] ): pos 1 # 跳过右括号 break max_len max(max_len, current_len) return max_len print(dfs()) if __name__ __main__: solve()这段代码里我用了nonlocal而不是global因为pos是在solve函数内部定义的用nonlocal更合适。如果你把pos定义在模块级别那就用global。5.2 C版本#include bits/stdc.h using namespace std; string s; int pos 0; int n; int dfs() { int max_len 0; int current_len 0; while (pos n) { if (s[pos] x) { current_len; pos; } else if (s[pos] |) { max_len max(max_len, current_len); current_len 0; pos; } else if (s[pos] () { pos; current_len dfs(); } else if (s[pos] )) { pos; break; } } max_len max(max_len, current_len); return max_len; } int main() { cin s; n s.size(); cout dfs() endl; return 0; }C版本和Python版本逻辑完全一致只是语法不同。注意pos和n都定义成了全局变量这样在dfs里可以直接访问和修改。5.3 手动模拟一遍执行过程为了让你彻底理解这段代码我们拿x(xx|xxx)x这个例子手动走一遍初始状态pos0max_len0current_len0s[0]xcurrent_len1pos1s[1](pos2递归调用dfs()子调用max_len0current_len0s[2]xcurrent_len1pos3s[3]xcurrent_len2pos4s[4]|max_len2current_len0pos5s[5]xcurrent_len1pos6s[6]xcurrent_len2pos7s[7]xcurrent_len3pos8s[8])max_lenmax(2,3)3pos9break返回max_len3回到主调用current_len 3变成134pos9s[9]xcurrent_len5pos10循环结束max_lenmax(0,5)5返回5最终答案是5和我们的预期一致。6. 那些年我踩过的坑五个常见错误及修复方案6.1 忘记在递归前跳过左括号这是最常见的错误。如果你在遇到(时直接调用dfs()而不先pos那么子调用会再次看到同一个(然后再次递归导致无限递归直到栈溢出。修复方案在递归调用之前务必先pos 1跳过左括号。6.2 遇到右括号后忘记做最后一次max比较这个错误很隐蔽因为它在很多测试用例上都能通过只有在特定情况下才会暴露。比如xx|xxx在括号内时如果遇到)直接返回而不比较max_len就停留在2丢失了xxx的长度3。修复方案在break之前一定要执行max_len max(max_len, current_len)。6.3 全局变量pos没有重置如果你在多个测试用例之间复用同一个pos变量忘记重置的话第二个用例会从第一个用例结束的位置开始扫描结果完全错误。修复方案每次处理新用例前把pos重置为0。或者干脆把pos定义在函数内部用nonlocal访问。6.4 把|的优先级理解错了有些同学会认为|的优先级低于括号所以在处理括号内的|时需要特殊处理。但实际上在这道题里括号内的|和括号外的|处理逻辑完全一样都是结算当前段重置计数器。递归调用天然地隔离了不同层级的|你不需要额外考虑优先级问题。修复方案相信递归的力量不要人为增加复杂度。6.5 输入字符串包含空格或换行有些测试用例的输入可能包含多余的空格或换行符如果你直接用input()而不做strip()可能会把空格也当成表达式的一部分导致解析错误。修复方案读取输入后立即strip()去掉首尾空白字符。注意这道题的输入保证是合法的正则表达式所以你不必考虑非法输入的情况。但在实际工程中解析表达式时一定要做合法性校验。7. 从这道题延伸出去DFS处理嵌套结构的通用套路7.1 识别嵌套结构类问题的特征这道题的核心特征是什么是括号嵌套。表达式可以无限层嵌套每一层的处理逻辑完全相同只是作用范围不同。这类问题在算法竞赛中非常常见比如括号匹配与嵌套深度计算表达式的解析与求值如四则运算JSON/XML等嵌套格式的解析树形结构的遍历它们的共同点是结构是递归定义的处理逻辑也是递归的。7.2 递归函数的设计模板对于这类问题递归函数通常遵循以下模板def dfs(): # 初始化当前层的状态 result 初始值 current 初始值 while 还有输入: if 遇到基础元素: # 直接处理 current 更新(current) elif 遇到分隔符: # 结算当前段 result 合并(result, current) current 重置 elif 遇到左括号: # 递归进入下一层跳过左括号 current 合并(current, dfs()) elif 遇到右括号: # 结算并返回 result 合并(result, current) 跳过右括号 return result # 循环结束后的收尾 result 合并(result, current) return result这个模板可以套用到很多类似问题上。你只需要根据具体问题替换基础元素、分隔符、合并方式和重置方式即可。7.3 一个变体如果要求的是最短长度假设题目改成求最短匹配长度你只需要把max换成min并且注意初始值的设置。max的初始值通常是0而min的初始值需要设为一个很大的数比如float(inf)。其他逻辑完全不变。7.4 另一个变体如果支持*量词如果题目增加*表示前面的元素可以重复任意次那么处理逻辑会复杂一些。你需要在遇到*时把前一个元素的长度乘以一个系数0次就是01次就是原长度多次就是无限大。但整体的递归框架是不变的只是在基础元素的处理上增加了一种情况。7.5 实际工程中的应用虽然这道题是竞赛题但它背后的DFS思想在实际工程中也有广泛应用。比如配置文件解析解析嵌套的JSON或YAML配置提取最深层的值。模板引擎处理嵌套的模板标签如{% if %}里面嵌套{% for %}。编译器前端解析源代码中的嵌套括号和表达式。我在实际项目中就遇到过一个类似的问题需要从一个嵌套的配置结构中提取所有叶子节点的路径。当时用的就是DFS递归代码不到50行就搞定了比用栈迭代清晰得多。8. 测试用例设计与验证怎么确认你的代码真的对了8.1 基础测试用例写完代码后不要急着提交先用几个基础用例验证一下输入期望输出验证点x1最简单情况xx2连续xx|x1或运算取maxxx|xxx3或运算取max(x)1单层括号(xx)2单层括号x(xx|xxx)x5括号嵌套前后缀((xx|xxx)x|xx)x5多层嵌套8.2 边界测试用例除了基础用例还要考虑一些边界情况空字符串虽然题目保证输入合法但你可以测试一下空字符串看看代码会不会崩溃。只有括号如()理论上应该返回0但题目可能不会给这种输入。深层嵌套如((((x))))测试递归深度是否会导致栈溢出。大量或运算如x|x|x|x|...|x测试性能。8.3 对拍验证如果你不确定自己的代码是否正确可以写一个暴力解法来对拍。暴力解法的思路是枚举所有可能的匹配字符串取最长长度。虽然暴力解法效率低但对于小规模输入它可以作为验证标准。def brute_force(s): # 递归展开所有可能性 def expand(expr): # 返回所有可能的字符串集合 results set() # 处理或运算 parts split_by_or(expr) for part in parts: # 处理括号和x ... return results all_strings expand(s) return max(len(t) for t in all_strings)对拍的方法是随机生成大量小规模表达式分别用DFS解法和暴力解法计算比较结果是否一致。如果所有用例都一致说明你的DFS解法大概率是正确的。8.4 性能测试这道题的时间复杂度是O(n)因为每个字符最多被访问一次。空间复杂度是O(d)其中d是括号的最大嵌套深度也就是递归栈的深度。对于蓝桥杯的测试数据规模通常n不超过1000这个复杂度完全够用。但如果你担心递归深度过大导致栈溢出可以把递归改成显式栈的迭代写法。不过对于这道题来说没必要因为嵌套深度通常不会太大。9. 一些实战中的小技巧和心得9.1 用print大法调试递归递归代码最难调试的地方在于你不知道每一层递归的pos和current_len是多少。我的做法是在关键位置加print语句输出当前层的信息def dfs(): nonlocal pos max_len 0 current_len 0 print(f进入dfs, pos{pos}) while pos n: # ... print(f处理{s[pos]}, pos{pos}, current_len{current_len}, max_len{max_len}) print(f离开dfs, 返回{max_len}) return max_len这样你就能清楚地看到每一层递归的进入和离开以及每一步的状态变化。虽然输出会很多但对于理解递归流程非常有帮助。9.2 用缩进表示递归深度如果你觉得print输出太乱可以在print时加上缩进用缩进的层数表示递归深度depth 0 def dfs(): global depth depth 1 indent * depth print(f{indent}进入dfs, pos{pos}) # ... print(f{indent}离开dfs, 返回{max_len}) depth - 1 return max_len这样输出就会像树形结构一样一目了然。9.3 注意Python的递归深度限制Python默认的递归深度限制是1000。如果你的表达式嵌套深度超过1000会抛出RecursionError。虽然蓝桥杯的测试数据不太可能这么极端但你可以通过sys.setrecursionlimit(10000)来增加限制。9.4 竞赛中的输入输出优化如果输入字符串很长用sys.stdin.readline()比input()快。输出用print()就够了不需要额外优化。9.5 这道题在蓝桥杯中的定位这道题在蓝桥杯历届试题中属于中等难度。它的难点不在于算法本身而在于能否想到用DFS来处理嵌套结构。一旦你想通了这一点代码其实很短。我见过很多同学在这道题上卡了很久就是因为一开始想复杂了试图用栈或者字符串替换来解决问题。提示遇到嵌套结构的问题第一反应应该是能不能递归。递归是处理嵌套结构最自然的方式没有之一。10. 写在最后递归思维比代码本身更重要这道题表面上考的是DFS实际上考的是你能不能把嵌套结构映射成递归调用。这个思维模式一旦建立起来你会发现很多看似复杂的问题都变得简单了。我后来在做其他题目时经常遇到类似的情况一看到括号嵌套、树形结构、分治问题脑子里就会自动浮现出递归的框架。这种条件反射不是天生的而是通过反复练习这道题这样的经典题目培养出来的。如果你现在还在纠结这道题的代码细节我的建议是先把代码背下来然后手动模拟几遍执行过程直到你能不假思索地写出正确的递归逻辑。到那时候你就真正掌握了DFS处理嵌套结构的精髓。最后分享一个我个人的习惯每做完一道经典题我都会把它的核心思路用一句话总结出来记在笔记本上。这道题的总结就是遇到括号就递归遇到或运算就取max遇到x就累加。短短一句话涵盖了整道题的所有逻辑。下次再遇到类似的题目我只需要回忆这句话就能快速写出代码。

蓝桥杯正则问题：DFS递归解嵌套表达式求最长匹配

相关推荐

编译原理课设实践：自动机压缩、语法树与文法处理器全解析

CSP-J初赛真题：信奥能力诊断与工程化备考指南

JPG转WebP在线工具怎么选？压缩原理与参数设置全指南

更多资讯

Java编程进阶：算法、Lambda与API的实战结合

ngx-bootstrap Carousel 禁用循环播放（Disable Slide Looping）完整指南：从 use-case 规格到源码实现

tf-quant-finance EurodollarFutures 定价指南：构造参数、结算公式与源码实现

AI 软件开发全流程工具全景图（2025前沿版）：用 TaoToken 统一 Key 打通编码到部署链路

用my-translator的Read模式做离线越南语朗读器：分块合成、预取缓存与逐块错误标记是如何做到的

酒店评论中文情感分析系统实战：数据清洗、机器学习建模与避坑指南

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？