PAT(乙) : 1003. 我要通过！

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：

1. 字符串中必须仅有P, A, T这三种字符，不可以包含其它字符；
2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a, b, c 均或者是空字符串，或者是仅由字母 A 组成的字符串。

现在就请你为PAT写一个自动裁判程序，判定哪些字符串是可以获得“ 答案正确”的。

输入格式：每个测试输入包含1个测试用例。第1行给出一个自然数n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过100，且不包含空格。

输出格式：每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出YES，否则输出NO。

输入样例：

8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

输出样例：

YES
YES
YES
YES
NO
NO
NO
NO

第一个条件好判断，第三个条件是以第二个条件为前提，要判断aPbATca是否正确，要先拆解，若能拆解得出第二个条件，则aPbATca正确，我用递归将之拆解，我将aPbTc 换成了（firstA）P(midA)T(lastA)形式，那对于aPbATca来说，a = firstA,b = midA-1,c = lastA-firstA，然后不断递归，直到满足第二个条件即为正确，或者不符合第一个条件即为错误。

代码如下：

#include"stdio.h"
int recur_Judge(int firstA,int midA,int lastA)
{
 if(firstA<0||midA==0||lastA<0)
 {
  return 0;
 }
 if ((firstA==lastA)&&midA==1)//P前和C后的A个数相同且中间只有一个A
 {
  return 1;
 }
 else
 {
  int a = firstA,b = midA-1,c = lastA-firstA;//根据题中aPbTc与aPbATca的规律得出。
  return recur_Judge(a,b,c);//递归判断
 }
}
int judge(char str[])
{
 int i=0;
 int firstA=0,midA=0,lastA=0;//firstA：P前的A个数；midA：P后且T前的A个数；lastA：T后A个数
 int P,A,T;//保存PAT三字母出现的次数
 P=A=T=0;
 while (str[i]!='\0')
 {
  switch (str[i])
  {
  case 'P':
   if (P==1)
   {
    return 0;//如果P已经出现过，此时再次出现，则返回错误
   }
   P = 1;break;//若P是第一次出现，打标记
  case 'A':
   A = 1;//给A打标记
   if (P==0)
   {
    firstA++;//还没有出现P，A记录++
   }
   else
   {
    if (T==0)
    {
     midA++;//出现P，还没有出现T，A记录++
    }
    else
    {
     lastA++;//出现P,T，A记录++
    }
   }break;
  case 'T':   //与P同理
   if (T)
   {
    return 0;
   }
   T = 1;break;
  default:return 0;break;//若出现非PAT字母，返回错误
  }
  i++;
 }
 if (P==0||A==0||T==0)
 {
  return 0;//若有一个字母未出现，返回错误
 }
 if(recur_Judge(firstA,midA,lastA))//判断第2、3种情况
 {
  return 1;
 }
 else
 {
  return 0;
 }
}
int main()
{
 int n;
 char str[100];
 scanf("%d",&n);
 for (int i=0;i<n;i++)
 {
  scanf("%s",str);
  if (judge(str)==1)
  {
   printf("YES\n");
  }
  else
  {
   printf("NO\n");
  }
 }
 return 0;
}