UVa 759 The Return of the Roman Empire

题目描述编写一个程序接受罗马数字并将其转换为十进制形式。罗马数字由七个基本符号组成I111、V555、X101010、L505050、C100100100、D500500500、M100010001000。此外存在六个减性组合IV444、IX999、XL404040、XC909090、CD400400400、CM900900900。程序需验证输入是否为合法罗马数字若合法则输出对应的十进制整数否则输出This is not a valid number。输入格式输入包含若干行每行一个字符串表示一个罗马数字。输入直至文件结束。输出格式对于每行输入若为合法罗马数字输出其对应的十进制数值整数否则输出This is not a valid number。样例输入MCMXCVIII CCM样例输出1998 This is not a valid number题目分析罗马数字的合法形式遵循特定的句法规则千位MMM最多333个百位CCC、CDCDCD、DDD、CMCMCM按规则组合十位XXX、XLXLXL、LLL、XCXCXC同理个位III、IVIVIV、VVV、IXIXIX同理。任何不符合该正则表达式的字符串均无效。有效的罗马数字可通过从左到右扫描利用减法原则计算数值若当前符号值小于下一个符号值则当前值为负否则为正累加即可。解题思路实现方法分为两步步骤1\texttt{1}1. 使用正则表达式验证输入字符串的合法性。标准罗马数字的正则表达式为^M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$该表达式精确匹配所有合法的罗马数字数值范围111到399939993999。若匹配失败则输出错误信息。步骤2\texttt{2}2. 对于合法字符串进行数值转换。遍历字符串对于每个字符ccc若ccc的数值小于其后继字符的数值则从总和中减去ccc的数值否则加上ccc的数值。最后的总和即为对应的十进制数。代码中还包含从十进制转换回罗马数字的函数但本题仅需正向转换。输入可能包含空行处理时直接输出000或视为无效但题目未明确可按代码处理。代码实现// The Return of the Roman Empire// UVa ID: 759// Verdict: Accepted// Submission Date: 2017-06-11// UVa Run Time: 0.040s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;mapchar,intletters{{I,1},{V,5},{X,10},{L,50},{C,100},{D,500},{M,1000},};vectorintnumbers{3000,2000,1000,900,500,400,300,200,100,90,50,40,30,20,10,9,8,7,6,5,4,3,2,1};vectorstringsymbols{MMM,MM,M,CM,D,CD,CCC,CC,C,XC,L,XL,XXX,XX,X,IX,VIII,VII,VI,V,IV,III,II,I};string patternR(^M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$);regexromanExp(pattern,regex_constants::ECMAScript);introman2Arab(stringroman){intarab0,idx0;while(idxroman.length()-1){intpreviousletters[roman[idx]],nextletters[roman[idx1]];if(previousnext)arabnext-previous,idx2;elsearabprevious,idx1;}if(idxroman.length())arabletters[roman[idx]];returnarab;}stringarab2Roman(intarab){string roman;while(arab0){for(inti0;inumbers.size();i)if(arabnumbers[i]){romansymbols[i];arab-numbers[i];break;}}returnroman;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string line;while(getline(cin,line)){if(line.length()0)cout0\n;elseif(regex_match(line,romanExp))coutroman2Arab(line)\n;elsecoutThis is not a valid number\n;}return0;}总结本题通过正则表达式验证罗马数字合法性并利用减法原则进行数值转换。正则表达式精确覆盖了标准罗马数字的句法结构避免了复杂的逻辑判断。转换过程简单高效。注意输入可能包含空行代码中将其视为000但题目未明确可根据需要调整。该解法体现了正则表达式在文本验证中的强大能力同时巩固了罗马数字的数值规则。