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

fiwhgikbl

一、题目解读

洛谷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题解：递归解析正则表达式并求解**长度