洛谷P8650题（2017年蓝桥杯省A）：递归下降法解决正则问题

一、题目解读

题目要求计算由字符'x'、'|'和括号组成的特殊表达式中，能够匹配到的最长连续'x'串长度。该表达式支持两种操作：连接（隐式）和或运算（|），考察字符串解析和递归算法的综合应用能力。

二、解题思路

采用递归下降分析法构建三级解析器：

1. 表达式级(parseExpr)：作为入口调用项级解析

2. 项级(parseTerm)：处理|或运算，返回最大值

3. 因子级(parseFactor)：处理基础单元(x)和嵌套表达式

三、解题步骤

1. 全局初始化：定义字符串s和位置指针pos

2. 因子解析：

• 遇到x时计数并移动指针

• 遇到(时递归解析子表达式

3. 项解析：通过|比较多个因子的最大值

4. 表达式解析：作为语法分析的顶层入口

四、完整代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string s;
int pos = 0;

// 解析表达式并返回最大长度
int parseExpr();

// 解析因子(由原子或括号表达式组成)
int parseFactor() {
    int total = 0;
    while (pos < s.size() && (s[pos] == 'x' || s[pos] == '(')) {
        if (s[pos] == 'x') {
            total++;
            pos++;
        } else { // 处理括号表达式
            pos++; // 跳过'('
            int len = parseExpr();
            pos++; // 跳过')'
            total += len;
        }
    }
    return total;
}
// 解析项(由因子通过|连接)
int parseTerm() {
    int max_len = parseFactor();
    while (pos < s.size() && s[pos] == '|') {
        pos++;
        max_len = max(max_len, parseFactor());
    }
    return max_len;
}
// 解析整个表达式
int parseExpr() {
    return parseTerm();
}

int main() {
    cin >> s;
    cout << parseExpr() << endl;
    return 0;
}

五、算法总结

本解法通过递归下降法实现LL(1)文法的自顶向下分析，时间复杂度O(n)优于正则表达式方案。关键点在于：

1. 使用全局pos指针维护解析进度

2. 通过函数调用栈实现括号嵌套

3. |运算符的即时最大值比较