一、题目解读
洛谷P8650题要求解析由‘x’、‘|’和括号组成的表达式,计算并输出其最大长度。题目核心在于处理嵌套括号与‘|’分隔的项。
二、解题思路
使用递归策略:
解析因子:识别单个‘x’或括号表达式,递归处理括号内内容,累加长度。
解析项:通过‘|’分隔,递归调用因子解析,动态更新最大长度。
整体解析:顶层调用项解析函数,最终返回全局最大值。
利用递归处理嵌套结构,结合动态比较优化效率。
三、解题步骤
○ 因子解析:遇‘x’递增长度,遇‘(’递归解析子表达式并跳过‘)’。
○ 项解析:循环处理‘|’分隔的多个因子,动态记录最长项。
- 输出结果:返回最终解析的最大长度。
四、代码与注释
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
int pos = 0;
// 解析表达式并返回最大长度
int parseExpr() {
return parseTerm(); // 顶层为项
}
// 解析因子(由原子或括号表达式组成)
int parseFactor() {
int total = 0;
while (pos < s.size() && (s[pos] == 'x' || s[pos] == '(')) {
if (s[pos] == 'x') { // 原子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 main() {
cin >> s;
cout << parseExpr() << endl;
return 0;
}
注释说明:代码通过递归函数分层解析,利用while循环处理分隔符,动态比较机制确保捕获全局最大值。
五、总结
本解法巧妙结合递归与动态规划思想,通过分层解析(表达式→项→因子)高效处理嵌套结构。代码简洁且无需额外空间,适合处理类似表达式解析问题。关键点在于递归终止条件的设计(括号匹配与分隔符检测),为同类算法设计提供参考。