如何將羅馬數字轉換爲整數，同時使用標準C拒絕無效數字？

Question

什麼意思是正確的Roman numeralsmayvary。爲簡單起見（沒有Unicode，沒有乘法原理，沒有雙subtractives，沒有overbars，沒有大的號碼等）對這一問題的原因，有效的羅馬數字由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()。正則表達式使用「嚴格」規則表示的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。但roman_numeral_to_int()接受由正則表達式拒絕的數字，如IIIII。是否有一個類似的簡單跨平臺解決方案，不需要pcre_exec()或其他外部依賴項可用於有效的羅馬數字，僅適用於？

Answer 1

使用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; 
} 

---

課：我做代碼建立直接的驗證功能。爲了測試它，我需要逆roman_int_to_string()。隨機字符串生成器迅速顯示出許多令人驚訝的錯誤，如"CMC"和"CMCD"以及OP的"IIII"。最後，使用簡單的string-to-int和int-to-string函數對，然後進行字符串比較是最有彈性的。

Answer 2

通過從較高級別的規格生成的C代碼，我們可以得到僅使用標準C.例如一個 可讀溶液，the regex：使用 Ragel finite-state machine compiler

^(?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 ：

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。
• 它是聲明性的，易於而不例如引入誤差延伸，以支持四個連續符號如除了減色IVIIII，它是足以與{,4}取代{,3}。爲支持Unicode /下/大寫字母，相應的文字如'M'可以與M其中M = 'M' | 'm' | "Ⅿ" | "ⅿ";
• ragel將其轉換爲一個快表 - 或goto驅動FSM在純C.

被替換

Complete code example (with Unicode and IIII extensions mentioned above)。生成的roman_numerals.c沒有第三方依賴關係。

Answer 3

羅馬數字分爲兩類，「一」（I，X，C，M）和「五」（V，L，D）。 「五」不能重複，不能被減。當這些「1」不是來自較小的數字時，可以重複三次，並且可以從不大於下一個「1」的數字中減去。

解析時，數字可以有三種不同的模式：它可以正常添加，也可以是要減去的數字，也可以是前一個數字減去的數字。

您可以在構建號碼時執行這些規則。除了數字的值之外，還需要一個對數字進行分類的功能。在下面的代碼中，功能repeat執行此操作。它返回每個數字的最大重複次數，但它也用作分類：3表示「1」，1表示「5」。

下面的代碼似乎產生與您的代碼與正則表達式驗證相同的結果。它返回有效羅馬數字的正數，否則返回−。 （而且有少於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; 
} 

編輯：我的代碼的前兩個草案有錯誤，目前已固定。

由於通過正則表達式來驗證正確性，另一種方法是直接實現正則表達式，同時計算羅馬數字的值。此外，給羅馬數字的邏輯有多複雜，這可能是更好的方法。

這種方法的一個實現可以是：

/* 
*  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 plus正則表達式驗證–對於所有情況產生相同的結果。

Answer 4

簡單而甜蜜的邏輯使用減去值

納克遺憾的代碼是在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  

Answer 5

要創建某種級別的規則靈活性，以下Roman_string_to_unsigned0()使用一個表。

它遵循strtol()風格的功能，因爲返回的結束指針指示停止解析的位置。根據'\0'取得成功，並進行測試。

該函數有一個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; 
} 

---

注：忽略大小寫尚未編碼。一個空字符串返回0.通過這個代碼工作最重要，"XXXMMM"沒有通過。