PAT (Basic Level) Practice 1003:我要通过（python）

题目描述

输入样例

10
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
APATTAA

输出样例

YES
YES
YES
YES
NO
NO
NO
NO
NO
NO

题中还要求输入和输出末尾不换行。

思路

答案正确的第一个必要条件：仅有P、A、T。

xPATx是正确的，然后是递推式。

递推式能告诉我们些什么？

给出递推的源头，可以得到发展出的结果。
给出发展出的结果，也应该可以找到递推的源头。

递推式的内容：若aPbTc正确，则aPbATca正确。即如果aPbTc正确，那么在P、T间b后的string尾加"A"，在T后的string尾加字符串a，得到的串也正确。再递推，则是P，T间成为bAA，T后成为caa，其他不变。

也就是说递推得到的正确string是：和最初aPbTc相比，b后多了多少"A"，T后多了多少a。
那么将要判断的string去掉这些多的"A"（为多的"A"计数counts，replace( $c o u n t s ? A$ , “”, 1)），
和多的a（replace( $c o u n t s ? a$ , “”, 1)），得到源头为aPbTc这样的形式，如果是正确的，那么它就是正确的。

另外，我们的大脑或许早发现了（并行地？）正确的源头aPbTc：它必须是xPATx，因为它不是由递推规则得到，因而只能是另外的方式（往往直接地）给出的答案，这里就是条件2。

即a = c，b = A，仅有一个P，T，且P在T前。

还要考虑string就是最初的string：对正确的它（xPATx）进行上述过程，得到它自身，然后判断它自身，为YES，非xPATx则判断为NO。故对最初的string不需另写判断方法。

所以我们的解法是：对要判断的每个string，其中仅有P，A，T三种字符的，寻找递推的源头？其他say NO？开始写代码？

不，这属于是"解法（代码）未完整呈现思路"。当我们写好上述流程的代码时，发现部分测试不通过。
实际上在我们看到样例APATTAA得到输出为"NO"时，我们就应该想到，该string不用寻找递推源头，而直接say NO。

不能直接否定，而要进一步判断的string，是仅有一个P，T的，且P在T之前的。
这个信息本就包含在了"其他不变"（递推式的内容）中：要进一步判断的string，P前仅有a，仅有一个P，T，P在T前。写了string仅有P，A，T的必要前提加上P，T另外的必要前提，且P前a可为空，则不用写P前a的必要前提。

代码

import re
n = int(input())
for i in range(n):
    s = input()
    # 对仅含PAT三种字符,且仅有一个P，一个T， P在T前，才进一步判断。
    # 如何判断仅含这三种字符：我的办法，先看三者是否存在其中(in s),
    # 再将他们都替换为""得changed_s(原s后面要进一步判断），若它不为空，则不仅含这三种字符。
    if "P" in s and "A" in s and "T" in s and s.count("P") == 1 and s.count("T") == 1 and s.find("P") < s.find("T"):
        changed_s = s.replace("P", "")   
        # 注意，当原字符串没有被替换字符时，不会发生替换操作，而返回原串。
        # 因而若没有先前判in s的步骤，而仅有这三步替换时：原串其实少了某种字符（如原串是PA）但发现不了，
        # 应print“NO”，却进入进一步判断，且判断出错。
        changed_s = changed_s.replace("A", "")
        changed_s = changed_s.replace("T", "")
        if changed_s != "":
            print("NO", end="")
        else:
            s_split = re.split("[PT]", s)
            # 正确的又一个必要条件，分割出来的是三段：当保证仅有1个P，一个T时，
            # 就已经满足。若存在段是""，仍会分出，不报错
            mid_a_counts = s_split[1].count("A")
            tail_to_reduce = (mid_a_counts - 1) * s_split[0]
            s_split[2] = s_split[2].replace(tail_to_reduce, "", 1)
            s_split[1] = s_split[1].replace((mid_a_counts - 1) * "A", "", 1)
            if s_split[1] == "A" and s_split[0] == s_split[2]:
                print("YES", end="")
            else:
                print("NO", end="")
    else:
        print("NO", end="")
    if i != n - 1:
        print("")