UVa 723 Comment Removal

题目描述给定一个语法正确的Pascal\texttt{Pascal}Pascal源程序要求按照指定的顺序对其进行压缩处理。压缩规则共三条必须严格按顺序执行1.\texttt{1.}1.将字符串常量之外的所有连续空格替换为单个空格。字符串常量由单引号界定且至少包含一个字符。字符串内的两个连续单引号表示一个单引号字符本身不应视为字符串结束。2.\texttt{2.}2.删除所有注释。注释有两种形式以(*开始、*)结束或以{开始、}结束。删除时连同注释标记一并移除。3.\texttt{3.}3.删除所有完全空白的行即删去注释后该行仅由空格和换行符组成。输入保证语法正确不包含制表符或其他不可打印字符。输入格式输入文件包含一个任意的、语法正确的Pascal\texttt{Pascal}Pascal源程序可能包含多行。输出格式输出压缩后的Pascal\texttt{Pascal}Pascal源程序结果应仍为语法有效的Pascal\texttt{Pascal}Pascal程序但风格可能更为紧凑。样例输入Program Test (input, output); { this is a great program } Var X, Y : integer ; begin readln (X, Y); writeln (X, This is Y , Y, Hi!) ; end.输出Program Test (input, output); Var X, Y : integer ; begin readln (X, Y); writeln (X, This is Y , Y, Hi!) ; end.题目分析本题属于文本处理与词法分析类问题。核心挑战在于正确区分程序代码与字符串常量、注释因为注释标记和引号在字符串内不应被识别为语法符号而字符串内的连续单引号需要作为转义处理。三条规则具有严格的先后顺序必须在实现中保持该顺序。规则顺序的影响规则1\texttt{1}1压缩空格在规则2\texttt{2}2删除注释之前执行。这意味着注释内部的连续空格也会先被压缩但注释最终会被删除因此该顺序对最终结果几乎没有影响因为注释被删除了。然而若注释与代码相邻压缩空格可能会影响相邻代码间的空格数量。但删除注释后这些空格可能被重新组合因此必须按顺序模拟。规则3\texttt{3}3删除空行在最后执行此时注释已全部移除仅根据压缩后的内容判断行是否为空。词法状态机由于注释和空格压缩都必须忽略字符串常量内部的内容我们需要一个状态机来区分当前是否处于字符串常量内部。Pascal\texttt{Pascal}Pascal的字符串常量由单引号界定且使用表示转义的单引号字符因此状态机在遇到时需要检查下一个字符是否也是若是则输出一个单引号并跳过两个字符否则切换字符串状态。字符流处理输入可能跨多行注释也可能跨行。因此不能简单地按行处理而应将整个输入读入一个字符串保留换行符然后统一处理。最终输出时再根据换行符拆分并删除空行。解题思路整个处理流程分为三个独立的阶段每个阶段均需区分字符串内外压缩空格遍历整个输入字符串。在字符串外遇到空格时仅输出一个空格然后跳过后续所有连续空格在字符串内原样保留所有字符包括空格并正确处理转义单引号。删除注释再次遍历。在字符串外检测到(*或{时直接跳过直到匹配的*)或}在字符串内原样保留同时正确处理转义单引号。删除空行将上一步的结果按换行符分割检查每行是否只包含空格。若否则保留该行否则丢弃。最后将保留下来的行重新拼接末尾补一个换行符。三个阶段均使用相同的字符串状态识别逻辑因此可以复用同一个处理函数或编写独立的函数。由于规则顺序固定主流程依次调用这三个函数即可。关键细节单引号转义当遇到且当前在字符串内时若下一个字符也是则输出两个并将指针后移两位表示一个转义的单引号字符不改变字符串状态否则该为字符串结束符切换状态。注释嵌套Pascal\texttt{Pascal}Pascal不允许注释嵌套因此只需找到最近的结束标记即可无需栈结构。连续空格压缩在字符串外连续空格输出一个后指针直接跳到下一个非空格字符。复杂度分析设输入总字符数为NNN包括换行符。压缩空格单次遍历O(N)O(N)O(N)。删除注释单次遍历O(N)O(N)O(N)。删除空行分割与检查O(N)O(N)O(N)。总时间复杂度O(N)O(N)O(N)空间复杂度O(N)O(N)O(N)。代码实现// Comment Removal// UVa ID: 723// Verdict: Accepted// Submission Date: 2026-07-09// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 第一步压缩空格字符串常量内除外// 将非字符串区域内的连续空格替换为单个空格stringcompressSpaces(conststrings){string res;intn(int)s.size();boolinStringfalse;for(inti0;in;){if(!inString){if(s[i]\){inStringtrue;res.push_back(s[i]);i;}elseif(s[i] ){res.push_back( );while(ins[i] )i;}else{res.push_back(s[i]);i;}}else{res.push_back(s[i]);if(s[i]\){if(i1ns[i1]\){res.push_back(s[i1]);i2;}else{inStringfalse;i;}}elsei;}}returnres;}// 第二步删除注释(* *) 和 { }同样需要区分字符串常量stringremoveComments(conststrings){string res;intn(int)s.size();boolinStringfalse;for(inti0;in;){if(!inString){if(i1ns[i](s[i1]*){i2;while(i1n!(s[i]*s[i1])))i;if(i1n)i2;continue;}if(s[i]{){i;while(ins[i]!})i;if(in)i;continue;}if(s[i]\){inStringtrue;res.push_back(s[i]);i;}else{res.push_back(s[i]);i;}}else{res.push_back(s[i]);if(s[i]\){if(i1ns[i1]\){res.push_back(s[i1]);i2;}else{inStringfalse;i;}}elsei;}}returnres;}// 第三步删除完全空白的行仅包含空格和换行符的行stringremoveBlankLines(conststrings){vectorstringlines;string line;istringstreamiss(s);while(getline(iss,line)){boolonlySpacestrue;for(charc:line){if(c! ){onlySpacesfalse;break;}}if(!onlySpaces)lines.push_back(line);}string result;for(size_t i0;ilines.size();i){resultlines[i];if(i1lines.size())result\n;}if(!lines.empty())result\n;returnresult;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string input,line;while(getline(cin,line)){inputline;input\n;}string step1compressSpaces(input);string step2removeComments(step1);string outputremoveBlankLines(step2);coutoutput;return0;}总结本题的关键在于正确实现词法状态机区分字符串内外的处理逻辑并严格按照规定的顺序执行三个压缩步骤。字符串内对转义的处理是容易出错的细节必须谨慎。三个步骤虽可合并为一个遍历以减少开销但分开实现更清晰、易于验证。本题也提醒我们在处理源代码或文本格式时务必遵循给定的语法规则尤其是转义字符和注释标记否则可能产生错误结果。该解法时间复杂度O(N)O(N)O(N)能够高效处理任意大小的输入。