UVa 384 Slurpys

题目描述

基于一组约束识别字符串是一个常见的计算问题。

Slurpy\texttt{Slurpy}Slurpy是一种具有特定属性的字符串。你的程序将读取字符串并判断它们是否为Slurpy\texttt{Slurpy}Slurpy。

定义

Slump\texttt{Slump}Slump是一个满足以下属性的字符串：

1. 第一个字符是D或E
2. 第一个字符后跟一个或多个F
3. F的序列后跟一个Slump\texttt{Slump}Slump或一个G，以此结束整个Slump\texttt{Slump}Slump
4. 除此之外都不是Slump\texttt{Slump}Slump

例如：DFFEFFFG是一个Slump\texttt{Slump}Slump（以D开头，后跟两个F，再跟Slump\texttt{Slump}SlumpEFFFG）

Slimp\texttt{Slimp}Slimp是一个满足以下属性的字符串：

1. 第一个字符是A
2. 如果是两个字符的Slimp\texttt{Slimp}Slimp，则第二个字符是H
3. 如果不是两个字符，则属于以下两种形式之一：
   • A+B+Slimp\texttt{Slimp}Slimp+C
   • A+Slump\texttt{Slump}Slump+C
4. 除此之外都不是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;}