UVa 464 Sentence/Phrase Generator

题目描述题目要求根据给定的上下文无关文法CFG\texttt{CFG}CFG生成英文短语或句子。文法规则如下::表示“定义为”|表示“或”sentence :: trans-sentence | intrans-sentence trans-sentence :: subject verb-phrase object prep-phrase intrans-sentence :: subject intrans-verb-phrase prep-phrase subject :: noun-phrase object :: noun-phrase noun-phrase :: article modified-noun modified-noun :: noun | modifier noun modifier :: adjective | adverb adjective verb-phrase :: trans-verb | adverb trans-verb intrans-verb-phrase :: intrans-verb | adverb intrans-verb prep-phrase :: preposition noun-phrase | empty noun :: man | dog | fish | computer | waves trans-verb :: struck | saw | bit | took intrans-verb :: slept | jumped | walked | swam article :: the | a adjective :: green | small | rabid | quick adverb :: nearly | suddenly | restlessly preposition :: on | over | through empty :: 程序按顺序读入多个请求每个请求是一个短语名如sentence、noun等。对于每个请求按文法规则生成一个短语并输出。当遇到有多种规则可选时按以下方式选择设这是程序开始运行以来遇到的第kkk个选择该短语有nnn种规则按文法中出现的顺序编号111到nnn则选择规则编号(k mod n)1(k \bmod n) 1(kmodn)1。输入格式输入包含若干行每行一个短语名如sentence、noun等没有括号。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个请求输出一行生成的短语单词之间用单个空格分隔。样例输入sentence noun sentence输出the small dog restlessly jumped through the quick dog fish a dog took the quick computer题目分析本题的核心是模拟一个带随机选择的上下文无关文法的生成过程。由于文法规模较小可以直接使用递归展开。数据结构使用一个映射phrases\textit{phrases}phrases键为短语名加上#前缀以区分终结符值为一个向量每个元素是一个规则即一个字符串向量表示该规则中的各组成部分。例如#sentence对应两条规则[[#trans-sentence], [#intrans-sentence]]#noun对应[[man], [dog], [fish], [computer], [waves]]生成过程函数generate(phrase)\texttt{generate(phrase)}generate(phrase)如果phrase\textit{phrase}phrase以#开头非终结符获取该短语的规则列表规则数为nnn。若n1n 1n1根据当前选择计数器kkk计算规则索引index(k mod n)\textit{index} (k \bmod n)index(kmodn)然后kkk加111。递归展开所选规则中的每个组成部分。否则终结符输出该单词注意空格分隔第一个单词前不加空格。选择计数器全局变量kkk从111开始每遇到一个多选规则n1n 1n1时kkk递增。规则索引从000开始计算indexk%n\textit{index} k \% nindexk%n当kkk从111开始时需要调整。参考代码中indexChoosed k % choiceskkk从111开始1 % n得到111但规则编号从000开始注意实际使用中k初始为111每次多选时先取模再k。由于规则列表索引从000开始而规则编号从111开始因此(k mod n)(k \bmod n)(kmodn)正好对应111到n−1n-1n−1和000的循环即(k % n)为000时选择第nnn条规则索引n−1n-1n−1。这与题目要求一致。空短语处理empty规则生成空字符串输出时不应输出任何内容也不应添加空格。复杂度分析每次请求的生成时间与生成的短语长度成正比短语长度有限完全可接受。代码实现// Sentence/Phrase Generator// UVa ID: 464// Verdict: Accepted// Submission Date: 2016-08-04// UVa Run Time: 0.050s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intk1;boolprintSpacefalse;mapstring,vectorvectorstringphrases{{#sentence,{{#trans-sentence},{#intrans-sentence}}},{#trans-sentence,{{#subject,#verb-phrase,#object,#prep-phrase}}},{#intrans-sentence,{{#subject,#intrans-verb-phrase,#prep-phrase}}},{#subject,{{#noun-phrase}}},{#object,{{#noun-phrase}}},{#noun-phrase,{{#article,#modified-noun}}},{#modified-noun,{{#noun},{#modifier,#noun}}},{#modifier,{{#adjective},{#adverb,#adjective}}},{#verb-phrase,{{#trans-verb},{#adverb,#trans-verb}}},{#intrans-verb-phrase,{{#intrans-verb},{#adverb,#intrans-verb}}},{#prep-phrase,{{#preposition,#noun-phrase},{#empty}}},{#noun,{{man},{dog},{fish},{computer},{waves}}},{#trans-verb,{{struck},{saw},{bit},{took}}},{#intrans-verb,{{slept},{jumped},{walked},{swam}}},{#article,{{the},{a}}},{#adjective,{{green},{small},{rabid},{quick}}},{#adverb,{{nearly},{suddenly},{restlessly}}},{#preposition,{{on},{over},{through}}},{#empty,{{}}}};voidgenerate(string phrase){if(phrase.length()0phrase.front()#){intchoicesphrases[phrase].size();intindexChoosed0;if(choices1){indexChoosedk%choices;k;}for(autop:phrases[phrase][indexChoosed])generate(p);}else{if(printSpacefalse)printSpacetrue;elseif(phrase.length()0)cout ;coutphrase;}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line)){while(line.length()0isblank(line.front()))line.erase(line.begin());while(line.length()0isblank(line.back()))line.erase(line.end()-1);printSpacefalse;generate(#line);cout\n;}return0;}