题目

原题链接

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于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

解析

规则如下：
对于(x)PAT(x)一定是正确的，其中(x)是空字符串或者由A组成的字符串，并且两个(x)是相等的
而所有的(x)PA(*n)T(x*n)也是正确的，也即P和T中间A的个数 乘上 P前面A的个数 等于 T后面A的个数

再加上判断P和T中间至少有一个A即可

代码

C++解法

#include <cstdio>
#include <cstring>

const int maxn = 105;
char s[maxn];

bool judge() {
    bool hasP = false;
    bool hasT = false;
    bool wrong = false;
    int aNums[3] = {0, 0, 0};
    int len = strlen(s);
    for (int i = 0; i < len && !wrong; ++i) {
        if (s[i] == 'A') {
            if (!hasP && !hasT)
                ++aNums[0];
            if (hasP && !hasT)
                ++aNums[1];
            if (hasP && hasT)
                ++aNums[2];
            if (!hasP && hasT)
                wrong = true;
            continue;
        }
        if (s[i] == 'P') {
            if (hasP)
                wrong = true;
            else
                hasP = true;
            continue;
        }
        if (s[i] == 'T') {
            if (hasT)
                wrong = true;
            else
                hasT = true;
            continue;
        }
        wrong = true;
    }
    return hasP && hasT && aNums[1] >= 1 && (aNums[1] * aNums[0] == aNums[2]) &&
           !wrong;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", s);
        printf("%s\n", judge() ? "YES" : "NO");
    }
    return 0;
}

Python解法

import re


def judge(s):
    wrong = False
    l = s.split('P')
    if len(l) != 2:
        return False
    r = l[1].split('T')
    if len(r) != 2:
        return False
    if not re.match(r'[PAT]+', s):
        return False

    # print([l[0], r[0], r[1]])

    return (len(l[0]) * len(r[0]) == len(r[1])) and len(r[0]) > 0


n = int(input())
for i in range(n):
    s = input()
    print("YES" if judge(s) else "NO")

Java解法

import java.util.Scanner;

class Main {
    static Scanner in;

    public static boolean check(String s) {
        boolean hasP = false;
        boolean hasT = false;
        boolean wrong = false;
        int[] aNums = { 0, 0, 0 };

        for (int i = 0; i < s.length() && !wrong; ++i) {
            char c = s.charAt(i);
            if (c == 'P') {
                if (hasP == true) {
                    wrong = true;
                } else {
                    hasP = true;
                }
                continue;
            }
            if (c == 'T') {
                if (hasT == true) {
                    wrong = true;
                } else {
                    hasT = true;
                }
                continue;
            }
            if (c == 'A') {
                if (!hasP && !hasT) {
                    ++aNums[0];
                }
                if (hasP && !hasT) {
                    ++aNums[1];
                }
                if (hasP && hasT) {
                    ++aNums[2];
                }
                if (!hasP && hasT) {
                    wrong = true;
                }
                continue;
            }
            wrong = true;
        }
        // System.out.printf("%s %b %d %d %d\n",s,wrong,aNums[0],aNums[1],aNums[2]);
        return hasP && hasT && (!wrong && (aNums[0] * aNums[1] == aNums[2]) && aNums[1] > 0) == true;
    }

    public static void main(String args[]) {
        in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; ++i) {
            String s = in.next();
            if (check(s) == true)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
        in.close();
    }
}