蓝桥杯-PREV35-正则问题
问题描述 考虑一种简单的正则表达式： 只由 x ( ) | 组成的正则表达式。 小明想求出这个正则表达式能接受的最长字符串的长度。 例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。输入格式 一个由x()|组成的正则表达式。输入长度不超过100，保证合法。输出格式 这个正则表达式能接受的最长字符串的长度。样例输入 ((xx|xxx)x|(x|xx))xx样例输出 6 数据规模和约定 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms解题思路： 首先，输入string 表达式，正则表达式由 x ( ) | 组成，x是字符，|是运算，A|B=max(A,B)，()和计算四则运算时的作用一样。 然后，用DFS搜索，遇到“（”是运算的起点，遇到")"是运算的终点，遇到“|”，用max()计算，调用DFS函数，一直到搜索到正则表达式length时退出DFS函数。 最后，输出表达式中字符串的max length。 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int k; string str; int dfs(){ int res=0; //记录字符串的长度 while(k<str.size()){ if(str[k]=='('){ k++; res+=dfs(); k++; } else if(str[k]=='|'){ k++; res=max(res,dfs()); } else if(str[k]==')'){ break; } else{ res++; k++; } } return res; } int main(){ cin>>str; cout<<dfs()<<endl; return 0; }