1225. 正则问题

本文主要是介绍1225. 正则问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一个字符串，由()|x四种字符组成，问得到的最长的x是多少个。

因为是要得到最长，所以 | 符号选择左右两边较长的那一串x。括号的话就是括号内是一个x串的整体。

思路：

其实这道题看起来就i是一道简单的模拟题。可以使用栈来实现。但是这里我们用递归来实现。

从头开始对整个字符串进行dfs，res表示dfs得到的x串的长度。
当遇到的字符是（ 的时候，就调用dfs，res+=dfs，因为左右括号里的串是可以直接加在x串上的。
当遇到的字符是 ） ，直接break，因为表示括号结束，跳出循环。
当遇到的字符是 | ，res = max（res，dfs），因为 | 要取两边的较大值。
当遇到的字符是x，res++，可以直接加在x串中。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std ;int k ;
string s;int dfs(){int res = 0;while(k < s.size()){if(s[k] == '('){k++;res += dfs();k++;}else if(s[k] == ')')break;else if(s[k] == '|'){k++;res = max(res , dfs());}else{k++;res++;}}return res;
}int main(){cin >> s;cout << dfs() << endl ;return 0 ;}

这篇关于1225. 正则问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---