PAT 乙級 1003 我要通過！：字符串模式匹配遞歸定義解析

題目規則遞歸定義

合法字符串僅含P、A、T三字符，滿足：
1. xPATx合法，x為空串或純A串。
2. 若aPbTc合法，則aPbATca合法（a,b,c為空或純A）。

等價數學條件：設P前A數為a，P-T間A數為b，T後A數為c。則必須滿足：
a ≥ 0, b ≥ 1, c = a × b，且整串無其他字符。

算法邏輯

1. 掃描字符串統計P、T各出現1次，A至少1次，無其他字符。
2. 記錄P、T位置posP、posT，計算a = posP、b = posT - posP - 1、c = len - posT - 1。
3. 判斷a * b == c。

C語言實現

#include 
#include 
#include 
#define MAXL 101

int main() {
    int n; scanf("%d", &n);
    char **s = malloc(n * sizeof(char*));
    for (int i = 0; i < n; i++) {
        s[i] = malloc(MAXL);
        scanf("%s", s[i]);
    }
    for (int i = 0; i < n; i++) {
        int cntP=0, cntT=0, cntA=0, other=0;
        char *pP=NULL, *pT=NULL;
        for (int j=0; s[i][j]; j++) {
            if (s[i][j]=='P') { cntP++; pP=&s[i][j]; }
            else if (s[i][j]=='T') { cntT++; pT=&s[i][j]; }
            else if (s[i][j]=='A') cntA++;
            else other=1;
        }
        int ok = (cntP==1 && cntT==1 && cntA>0 && !other);
        if (ok) {
            int a = pP - s[i];
            int b = pT - pP - 1;
            int c = strlen(pT) - 1;
            ok = (a * b == c);
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

樣例驗證