P3719 [AHOI2017初中组] rexp
题目背景
为了解决形形色色的字符串匹配问题，正则表达式是一个强有力的工具。正则表达式通过定义一套符号体系，能够表示出需要查找的字符串所具有的性质。如a|aa能匹配a或aa，(a|b)c能匹配ac或bc。
题目描述
完整的正则表达式过于复杂，在这里我们只考虑由(、)、|和a组成的正则表达式。运算遵循下列法则：
有括号时，我们总是先算括号内的部分；
当两个字符串（或由括号定义的子串）间没有符号时，我们总把它们连起来作为一个整体；
|是或连接符，表示两边的字符串任取其一，若同一层里有多个或连接符，可以看作在这些或连接符所分开的若干字符串里任取其一。
例如，(aaa)aa|aa|(a(aa)a)、(aaaaa)|(aa)|aaaa和aaaaa|aaaa|aa是等价的，它们都能匹配长度为2 , 4 2,42,4或5 55的全a字符串。
下面给定一个简化正则表达式，试编程计算它最多能匹配多长的全a字符串。
输入格式
输入一行一个合法的简化正则表达式。
输出格式
一行一个整数，表示能匹配的最长全a字符串长度。
输入输出样例 #1
输入 #1
(aaa)aa|aa|(a(aa)a)输出 #1
5输入输出样例 #2
输入 #2
((a|aaa)|aa)|a输出 #2
3输入输出样例 #3
输入 #3
(a(aa|aaa)a|(a|aa))aa输出 #3
7说明/提示
【数据范围】
对于20 % 20\%20%数据，表达式长度不超过100 100100，且不存在括号。
对于40 % 40\%40%数据，表达式长度不超过100 100100。
对于70 % 70\%70%数据，表达式长度不超过2 × 10 3 2 \times 10^32×103。
对于100 % 100\%100%的数据，表达式长度不超过10 5 10^5105。
保证表达式合法（即|两端和括号内运算结果均非空字符串）。
C++实现
#include<stdio.h>#include<string.h>inti=1;charch[100005];intwork(){intlen=0,t;while(1){i++;if(ch[i]==')'){returnlen;}//右括号必须写在前面if(ch[i]=='a')len++;if(ch[i]=='(')len+=work();if(ch[i]=='|'){t=work();return(len>t)?len:t;}//这个地方必须加return}}intmain(){scanf("%s",ch+1);intlen,num,sum=0,max=0;len=strlen(ch+1);while(i<=len){if(ch[i]=='a')sum++,i++;elseif(ch[i]=='('){num=work();sum=sum+num;}elseif(ch[i]=='|')if(sum>max)max=sum,sum=0,i++;elsesum=0,i++;elseif(ch[i]==')')i++;}printf("%d",(sum>max)?sum:max);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
