（2017蓝桥杯省A）洛谷P8650题解：递归解析正则表达式并求解**长度

ftggdnt

一、题目解读

洛谷P8650题要求解析由‘x’、‘|’和括号组成的表达式，计算并输出其**长度。题目核心在于处理嵌套括号与‘|’分隔的项。

二、解题思路

使用递归策略：

1. 解析因子：识别单个‘x’或括号表达式，递归处理括号内内容，累加长度。

2. 解析项：通过‘|’分隔，递归调用因子解析，动态更新**长度。

3. 整体解析：顶层调用项解析函数，最终返回全局**值。

利用递归处理嵌套结构，结合动态比较优化效率。

三、解题步骤

1. 输入处理：读取表达式字符串，初始化解析指针pos=0。

2. 顶层解析：调用parseExpr() → 调用parseTerm() → 递归调用parseFactor()处理因子。

3. 递归细节：

○ 因子解析：遇‘x’递增长度，遇‘(’递归解析子表达式并跳过‘)’。

○ 项解析：循环处理‘|’分隔的多个因子，动态记录最长项。

4. 输出结果：返回最终解析的**长度。

四、代码与注释

1. #include <iostream>
   
2. #include <string>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. string s;
   
7. int pos = 0;
   
8. 
   
9. // 解析表达式并返回**长度
   
10. int parseExpr() {
    
11. return parseTerm(); // 顶层为项
    
12. }
    
13. 
    
14. // 解析因子(由原子或括号表达式组成)
    
15. int parseFactor() {
    
16. int total = 0;
    
17. while (pos < s.size() && (s[pos] == 'x' || s[pos] == '(')) {
    
18. if (s[pos] == 'x') { // 原子x累加
    
19. total++;
    
20. pos++;
    
21. } else { // 处理括号表达式
    
22. pos++; // 跳过'('
    
23. int len = parseExpr(); // 递归解析子表达式
    
24. pos++; // 跳过')'
    
25. total += len;
    
26. }
    
27. }
    
28. return total;
    
29. }
    
30. 
    
31. // 解析项(由因子通过|连接)
    
32. int parseTerm() {
    
33. int max_len = parseFactor(); // 初始化为**因子长度
    
34. while (pos < s.size() && s[pos] == '|') {
    
35. pos++; // 跳过'|'
    
36. max_len = max(max_len, parseFactor()); // 更新**长度
    
37. }
    
38. return max_len;
    
39. }
    
40. 
    
41. int main() {
    
42. cin >> s;
    
43. cout << parseExpr() << endl;
    
44. return 0;
    
45. }

复制代码

注释说明：代码通过递归函数分层解析，利用while循环处理分隔符，动态比较机制确保捕获全局**值。

五、总结

本解法巧妙结合递归与动态规划思想，通过分层解析（表达式→项→因子）高效处理嵌套结构。代码简洁且无需额外空间，适合处理类似表达式解析问题。关键点在于递归终止条件的设计（括号匹配与分隔符检测），为同类算法设计提供参考。

来源：（2017蓝桥杯省A）洛谷P8650题解：递归解析正则表达式并求解**长度