[蓝桥杯2017初赛]正则问题 递归

题目描述

考虑一种简单的正则表达式：只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。  
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6

输入

输入一个由x()|组成的正则表达式。输入长度不超过100，保证合法。  

输出

输出这个正则表达式能接受的最长字符串的长度。  

样例输入

((xx|xxx)x|(x|xx))xx  

样例输出

6

题解：构造一个递归函数，计算括号内可取的最大字符长度，处理到结束即可

#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<string.h>
using namespace std;

string s;
int i=0,len;
int fun()
{
    int now=0,le=0;
    while(i<len)
    {
        if(s[i]=='(')
        {
            i++;
            now=now+fun();
        }
        else if(s[i]==')')
        {
            i++;
            break;
        }
        else if(s[i]=='|')
        {
            i++;
            le=max(le,now);//le 表示（到 |之间有几个 X
            now=0;//开始统计 |到）之间有几个X

        }
        else
        {
            i++;
            now++;
        }
        
    }
    return max(now,le);
}
int main()
{
    cin>>s;
    len=s.length();
    cout<<fun()<<endl;
    return 0;
}