题目分析题目要求判断给定的字符串是否符合Hedonian\texttt{Hedonian}Hedonian语言的语法规则。语法规则总结根据题目描述Hedonian\texttt{Hedonian}Hedonian语言的语法规则非常简洁合法字符集只有小写字母p到z以及大写字母N、C、D、E、I是合法字符。原子句子任何单个字符从p到z都是一个正确的句子。否定规则如果sss是一个正确的句子那么NsNsNs也是一个正确的句子。二元运算规则如果sss和ttt是正确的句子那么CstCstCst、DstDstDst、EstEstEst、IstIstIst也都是正确的句子。封闭性只有上述规则能够确定句子的正确性。关键理解注意到这些规则定义了一种前缀表达式Polish Notation\texttt{Polish Notation}Polish Notation的语法结构小写字母p~z是原子操作数叶子节点N是一元运算符作用于其后一个子表达式C、D、E、I是二元运算符作用于其后两个子表达式例如句子CpIsz的解析结构为C p (I s z)即先应用I于s和z再应用C于p和Isz的结果。解题思路方法选择判断一个字符串是否符合这种前缀语法常见的方法有递归下降解析从字符串开头递归地解析表达式栈模拟归约从字符串末尾向前扫描使用栈来归约子表达式自顶向下替换反复将符合模式的子串替换为标记本题的参考代码采用了第三种方法——**反复归约Reduction\texttt{Reduction}Reduction**策略。归约法的核心思想归约法的基本思路是将句子中的每个字符映射为符号原子句子p~z映射为SENTENCE类型运算符N、C、D、E、I映射为对应的类型编号不断寻找可以归约的模式将其替换为SENTENCE如果最终整个字符串被归约为一个SENTENCE则句子合法归约模式表代码中定义了一个5×45 \times 45×4的归约表T运算符模式左部模式中间模式右部归约结果CSENTENCECSENTENCESENTENCEDSENTENCEDSENTENCESENTENCEESENTENCEESENTENCESENTENCEISENTENCEISENTENCESENTENCENN-1SENTENCESENTENCESENTENCE表示已经归约好的子句NONE值为−1-1−1表示对应位置不存在因为N是一元运算符只有右操作数对于N模式匹配[N, SENTENCE]的相邻两个符号替换为一个SENTENCE对于二元运算符匹配[SENTENCE, 运算符, SENTENCE]的相邻三个符号替换为一个SENTENCE算法步骤初始化读取一行字符串调用translateToSymbol()将每个字符转换为对应的符号编号存入向量S中。归约循环设置标志replaced false遍历555种归约模式在S中查找匹配当前模式的子序列如果找到匹配删除相应的元素并在原位置插入归约结果SENTENCE设置replaced true继续扫描直到当前模式无法找到更多匹配完成所有555种模式的扫描后如果replaced false则退出循环判断结果循环结束后检查S的大小是否为111且唯一的元素是SENTENCE。若是则输出YES否则输出NO。算法正确性说明由于语法规则是封闭的任何合法句子都可以通过不断应用逆规则从复合句子归约为子句子最终归约为一个原子句子。反之如果某个字符串不合法则归约过程会在某个阶段卡住无法归约为单一符号。该归约过程类似于自底向上的语法分析每个归约步骤都对应语法规则的一条逆应用。时间复杂度每个归约步骤减少至少一个符号因此归约次数为O(n)O(n)O(n)其中nnn为字符串长度。每次查找匹配需要扫描向量总体时间复杂度为O(n2)O(n^2)O(n2)。考虑到每个句子最长256256256个字符该复杂度完全可以接受。代码实现// Simply Syntax// UVa ID: 271// Verdict: Accepted// Submission Date: 2016-05-10// UVa Run Time: 0.060s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 定义符号常量constintNONE-1;// 表示不存在用于一元运算符NconstintN0;// 运算符N的编号constintC1;// 运算符C的编号constintD2;// 运算符D的编号constintE3;// 运算符E的编号constintI4;// 运算符I的编号constintSENTENCE5;// 归约后的句子标记vectorintS;// 存储当前待归约的符号序列// 归约规则表// 每行对应一种归约模式[左部, 中间, 右部, 归约结果]// NONE 表示该位置不参与匹配intT[5][4]{{SENTENCE,C,SENTENCE,SENTENCE},// 模式SENTENCE C SENTENCE - SENTENCE{SENTENCE,D,SENTENCE,SENTENCE},// 模式SENTENCE D SENTENCE - SENTENCE{SENTENCE,E,SENTENCE,SENTENCE},// 模式SENTENCE E SENTENCE - SENTENCE{SENTENCE,I,SENTENCE,SENTENCE},// 模式SENTENCE I SENTENCE - SENTENCE{N,NONE,SENTENCE,SENTENCE}// 模式N SENTENCE - SENTENCE一元运算符};// 将输入的字符串转换为符号编号序列存入向量SvoidtranslateToSymbol(string line){S.clear();for(inti0;iline.length();i){if(line[i]N)S.push_back(N);elseif(line[i]C)S.push_back(C);elseif(line[i]D)S.push_back(D);elseif(line[i]E)S.push_back(E);elseif(line[i]I)S.push_back(I);else// 小写字母p~z属于原子句子S.push_back(SENTENCE);}}// 判断句子是否合法boolisSentence(string line){// 将字符串转换为符号序列translateToSymbol(line);while(true){boolreplacedfalse;// 依次尝试5种归约模式for(inti0;i5;i){// 扫描整个符号序列for(intj0;jS.size();){// 检查当前位置是否匹配模式的左部if((S[j]!T[i][0])||// 如果模式有中间符号不是NONE检查前一个位置(~T[i][1](!j||S[j-1]!T[i][1]))||// 如果模式有右部符号不是NONE检查后一个位置(~T[i][2](j(S.size()-1)||S[j1]!T[i][2]))){j;continue;}// 匹配成功进行归约操作// 如果存在中间符号删除它位置j-1j~T[i][1]?S.erase(S.begin()j-1)-S.begin():j;// 如果存在右部符号删除它位置j1注意j可能已改变j~T[i][2]?S.erase(S.begin()j1)-S.begin()-1:j;// 将当前位置替换为归约结果SENTENCES[j]T[i][3];replacedtrue;// 标记发生过归约}}// 如果这一轮没有发生任何归约说明无法继续归约了if(replacedfalse)break;}// 最终序列长度为1且该符号为SENTENCE时句子合法returnS.size()1S.front()SENTENCE;}intmain(intargc,char*argv[]){string line;while(getline(cin,line))cout(isSentence(line)?YES:NO)endl;return0;}总结本题利用反复归约的方法将复杂的语法判断问题转化为简单的模式匹配和替换问题。关键在于正确构建归约规则表并理解归约过程是语法规则的逆应用。该方法实现简洁对于本题的规模句子长度≤256\leq 256≤256运行效率足够高。