PAT-B-1003

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

思路分析

这题我想复杂了,看到条件二 xPATx 不自觉想到正则表达式的反向引用,但是条件三用正则比较复杂,虽然此题 AC 了,但是做的实在是很不漂亮,以后有时间还得重新研究一下。

条件1,2都非常简单

条件3要难点在于条件是递归式的,简单计算易得, a * b = c

c++ 应该使用 “.” 保证转义,如 .1

正则搜索迭代器 regex_search() 注意不能用 “A*” 等无底线要求,会无限迭代

最后输出注意空行 \n

举一反三

正则虽好,其局限性也要在考虑范围内

推荐一本正则表达式的阅读书籍,我已经看完了,写的非常好:
精通正则表达式

我这边有复印版,想要的朋友也可以联系我

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <regex>
/*注意事项:
* 条件1,2都非常简单
* 条件3要难点在于条件是递归式的,简单计算易得, a * b = c
* c++ 应该使用 "\\" 保证转义,如 "\\1"
* 正则迭代器注意不能用 "A*" 等无底线要求,会无限迭代
* 最后输出注意空行 "\n"
* */
using namespace std;

int num = 0;
string str;
regex regex_1("[P|A|T]+");//满足条件一
regex regex_2("(A*)PAT\\1");//满足条件二直接输出
regex regex_3("A*PA+TA*");//条件三的大前提
regex regex_4("A+");//找到 A 的数量

bool checkString(string str) {
int i = 0;
bool r1, r2, r3, r4;
smatch result;
string temp[3];
string::const_iterator iterStart = str.begin();
string::const_iterator iterEnd = str.end();

r1 = regex_match(str, regex_1);
r2 = regex_match(str, regex_2);
r3 = regex_match(str, regex_3);


//使用迭代器,将正则匹配到的结果存在 temp[] 里
while (regex_search(iterStart, iterEnd, result, regex_4)) {
temp[i++] = result[0];
iterStart = result[0].second;
}

//满足 a * b = c
r4 = ((temp[0].size() * temp[1].size() == temp[2].size()));

//r1 必须满足,r2 或 r3 && r4 满足即可
if (r1 && (r2 || (r3 && r4))) {
return true;
} else return false;
}

int main() {
cin >> num;
string arr[num];
for (int i = 0; i < num; i++) {
cin >> str;
if (checkString(str)) {
arr[i] = "YES";
} else arr[i] = "NO";
}
for (int i = 0; i < num; i++) {
cout << arr[i] << "\n";
}

return 0;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2020-2023 Jack Kong
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信