如何使用标准C拒绝无效数字时将罗马数字转换为int?

正确的罗马数字意味着什么可能会 有所不同 。 为了简单起见(没有Unicode,没有乘法原理,没有双减法,没有过量栏,没有大数字等),为了这个问题,有效的罗马数字由正则表达式定义:

^(M{0,3})(D?C{0,3}|CM|CD)(L?X{0,3}|XC|XL)(V?I{0,3}|IX|IV)$ 

使用POSIX regexec()代码示例 。 正则表达式匹配使用“严格”规则表示的1..3999范围内的罗马数字。

如果我们不需要拒绝无效数字,有许多解决方案可以转换罗马数字,例如:

 int roman_numeral_value(unsigned char c) { switch(toupper(c)) { case 'I': return 1; case 'V': return 5; case 'X': return 10; case 'L': return 50; case 'C': return 100; case 'D': return 500; case 'M': return 1000; default: return 0; // error } } int roman_numeral_to_int(const char *s, int size) { int total = 0, prev = 0; for (int i = size-1; i >= 0; --i) { // in reverse order int value = roman_numeral_value(s[i]); total += value < prev ? -value : value; // subtract if necessary prev = value; } return total; } 

它适用于有效的罗马数字 。 但是roman_numeral_to_int()接受正则表达式拒绝的数字,例如IIIII 。 是否有一个类似的简单跨平台解决方案,不需要pcre_exec()或其他外部依赖项,这些依赖项适用于有效的罗马数字, 适用于它们?

使用strcmp()或换句话说,往返字符串。

首先考虑反向问题,数字 – >字符串。

有许多方法可以有效地将整数转换为罗马数字串。 我们称之为:

 // return false on error due to `value` range error or scant `size` bool roman_int_to_string(char *dest, size_t size, int value); 

除了字母案例问题之外,规范罗马数字字符串和int之间存在一对一的关系。 只需将源字符串转换为int ,然后将int转换为另一个测试字符串。 如果这些字符串匹配,我们就有赢家。

 #define ROMAN_STRING_N 20 int roman_numeral_to_int_with_validate(const char *s, int size, bool *is_canonical) { int value = roman_numeral_to_int(s, size); char test[ROMAN_STRING_N]; *is_canonical = roman_int_to_string(test, sizeof test, value); if (*is_canonical) { if (strcmp(s, test)) { // Or use a case insensitive compare as desired *is_canonical = false; } } return value; } 

经验教训:我编写了一个直接validation函数。 为了测试它我需要反向roman_int_to_string() 。 随机字符串生成器迅速显示出许多令人惊讶的错误,如"CMC""CMCD"以及OP的"IIII" 。 最后,使用简单的string-to-int和int-to-string函数对然后进行字符串比较是最有弹性的。

罗马数字分为两类,“一”(I,X,C,M)和“五”(V,L,D)。 “五个”不能重复,不能减去。 当它们没有在较小的数字之后出现时,“1”可以重复多达三次,并且可以从不大于下一个“1”的数字中减去“1”。

解析时,数字可以有三种不同的模式:它可以正常添加,也可以是要减去的数字,也可以是减去前一个数字的数字。

您可以在构建号码时强制执行这些规则。 除了数字的值,您还需要一个对数字进行分类的函数。 在下面的代码中,函数repeat执行此操作。 它返回每个数字的最大重复次数,但它也用作分类:3表示“一”,1表示“五”。

下面的代码似乎产生与使用正则表达式validation的代码相同的结果。 它返回有效罗马数字的正数,否则返回-1。 (它的条件少于28个。)

 int digit(int c) { if (c == 'I') return 1; if (c == 'V') return 5; if (c == 'X') return 10; if (c == 'L') return 50; if (c == 'C') return 100; if (c == 'D') return 500; if (c == 'M') return 1000; return 0; } int repeat(int c) { if (c == 'I') return 3; if (c == 'V') return 1; if (c == 'X') return 3; if (c == 'L') return 1; if (c == 'C') return 3; if (c == 'D') return 1; if (c == 'M') return 3; return 0; } int from_roman(const char *s) { int res = 0; // running result int prev = 10000; // value of previous digit if (s == NULL || *s == '\0') return -1; while (*s) { int c = *s++; // Roman digit int count = 1; // count of consecutive numbers int value = digit(c); // digit value int max = repeat(c); // allowed repetitions if (value == 0) return -1; // illegal Roman digit while (*s == c) { s++; count++; } if (*s && digit(*s) > value) { int next = digit(*s++); if (max != 3) return -1; // can only subtract I, X, C if (count > 1) return -1; // can only subtract once if (next > 10 * value) return -1; // IM,ID, IC, IL etc. invalid if (value * 10 > prev) return -1; // VIV, VIX etc. invalid res += next - value; } else { if (count > max) return -1; // too many repetitions if (value >= prev) return -1; // must decrease res += count * value; } prev = value; } return res; } 

编辑 :我的代码的前两个草稿有错误,现在已修复。

由于正确性的validation是通过正则表达式完成的,另一种方法是直接实现正则表达式,同时计算罗马数字的值。 另外,考虑到将逻辑设置为罗马数字是多么复杂,这可能是更好的方法。

这种方法的实施可以是:

 /* * Returns the length of the digit stretch and advances the pointer */ static int stretch(const char **s, int m, int max) { int n = 0; while (n < max && **s == m) { (*s)++; n++; } return n; } /* * Parses (I II III IV V VI VII VIII IX) for ones, * tens and hundreds and advances the pointer. */ static int parse(const char **s, int x, int v, int i) { int res = 0; if (**s == i && *(*s + 1) == x) { res += 9; *s += 2; } else if (**s == i && *(*s + 1) == v) { res += 4; *s += 2; } else { res += stretch(s, v, 1) * 5; res += stretch(s, i, 3); } return res; } /* * Parse a Roman numeral according the the regex; -1 means failure */ int from_roman_regex(const char *s) { int res = 0; if (s == NULL || *s == '\0') return -1; res += stretch(&s, 'M', 3) * 1000; res += parse(&s, 'M', 'D', 'C') * 100; res += parse(&s, 'C', 'L', 'X') * 10; res += parse(&s, 'X', 'V', 'I') * 1; if (*s) return -1; return res; } 

stretch函数模拟正则表达式,例如X{0,3} ; parse函数模拟正则表达式,例如(V?I{0,3}|IX|IV) ,但除了单独匹配成功或失败之外,它还将其评估为罗马数字。

第一种方法试图实现罗马数字的规则。 这有点复杂,但有一个优点,即如果有人愿意,可以轻松扩展它以提供准确的错误消息。 第二种方法的优点是它完全匹配问题的规范:它完成了正则表达式所做的事情。

我测试了所有罗马数字高达3,999以及最多7个罗马数字的所有组合。 上述两种方法和OP的方法 - 简单的aritgmetic加上正则表达式validation - 对所有情况都产生了相同的结果。

通过从更高级别的规范生成C代码,我们可以获得仅使用标准C的可读解决方案。例如, 正则表达式 :

  ^(?P M{,3}) (?PCM|CD|D?C{,3}) (?P XC|XL|L?X{,3}) (?P IX|IV|V?I{,3})$ 

可以使用Ragel有限状态机编译器表示为FSM:

 thousands = ('M' %{ n += 1000; }){,3}; hundreds = "CM" %{ n += 900; } | "CD" %{ n += 400; } | ('D' %{ n += 500; } )? ('C' %{ n += 100; }){,3}; tens = "XC" %{ n += 90; } | "XL" %{ n += 40; } | ('L' %{ n += 50; } )? ('X' %{ n += 10; }){,3}; units = "IX" %{ n += 9; } | "IV" %{ n += 4; } | ('V' %{ n += 5; } )? ('I' %{ n += 1; }){,3}; numeral = thousands hundreds tens units; main := numeral > { n = 0; } ; 
  • 它是一个完整的规范:它转换所有有效的罗马数字。 它拒绝所有无效的东西
  • 它简洁明了:你可以把它放在卡片上
  • 它很简单:用零初始化n并添加数千,数百,数十和单位。 100s,10s,1s遵循一个简单的模式: nine | four | (five? ten{0,3}) nine | four | (five? ten{0,3}) nine | four | (five? ten{0,3})例如,十个部分是9040或可选50加上三个10秒。
  • 它是声明性的并且易于扩展而不会引入错误,例如,除了减去IV之外,为了支持四个连续数字,例如IIII ,用{,4}代替{,3}就足够了。 为了支持Unicode /大写/大写字母,相应的文字如'M'可以替换为M ,其中M = 'M' | 'm' | "Ⅿ" | "ⅿ"; M = 'M' | 'm' | "Ⅿ" | "ⅿ";
  • ragel将其转换为纯C中的快速表格或旋转驱动的FSM。

完整的代码示例(上面提到的Unicode和IIII扩展) 。 生成的roman_numerals.c没有第三方依赖项。

为了创建某种程度的规则灵活性,以下Roman_string_to_unsigned0()使用了一个表。

它遵循strtol()函数样式,返回一个结束指针,指示解析停止的位置。 取消参考并测试'\0'是否成功。

该函数有一个bool subtractive参数来引导两种主要类型的罗马数字解析: 基本 , 减法 。

 static const struct Roman_digit { char ch[3]; bool subtractive; unsigned char limit; unsigned char nextdown; // with parse success, offset to next element to try unsigned value; } Roman_table[] = { { "I", false, 4, 1, 1 }, // { "IV", true, 1, 2, 4 }, // { "V", false, 1, 2, 5 }, // { "IX", true, 1, 4, 9 }, // { "X", false, 4, 1, 10 }, // { "XL", true, 1, 2, 40 }, // { "L", false, 1, 2, 50 }, // { "XC", true, 1, 4, 90 }, // { "C", false, 4, 1, 100 }, // { "CD", true, 1, 2, 400 }, // { "D", false, 1, 2, 500 }, // { "CM", true, 1, 4, 900 }, // { "M", false, 4, 1, 1000 }, // }; #define Roman_table_N (sizeof Roman_table / sizeof Roman_table[0]) const char *Roman_string_to_unsigned0(unsigned *dest, const char *src, bool subtractive){ *dest = 0; for (unsigned i = Roman_table_N; i > 0;) { const struct Roman_digit *digit = &Roman_table[i - 1]; if (!subtractive && digit->subtractive) { i--; continue; } unsigned limit = digit->limit; // repeat count if (limit > 1 && subtractive) limit--; size_t ch_length = strlen(digit->ch); size_t next_i = i-1; for (unsigned j=0; jch, ch_length) == 0) { *dest += digit->value; if (*dest < digit->value) { // Overflow detection return (char*) src; } src += ch_length; next_i = i - digit->nextdown; // With success, maybe skip down the list } else { break; } } i = next_i; } return (char*) src; } 

注意:尚未编码的不区分大小写。 空字符串返回0.通过此代码工作最重要, "XXXMMM"不通过。

简单和甜的逻辑使用减去值

对不起的代码是在python中,但你可以按照我已经使用的逻辑完成这个程序**

 def checkio(data): roman="" while(data!=0): if data>=1000: data-=1000 roman+='M' elif data>=900: data-=900 roman+='CM' elif data>=500: data-=500 roman+='D' elif data>=400: data-=400 roman+='CD' elif data>=100: data-=100 roman+='C' elif data>=90: data-=90 roman+='XC' elif data>=50: data-=50 roman+='L' elif data>=40: data-=40 roman+='XL' elif data>=10: data-=10 roman+='X' elif data>=9: data-=9 roman+='IX' elif data>=5: data-=5 roman+='V' elif data>=4: data-=4 roman+='IV' elif data>=1: data-=1 roman+='I' return roman