Roman Numerals to Integer

From Software Engineers Wiki
Jump to: navigation, search

Convert a string containing roman numerals to integer.

Roman numerals use alphabet letters to represent numbers. In this system,

  • I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
  • A letter placed after another of greater value adds.
  • A letter placed before another of greater value subtracts.

Answer

unsigned int roman_numeral_to_int(const char *str, const char **end)
{
        /* I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 
         * A letter placed after another of greater value adds.
         * A letter placed before another of greater value subtracts.
         */

        const char *cp;
        unsigned int value = 0;
        unsigned int pending_value = 0;

        for (cp = str; *cp != '\0'; ++cp) {
                unsigned int cur_value;

                switch (toupper(*cp)) {
                case 'I' :
                        cur_value = 1;
                        break;
                case 'V' :
                        cur_value = 5;
                        break;
                case 'X' :
                        cur_value = 10;
                        break;
                case 'L' :
                        cur_value = 50;
                        break;
                case 'C' :
                        cur_value = 100;
                        break;
                case 'D' :
                        cur_value = 500;
                        break;
                case 'M' :
                        cur_value = 1000;
                        break;
                default :
                        if (end)
                                *end = cp;
                        return value + pending_value;
                };

                if (pending_value) {
                        if (pending_value < cur_value) {
                                value += cur_value - pending_value;
                                pending_value = 0;
                        } else {
                                value += pending_value;
                                pending_value = cur_value;
                        }
                } else {
                        pending_value = cur_value;
                }
        };

        return value + pending_value;
}

Test program

int main(void)
{
        struct {
                const char *str;
                unsigned int val;
        } test_table[] = {
                { "i", 1 },
                { "ii", 2 },
                { "iii", 3 },
                { "iv", 4 },
                { "v", 5 },
                { "vi", 6 },
                { "vii", 7 },
                { "viii", 8 },
                { "ix", 9 },
                { "x", 10 },
                { "xi", 11 },
                { "xii", 12 },
                { "xiii", 13 },
                { "xiv", 14 },
                { "xv", 15 },
                { "xvi", 16 },
                { "xvii", 17 },
                { "xviii", 18 },
                { "xix", 19 },
                { "xx", 20 },
                { "xxiv", 24 },
                { "xxvi", 26 },
                { "xxix", 29 },
                { "xxx", 30 },
                { "xl", 40 },
                { "xli", 41 },
                { "xliv", 44 },
                { "xlv", 45 },
                { "xlvi", 46 },
                { "xlix", 49 },
                { "l", 50 },
                { "li", 51 },
                { "lii", 52 },
                { "lxvii", 67 },
                { "lxxxviii", 88 },
                { "lxxxix", 89 },
                { "xc", 90 },
                { "xci", 91 },
                { "xcv", 95 },
                { "xcix", 99 },
                { "c", 100 },
                { "di", 501 },
                { "dxxx", 530 },
                { "dl", 550 },
                { "dccvii", 707 },
                { "dcccxc", 890 },
                { "cm", 900 },
                { "md", 1500 },
                { "mdccxcix", 1799 },
                { "mdccc", 1800 },
        };

        unsigned int i;
        unsigned int val;

        for (i = 0; i < sizeof(test_table) / sizeof(test_table[0]); ++i) {
                val = roman_numeral_to_int(test_table[i].str, NULL);
                if (val != test_table[i].val) {
                        printf("Error: %s is %u but got %u\n",
                                test_table[i].str, test_table[i].val, val);
                }
        }

        return 0;
}

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox