UVa 384 Slurpys
题目描述
基于一组约束识别字符串是一个常见的计算问题。
Slurpy\texttt{Slurpy}Slurpy是一种具有特定属性的字符串。你的程序将读取字符串并判断它们是否为Slurpy\texttt{Slurpy}Slurpy。
定义
Slump\texttt{Slump}Slump是一个满足以下属性的字符串：
- 第一个字符是
D或E - 第一个字符后跟一个或多个
F F的序列后跟一个Slump\texttt{Slump}Slump或一个G，以此结束整个Slump\texttt{Slump}Slump- 除此之外都不是Slump\texttt{Slump}Slump
例如：DFFEFFFG是一个Slump\texttt{Slump}Slump（以D开头，后跟两个F，再跟Slump\texttt{Slump}SlumpEFFFG）
Slimp\texttt{Slimp}Slimp是一个满足以下属性的字符串：
- 第一个字符是
A - 如果是两个字符的Slimp\texttt{Slimp}Slimp，则第二个字符是
H - 如果不是两个字符，则属于以下两种形式之一：
A+B+Slimp\texttt{Slimp}Slimp+CA+Slump\texttt{Slump}Slump+C
- 除此之外都不是Slimp\texttt{Slimp}Slimp
Slurpy\texttt{Slurpy}Slurpy是一个由Slimp\texttt{Slimp}Slimp后跟Slump\texttt{Slump}Slump组成的字符串。
输入格式
第一行包含整数NNN（1≤N≤101 \leq N \leq 101≤N≤10），表示字符串数量。接下来NNN行，每行包含一个由字母组成的字符串（长度1∼601 \sim 601∼60）。
输出格式
第一行输出SLURPYS OUTPUT。接下来NNN行，每行输出YES或NO。最后一行输出END OF OUTPUT。
样例输入
2 AHDFG DFGAH样例输出
SLURPYS OUTPUT YES NO END OF OUTPUT题目分析
问题的本质
这是一个递归下降解析问题。需要根据给定的上下文无关文法判断字符串是否属于定义的语言。
文法规则
Slump → D F+ (Slump | G) Slimp → A H | A B Slimp C | A Slump C Slurpy → Slimp Slump解析方法
使用递归下降解析器，维护一个全局位置指针，尝试匹配规则。
参考代码
// Slurpys// UVa ID: 384// Verdict: Accepted// Submission Date: 2016-06-30// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;boolisC();boolisSlump();boolisSlimp();boolisSlurpy();string line;intposition;// 解析字符 'C'boolisC(){if(position<line.length()&&line[position]=='C'){position++;returntrue;}returnfalse;}// 解析 Slump: D/E F+ (Slump | G)boolisSlump(){if(position>=line.length())returnfalse;if(line[position]!='D'&&line[position]!='E')returnfalse;position++;// 至少一个 FboolatLeastOneF=false;while(position<line.length()&&line[position]=='F'){atLeastOneF=true;position++;}if(!atLeastOneF)returnfalse;// 以 G 结尾if(position<line.length()&&line[position]=='G'){position++;returntrue;}// 或者后面跟一个 SlumpreturnisSlump();}// 解析 Slimp: A H | A B Slimp C | A Slump CboolisSlimp(){if(position>=line.length()||line[position]!='A')returnfalse;position++;// 情况1：AHif(position<line.length()&&line[position]=='H'){position++;returntrue;}// 情况2：A B Slimp Celseif(position<line.length()&&line[position]=='B'){position++;if(!isSlimp())returnfalse;if(position<line.length()&&line[position]=='C'){position++;returntrue;}returnfalse;}// 情况3：A Slump Celse{if(!isSlump())returnfalse;if(position<line.length()&&line[position]=='C'){position++;returntrue;}returnfalse;}}// 解析 Slurpy: Slimp + SlumpboolisSlurpy(){intsavedPos=position;if(isSlimp()&&isSlump()&&position==line.length())returntrue;position=savedPos;returnfalse;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);string firstLine;getline(cin,firstLine);intn=stoi(firstLine);cout<<"SLURPYS OUTPUT"<<endl;for(inti=1;i<=n;i++){getline(cin,line);position=0;cout<<(isSlurpy()?"YES":"NO")<<endl;}cout<<"END OF OUTPUT"<<endl;return0;}