问题描述
考虑一种简单的正则表达式：
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是 6。输入格式
一个由 x()| 组成的正则表达式。输入长度不超过 100，保证合法。输出格式
这个正则表达式能接受的最长字符串的长度。样例输入
((xx|xxx)x|(x|xx))xx样例输出
6
思路如下：
记住dfs的思想，大问题化小问题，注重相同性！！！！！！！这样的话想想怎么递归就会更容易想出来
我的想法是每碰见“(”和“|”就把右端看成一个式子，用dfs求那个式子的值，然后把值return回来，这样遍历下去。比如说式子((xx|xxx)x|(x|xx))xx，
i为0时，碰见“(”，进行一次dfs(i+1=1)，
在dfs(i+1)里又碰见“(”，再dfs(i+1=2)，此时s[i]='x'，开始统计出现个数，为2，
碰见“|”，那我又得把右端看成式子，用dfs求出右端的值，然后判断“|”左右两端的值大小，取最大的，确定“|”右端是否结束得看“)”
这时冲突就来了，“(”跟“|”的结束界限都是“)”，那如果两个碰见了“)”都跳过，那比如(xx|xxx)，“|”跳过了“)”，那我“(”如何知道结束了呢，解决办法就是在dfs时留一个位置，存我是为什么进入这个递归的，如果是因为碰见了“(”，那在碰见“)”后，我就可以跳过了，即i++，但是因为碰见“|”才进入递归的，就不能跳过，因为对于“|”来说，“)”仅仅为识别结束的标志，他们两个不相匹配。
代码如下：
#include <iostream>
using namespace std;
string s;
int dfs(char symbol,int& i) { int value=0;//dfs式子的总体值while(i<s.length()) {while(s[i]=='x'){value+=1;i++;}if(s[i]=='('){value+=dfs('(',++i);}if(s[i]=='|'){value=max(value,dfs('|',++i));}if(s[i]==')'){if(symbol=='(')i++;return value; }}return value;
}
int main() {cin>>s;int i=0;cout<<dfs('0',i);return 0;
}看了下别人的代码，用不上标记位，只需要在判断"(" 的语句里边dfs结束后，自己再进行i++即可
