如何在使用标准 C 拒绝无效数字的同时将罗马数字转换为 int？
How to convert Roman numerals to int while rejecting invalid numbers using standard C?
什么是正确的Roman numerals may vary. For simplicity (no Unicode, no multiplicative principle, no double subtractives, no overbars, no large numbers, etc) for the sake of this question, valid Roman numerals are defined by the regex：
^(M{0,3})(D?C{0,3}|CM|CD)(L?X{0,3}|XC|XL)(V?I{0,3}|IX|IV)$
Code example with POSIX regexec()。正则表达式匹配使用 "strict" 规则表示的 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;
}
It works for valid Roman numerals. But roman_numeral_to_int() accepts numerals such as IIIII that are rejected by the regex. Is there a similarly simple cross-platform solution that doesn't require pcre_exec() 或其他适用于有效罗马数字且 仅 的外部依赖项？
通过从更高级别的规范生成 C 代码，我们可以得到
仅使用标准 C 的可读解决方案。例如，the regex:
^(?P<thousands> M{,3})
(?P<hundreds>CM|CD|D?C{,3})
(?P<tens> XC|XL|L?X{,3})
(?P<units> IX|IV|V?I{,3})$
可以表示为FSM
使用
Ragel finite-state machine compiler:
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}) 例如，十位部分是 90 或 40 或可选的 50 加上最多三个 10s。
- 它是声明式的并且易于扩展而不会引入错误例如，除了减法
IV 之外还支持 IIII 等四个连续数字，将 {,3} 替换为{,4}。为了支持 Unicode/lower/upper 大小写字母，相应的文字如 'M' 可以替换为 M 其中 M = 'M' | 'm' | "Ⅿ" | "ⅿ";
- ragel 将其转换为纯 C 中的快速 table- 或 goto 驱动的 FSM。
Complete code example (with Unicode and IIII extensions mentioned above)。生成的roman_numerals.c没有第三方依赖。
罗马数字有两个 类，"ones"（I、X、C、M）和 "fives"（V、L、D）。 "fives" 不能重复也不能减去。 "ones" 最多可以重复 3 次，如果它们不在较小的数字之后，并且可以从不大于下一个 "one".
的数字中减去
解析时，一个数字可以有三种不同的模式：要么是正常添加，要么是要减去的数字，要么是前面的数字被减去的数字。
您可以在建立号码时强制执行这些规则。除了数字的值之外，您还需要一个对数字进行分类的函数。在下面的代码中，函数 repeat 执行此操作。它 returns 每个数字的最大重复次数，但它也用作分类：3 表示 "one" 和 1 表示 "five."
下面的代码产生的结果似乎与您使用正则表达式验证的代码产生的结果相同。它 returns 有效罗马数字的正数，否则为 -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 == '[=10=]') 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;
}
编辑：我的代码的前两稿有错误，现在已修复。
由于正确性的验证是通过正则表达式完成的，另一种方法是直接实现正则表达式，同时计算罗马数字的值。此外，考虑到正确理解罗马数字的逻辑是多么复杂，这可能是更好的方法。
此方法的实现可以是：
/*
* 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 == '[=11=]') 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 的方法——简单算术加正则表达式验证——在所有情况下都产生了相同的结果。
Simple and Sweet logic using subtract the value
ng 抱歉，代码在 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
使用 strcmp() 或者换句话说，往返字符串。
先考虑逆向问题，number --> string.
有很多方法可以有效地将整数转换为罗马数字字符串。让我们称它为：
// 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;
}
课程：我编写了一个直接验证函数。为了测试它，我需要反转 roman_int_to_string()。随机字符串生成器迅速显示出许多令人惊讶的错误，例如 "CMC" 和 "CMCD" 以及 OP 的 "IIII"。最后，使用简单的字符串到整数和整数到字符串函数对，然后进行字符串比较是最有弹性的。
为了创建一定程度的规则灵活性，以下 Roman_string_to_unsigned0() 采用 table。
它遵循 strtol() 风格的功能，返回一个结束指针，指示解析停止的位置。取消引用并针对 '[=13=]' 进行测试以取得成功。
该函数有一个 bool subtractive 参数来控制两种主要类型的罗马数字解析：basic, 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; j<limit; j++) {
if (strncmp(src, digit->ch, 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;
}
注意：不区分大小写尚未编码。空字符串 returns 0。通过此代码从高到低有效，"XXXMMM" 未通过。
什么是正确的Roman numerals may vary. For simplicity (no Unicode, no multiplicative principle, no double subtractives, no overbars, no large numbers, etc) for the sake of this question, valid Roman numerals are defined by the regex：
^(M{0,3})(D?C{0,3}|CM|CD)(L?X{0,3}|XC|XL)(V?I{0,3}|IX|IV)$
Code example with POSIX regexec()。正则表达式匹配使用 "strict" 规则表示的 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;
}
It works for valid Roman numerals. But roman_numeral_to_int() accepts numerals such as IIIII that are rejected by the regex. Is there a similarly simple cross-platform solution that doesn't require pcre_exec() 或其他适用于有效罗马数字且 仅 的外部依赖项？
通过从更高级别的规范生成 C 代码，我们可以得到 仅使用标准 C 的可读解决方案。例如，the regex:
^(?P<thousands> M{,3})
(?P<hundreds>CM|CD|D?C{,3})
(?P<tens> XC|XL|L?X{,3})
(?P<units> IX|IV|V?I{,3})$
可以表示为FSM 使用 Ragel finite-state machine compiler:
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})例如，十位部分是90或40或可选的50加上最多三个10s。 - 它是声明式的并且易于扩展而不会引入错误例如，除了减法
IV之外还支持IIII等四个连续数字，将{,3}替换为{,4}。为了支持 Unicode/lower/upper 大小写字母，相应的文字如'M'可以替换为M其中M = 'M' | 'm' | "Ⅿ" | "ⅿ"; - ragel 将其转换为纯 C 中的快速 table- 或 goto 驱动的 FSM。
Complete code example (with Unicode and IIII extensions mentioned above)。生成的roman_numerals.c没有第三方依赖。
罗马数字有两个 类，"ones"（I、X、C、M）和 "fives"（V、L、D）。 "fives" 不能重复也不能减去。 "ones" 最多可以重复 3 次，如果它们不在较小的数字之后，并且可以从不大于下一个 "one".
的数字中减去解析时，一个数字可以有三种不同的模式：要么是正常添加，要么是要减去的数字，要么是前面的数字被减去的数字。
您可以在建立号码时强制执行这些规则。除了数字的值之外，您还需要一个对数字进行分类的函数。在下面的代码中，函数 repeat 执行此操作。它 returns 每个数字的最大重复次数，但它也用作分类：3 表示 "one" 和 1 表示 "five."
下面的代码产生的结果似乎与您使用正则表达式验证的代码产生的结果相同。它 returns 有效罗马数字的正数，否则为 -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 == '[=10=]') 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;
}
编辑：我的代码的前两稿有错误，现在已修复。
由于正确性的验证是通过正则表达式完成的，另一种方法是直接实现正则表达式，同时计算罗马数字的值。此外，考虑到正确理解罗马数字的逻辑是多么复杂，这可能是更好的方法。
此方法的实现可以是：
/*
* 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 == '[=11=]') 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 的方法——简单算术加正则表达式验证——在所有情况下都产生了相同的结果。
Simple and Sweet logic using subtract the value
ng 抱歉，代码在 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
使用 strcmp() 或者换句话说，往返字符串。
先考虑逆向问题，number --> string.
有很多方法可以有效地将整数转换为罗马数字字符串。让我们称它为：
// 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;
}
课程：我编写了一个直接验证函数。为了测试它，我需要反转 roman_int_to_string()。随机字符串生成器迅速显示出许多令人惊讶的错误，例如 "CMC" 和 "CMCD" 以及 OP 的 "IIII"。最后，使用简单的字符串到整数和整数到字符串函数对，然后进行字符串比较是最有弹性的。
为了创建一定程度的规则灵活性，以下 Roman_string_to_unsigned0() 采用 table。
它遵循 strtol() 风格的功能，返回一个结束指针，指示解析停止的位置。取消引用并针对 '[=13=]' 进行测试以取得成功。
该函数有一个 bool subtractive 参数来控制两种主要类型的罗马数字解析：basic, 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; j<limit; j++) {
if (strncmp(src, digit->ch, 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;
}
注意：不区分大小写尚未编码。空字符串 returns 0。通过此代码从高到低有效，"XXXMMM" 未通过。