PTA L1-064 估值一亿的AI核心代码,详解+每一个测试点的分析

题目说明：

作者 陈越 单位 浙江大学

本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是：

• 无论用户说什么，首先把对方说的话在一行中原样打印出来；
• 消除原文中多余空格：把相邻单词间的多个空格换成 1 个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉；
• 把原文中所有大写英文字母变成小写，除了 I；
• 把原文中所有独立的 can you、could you 对应地换成 I can、I could—— 这里“独立”是指被空格或标点符号分隔开的单词；
• 把原文中所有独立的 I 和 me 换成 you；
• 把原文中所有的问号 ? 换成惊叹号 !；
• 在一行中输出替换后的句子作为 AI 的回答。

输入格式：

输入首先在第一行给出不超过 10 的正整数 N，随后 N 行，每行给出一句不超过 1000 个字符的、以回车结尾的用户的对话，对话为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。

输出格式：

按题面要求输出，每个 AI 的回答前要加上

AI:

和一个空格。

输入样例：

6
Hello ?
 Good to chat   with you
can   you speak Chinese?
Really?
Could you show me 5
What Is this prime? I,don 't know

输出样例：

Hello ?
AI: hello!
 Good to chat   with you
AI: good to chat with you
can   you speak Chinese?
AI: I can speak chinese!
Really?
AI: really!
Could you show me 5
AI: I could show you 5
What Is this prime? I,don 't know
AI: what Is this prime! you,don't know

注意本题有些坑（警示后人）：

    I、此题的输入并不一定正常（如可能在字符串中穿插多个空格（前、中、后）、字符串可能以标点符号开头、标点符号前面的空格是不需要的）。

    II、可能会在第一次进行替换过后，恰好凑成了其他关键词（同一位置发生连续替换是错误行为）。
     如果成功解决以上问题，此题便解决了。

解题思路：

初级思路：

    看到这道题，首先的一个想法就是遍历字符串，遍历的同时看有无符合条件（即可替换的字符串），如若有可替换的字符串，立即替换即可。

#include<bits/stdc++.h>
using namespace std;
    string str;
string s1="can you",s11="I can";
string s2="could you",s22="I could";
string s31="I",s32="me",s33="you";
int isletter(char ch){
    if(ch>='A'&&ch<='Z'||ch>='a'&&ch<='z') return 1;
    return 0;
}

int main(){
    int N;cin>>N;getchar();
    for(int i=0;i<N;++i){
        getline(cin,str); 
        cout<<str<<endl;
        str=" "+str;
        //大写转小写 并格式化语句 
        for(int i=0;i<str.length();++i){
            if(str[i]==' '&&!isletter(str[i+1])&&!isdigit(str[i+1])){
                 str.erase(i,1); i--;
            }
            if(str[i]>='A'&&str[i]<='Z'&&str[i]!='I') str[i]+=32;
            if(str[i]=='?') str[i]='!';
        }
        //独立的 I 换成 you     string s31="I",s32="me",s33="you";
        for(int i=0;i<str.length();++i){
            i=str.find(s31,i);
            if(i==-1) break;
            if(!(isletter(str[i-1])||isletter(str[i+s31.length()])))
                str.replace(i,s31.length(),s33);
        }
    //    cout<<"str换前:"+str<<"---------"<<endl; 
        //独立的 me 换成 you     string s31="I",s32="me",s33="you";
        for(int i=0;i<str.length();++i){
            i=str.find(s32,i);
            if(i==-1) break;
            if(!isletter(str[i-1])){
                str.replace(i,s32.length(),s33);
            }
        }
    //    cout<<"str换后:"+str<<"---------"<<endl; 
        // can you 换成 I can          string s1="can you",s11="I can";
        for(int i=0;i<str.length();++i){
            i=str.find(s1,i);
            if(i==-1) break;
            if(!(isletter(str[i-1])||isletter(str[i+s1.length()])))
                str.replace(i,s1.length(),s11); 
        }
        // could you 换成 I could          string s2="could you",s22="I could";
        for(int i=0;i<str.length();++i){
            i=str.find(s2,i);
            if(i==-1) break;
            if(!(isletter(str[i-1])||isletter(str[i+s2.length()])))
                str.replace(i,s2.length(),s22);
        }
        cout<<"AI:"+str+"\n";
    }
}

    很显然，没有通过所有测试点。 仔细思考，发现错误样例：

