UVa 189 Pascal Program Lengths

题目分析本题要求计算Turbo Pascal\texttt{Turbo Pascal}Turbo Pascal程序的长度长度由若干类token\texttt{token}token的数量决定包括保留字reserved words\texttt{reserved words}reserved words标识符identifiers\texttt{identifiers}identifiers常量constants\texttt{constants}constants左括号(和左方括号[运算符、-、*、/、、、、、、、、^、:需要特别注意的是注释使用{}界定不嵌套注释内容完全忽略。字符串常量使用单引号界定字符串中的表示一个单引号字符。数字常量包括整数、实数、科学计数法形式以及十六进制常量以$开头。标识符以字母或下划线_开头后跟字母、数字或下划线。子范围lower..upper形式中的..不是单独 token而是两个.字符但.不在计数范围内。和-尽可能视为运算符例如x : -3中的-是运算符。解题思路本题的核心是对Pascal\texttt{Pascal}Pascal源代码进行一次扫描识别出所有需要计数的token\texttt{token}token同时忽略注释、字符串内容等其他字符。一种可行的策略是多阶段扫描预处理将全部代码合并为一个字符串并转换为小写便于后续匹配保留字和标识符。移除注释扫描字符串将{到}之间的内容替换为空格。处理字符串常量扫描字符串将到之间的内容替换为空格同时注意转义。遇到字符串常量时需要为字符串本身计数111次字符串常量属于常量的一种。计数括号和方括号扫描字符串遇到(或[则计数器加111将这些字符替换为空格。计数标识符和保留字在begin之前的部分扫描标识符因为变量声明只出现在begin之前记录去重后的标识符列表然后在全文中计数这些标识符的每次出现。计数数字常量扫描字符串识别十六进制、整数、实数、科学计数法形式的数字常量每次识别一个常量则计数器加111。计数运算符依次匹配题目中给出的所有运算符每次匹配成功则计数器加111。处理剩余标识符扫描剩余字符串识别可能遗漏的标识符例如保留字并计数。最终输出格式为Program by 姓名 contains 数量 units.代码实现// Pascal Program Lengths// UVa ID: 189// Verdict: Accepted// Submission Date: 2016-04-05// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 存储整个程序的源代码string program;// 需要计数的运算符列表按长度从长到短排列便于匹配string operators[13]{,,,:,,^,,-,*,/,,,,};// 计算程序长度单位数intcount(){intcounter0;// 统一转换为小写便于后续匹配for(inti0;iprogram.length();i)if(isalpha(program[i]))program[i]tolower(program[i]);// 第一阶段处理注释 {} 和字符串常量intindex0;while(indexprogram.length()){// 处理注释if(program[index]{){program[index] ;while(indexprogram.length()){charcurrentprogram[index];program[index] ;if(current})break;index;}}// 处理字符串常量elseif(program[index]\){counter;// 字符串常量作为一个 token 计数program[index] ;while(indexprogram.length()){if(program[index]\){// 两个连续单引号表示一个单引号字符属于字符串内容if(program[index1]\){program[index] ;program[index1] ;index2;}else{program[index] ;break;// 字符串结束}}elseprogram[index] ;}}index;}// 第二阶段计数左括号和左方括号右括号和右方括号忽略index0;while(indexprogram.length()){if(program[index](||program[index][){counter;program[index] ;}elseif(program[index])||program[index]]){program[index] ;}index;}// 第三阶段在 BEGIN 之前收集标识符变量名、类型名等index0;intlastprogram.find(begin);if(lastprogram.npos)lastprogram.length();// 如果没有 begin则扫描整个程序vectorstringvariables;while(indexlast){// 标识符字母或下划线开头if(isalpha(program[index])||program[index]_){string block;blockprogram[index];counter;// 每个标识符计数一次program[index] ;while(indexlast)if(isalpha(program[index])||isdigit(program[index])||program[index]_){blockprogram[index];program[index] ;}elsebreak;variables.push_back(block);}index;}// 第四阶段在全文中查找这些标识符的每次出现并计数index0;while(indexvariables.size()){intnextprogram.find(variables[index]);while(next!program.npos){// 检查是否为独立单词边界不是字母、数字、下划线if(isalpha(program[next-1])falseisdigit(program[next-1])falseprogram[next-1]!_isalpha(program[nextvariables[index].length()])falseisdigit(program[nextvariables[index].length()])falseprogram[nextvariables[index].length()]!_){counter;for(inti0;ivariables[index].length();i)program[nexti] ;}nextvariables[index].length();nextprogram.find(variables[index],next);}index;}// 第五阶段处理数字常量index0;while(indexprogram.length()){// 十六进制常量以 $ 开头if(program[index]$){counter;program[index] ;while(indexprogram.length()){charcurrentprogram[index];if(isdigit(current)||(currentacurrentf))program[index] ;elsebreak;}}// 十进制数字常量整数、实数、科学计数法elseif(isdigit(program[index])){counter;program[index] ;// 整数部分while(indexprogram.length())if(isdigit(program[index]))program[index] ;elsebreak;// 小数部分可选if(indexprogram.length()program[index].){program[index] ;while(indexprogram.length())if(isdigit(program[index]))program[index] ;elsebreak;}// 指数部分可选if(indexprogram.length()program[index]e){program[index] ;if(program[index]||program[index]-)program[index] ;while(indexprogram.length()isdigit(program[index]))program[index] ;}}index;}// 第六阶段处理运算符for(inti0;i13;i){intstart0;intnextprogram.find(operators[i],start);while(next!program.npos){counter;for(intj0;joperators[i].length();j)program[nextj] ;startnextoperators[i].length();nextprogram.find(operators[i],start);}}// 第七阶段处理剩余的标识符如保留字index0;while(indexprogram.length()){if(isalpha(program[index])||program[index]_){counter;program[index] ;while(indexprogram.length())if(isalpha(program[index])||isdigit(program[index])||program[index]_)program[index] ;elsebreak;}index;}returncounter;}// 输出结果voidoutput(string name){intunitscount();coutProgram by name contains units units.\n;}intmain(){string line;while(getline(cin,line)){string firstTwoColumnsline.substr(0,2);// 遇到 ~~ 表示程序结束输出结果并清空if(firstTwoColumns~~){output(line.substr(2));program.clear();}else{// 将每行代码拼接用空格分隔保证 token 边界正确programline;program ;}}return0;}