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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 存储整个程序的源代码string program;// 需要计数的运算符列表，按长度从长到短排列便于匹配string operators[13]={"<=",">=","<>",":=","@","^","+","-","*","/","=","<",">",};// 计算程序长度（单位数）intcount(){intcounter=0;// 统一转换为小写，便于后续匹配for(inti=0;i<program.length();i++)if(isalpha(program[i]))program[i]=tolower(program[i]);// 第一阶段：处理注释 {} 和字符串常量intindex=0;while(index<program.length()){// 处理注释if(program[index]=='{'){program[index++]=' ';while(index<program.length()){charcurrent=program[index];program[index]=' ';if(current=='}')break;index++;}}// 处理字符串常量elseif(program[index]=='\''){counter++;// 字符串常量作为一个 token 计数program[index++]=' ';while(index<program.length()){if(program[index]=='\''){// 两个连续单引号表示一个单引号字符，属于字符串内容if(program[index+1]=='\''){program[index]=' ';program[index+1]=' ';index+=2;}else{program[index]=' ';break;// 字符串结束}}elseprogram[index++]=' ';}}index++;}// 第二阶段：计数左括号和左方括号，右括号和右方括号忽略index=0;while(index<program.length()){if(program[index]=='('||program[index]=='['){counter++;program[index]=' ';}elseif(program[index]==')'||program[index]==']'){program[index]=' ';}index++;}// 第三阶段：在 BEGIN 之前收集标识符（变量名、类型名等）index=0;intlast=program.find("begin");if(last==program.npos)last=program.length();// 如果没有 begin，则扫描整个程序vector<string>variables;while(index<last){// 标识符：字母或下划线开头if(isalpha(program[index])||program[index]=='_'){string block;block+=program[index];counter++;// 每个标识符计数一次program[index++]=' ';while(index<last)if(isalpha(program[index])||isdigit(program[index])||program[index]=='_'){block+=program[index];program[index++]=' ';}elsebreak;variables.push_back(block);}index++;}// 第四阶段：在全文中查找这些标识符的每次出现并计数index=0;while(index<variables.size()){intnext=program.find(variables[index]);while(next!=program.npos){// 检查是否为独立单词（边界不是字母、数字、下划线）if(isalpha(program[next-1])==false&&isdigit(program[next-1])==false&&program[next-1]!='_'&&isalpha(program[next+variables[index].length()])==false&&isdigit(program[next+variables[index].length()])==false&&program[next+variables[index].length()]!='_'){counter++;for(inti=0;i<variables[index].length();i++)program[next+i]=' ';}next+=variables[index].length();next=program.find(variables[index],next);}index++;}// 第五阶段：处理数字常量index=0;while(index<program.length()){// 十六进制常量：以 $ 开头if(program[index]=='$'){counter++;program[index++]=' ';while(index<program.length()){charcurrent=program[index];if(isdigit(current)||(current>='a'&¤t<='f'))program[index++]=' ';elsebreak;}}// 十进制数字常量（整数、实数、科学计数法）elseif(isdigit(program[index])){counter++;program[index++]=' ';// 整数部分while(index<program.length())if(isdigit(program[index]))program[index++]=' ';elsebreak;// 小数部分（可选）if(index<program.length()&&program[index]=='.'){program[index++]=' ';while(index<program.length())if(isdigit(program[index]))program[index++]=' ';elsebreak;}// 指数部分（可选）if(index<program.length()&&program[index]=='e'){program[index++]=' ';if(program[index]=='+'||program[index]=='-')program[index++]=' ';while(index<program.length()&&isdigit(program[index]))program[index++]=' ';}}index++;}// 第六阶段：处理运算符for(inti=0;i<13;i++){intstart=0;intnext=program.find(operators[i],start);while(next!=program.npos){counter++;for(intj=0;j<operators[i].length();j++)program[next+j]=' ';start=next+operators[i].length();next=program.find(operators[i],start);}}// 第七阶段：处理剩余的标识符（如保留字）index=0;while(index<program.length()){if(isalpha(program[index])||program[index]=='_'){counter++;program[index++]=' ';while(index<program.length())if(isalpha(program[index])||isdigit(program[index])||program[index]=='_')program[index++]=' ';elsebreak;}index++;}returncounter;}// 输出结果voidoutput(string name){intunits=count();cout<<"Program by "<<name<<" contains "<<units<<" units.\n";}intmain(){string line;while(getline(cin,line)){string firstTwoColumns=line.substr(0,2);// 遇到 ~~ 表示程序结束，输出结果并清空if(firstTwoColumns=="~~"){output(line.substr(2));program.clear();}else{// 将每行代码拼接，用空格分隔保证 token 边界正确program+=line;program+=' ';}}return0;}