1
can me

正确输出应为 ：

can you

而以上程序会输出 I can ，这说明此程序在输入can me时，先将can me变成了can you，此时can you恰好是关键字，此时can you便会再次被替换成I can。由此输出了错误答案。

初级思路bug的解决：

由此分析，不难想到解决方案：

    I、给字符串增加标记数组，当原字符串的某部分被替换过后，便用标记数组来记录此位置，此后需要替换此位置时先检查此位置是否曾被替换过，若为否，再进行替换。

    II、在替换时，不将 I、me 替换成you（因为这样会导致连续替换同一位置导致错误输出）。而是将 I、me 替换成yoU，这样一来就解决了替换过后会再次替换成I can的问题。最后在输出前再将所有的U转换成u即可。

    本人比较赞成第二种解决方案。下面给出写法。

#include<bits/stdc++.h>
using namespace std;
    string str; 
string s1="can you",s11="I can";
string s2="could you",s22="I could";
string s31="I",s32="me",s33="yoU";

//isletter函数用来判断当前字符是否为字母，1代表为字母 
int isletter(char ch){
    if(ch>='A'&&ch<='Z'||ch>='a'&&ch<='z') return 1;
    return 0;
}
int main(){ 
    int N;cin>>N;getchar();
    for(int i=0;i<N;++i){
        getline(cin,str); 
        cout<<str<<endl;
        str=" "+str;
        //大写转小写 并格式化语句 
        for(int i=0;i<str.length();++i){
            if(str[i]==' '&&!isletter(str[i+1])&&!isdigit(str[i+1])){
                 str.erase(i,1);
                 i--;
            }
            if(str[i]>='A'&&str[i]<='Z'&&str[i]!='I') str[i]+=32;
            if(str[i]=='?'){
                 str[i]='!';
            }
        }
        //独立的 I 换成 you     string s31="I",s32="me",s33="you";
        for(int i=0;i<str.length();++i){
            i=str.find(s31,i);
            if(i==-1) break;
            if(!(isletter(str[i-1])||isletter(str[i+s31.length()]))){
                str.replace(i,s31.length(),s33);
            }
        }
    //    cout<<"str换前:"+str<<"---------"<<endl; 
        //独立的 me 换成 you     string s31="I",s32="me",s33="you";
        for(int i=0;i<str.length();++i){
            i=str.find(s32,i);
            if(i==-1) break;
            if(!(isletter(str[i-1])||isletter(str[i+s32.length()]))){
                str.replace(i,s32.length(),s33);
            }
        }
    //    cout<<"str换后:"+str<<"---------"<<endl; 
        // can you 换成 I can          string s1="can you",s11="I can";
        for(int i=0;i<str.length();++i){
            i=str.find(s1,i);
            if(i==-1) break;
            if(!(isletter(str[i-1])||isletter(str[i+s1.length()]))){
                str.replace(i,s1.length(),s11); 
            }
        }
        // could you 换成 I could          string s2="could you",s22="I could";
        for(int i=0;i<str.length();++i){
            i=str.find(s2,i);
            if(i==-1) break;
            if(!(isletter(str[i-1])||isletter(str[i+s2.length()]))){
                str.replace(i,s2.length(),s22);
            }
        }
        for(int i=0;i<str.length();++i){
            if(str[i]=='U') str[i]='u';
        }
        if(str[0]!=' ') str=" "+str; 
        cout<<"AI:"+str+"\n";
    }
}

经过以上修改，此时AC了。

此题小结：

    当遇到会连续反复替换的情况，不一定设置标记数组才可以解决bug。尝试使用假串来替换也是个不错的选择。

    此外，特别感谢 http://t.csdnimg.cn/9My72 这篇博客给我的启发。这篇博客讲述了很不错的找出错误样例的方法，还提及到了本题的所有测试点，让我学到了很多东西。

初级小白（在校生）整理以用作学习，若有错误，还望指正，共勉！

初次书写，若存在侵权或其他问题，定立即改正，还望海涵。