Roman Numerals - the good, the bad, and the ugly

Question

I wrote a RomanNumeral class in C#. Please pull it to pieces:

class RomanNumeral
{
    public RomanNumeral(string num)
    {
        AsRoman = num;
        AsArabic = RomanNumeralToArabic(num);

        if (AsArabic == -1)
        {
            throw new ArgumentException();
        }
    }

    public RomanNumeral(int num)
    {
        AsRoman = ArabicNumeralToRoman(num);
        AsArabic = num;

        if (AsRoman == "")
        {
            throw new ArgumentException();
        }
    }

    private string ArabicNumeralToRoman(int num)
    {
        string val = "";

        while (num >= 1000)
        {
            val += "M";
            num -= 1000;
        }
        if (num >= 900)
        {
            val += "CM";
            num -= 900;
        }
        while (num >= 500)
        {
            val += "D";
            num -= 500;
        }
        if (num >= 400)
        {
            val += "CD";
            num -= 400;
        }
        while (num >= 100)
        {
            val += "C";
            num -= 100;
        }
        if (num >= 90)
        {
            val += "XC";
            num -= (0;
        }
        while (num >= 50)
        {
            val += "L";
            num -= 50;
        }
        if (num >= 40)
        {
            val += "XL";
            num -= 40;
        }
        while (num >= 10)
        {
            val += "X";
            num -= 10;
        }
        if (num >= 9)
        {
            val += "IX";
            num -= 9;
        }
        while (num >= 5)
        {
            val += "V";
            num -= 5;
        }
        if (num >= 4)
        {
            val += "IV";
            num -= 4;
        }
        while (num >= 1)
        {
            val += "I";
            num -= 1;
        }

        return val;
    }

    private int RomanNumeralToArabic(string num)
    {
        int val = -1;

        for (int i = 0; i < num.Length; i++)
        {
            switch (num[i])
            {
                case 'M':
                    val += 1000;
                    break;
                case 'D':
                    val += 500;
                    break;
                case 'C':
                    if (i != num.Length - 1)
                    {
                        switch (num[i + 1])
                        {
                            case 'M':
                            case 'D':
                                val -= 100;
                                break;
                            default:
                                val += 100;
                                break;
                        }
                    }
                    else
                    {
                        val += 100;
                    }
                    break;
                case 'L':
                    val += 50;
                    break;
                case 'X':
                    if (i != num.Length - 1)
                    {
                        switch (num[i + 1])
                        {
                            case 'M':
                            case 'D':
                                return -1;
                            case 'L':
                            case 'C':
                                val -= 10;
                                break;
                            default:
                                val += 10;
                                break;
                        }
                    }
                    else
                    {
                        val += 10;
                    }
                    break;
                case 'V':
                    val += 5;
                    break;
                case 'I':
                    if (i != num.Length - 1)
                    {
                        switch (num[i + 1])
                        {
                            case 'X':
                            case 'V':
                                val -= 1;
                                break;
                            case 'I':
                                val += 1;
                                break;
                            default:
                                return -1;
                        }
                    }
                    else
                    {
                        val += 1;
                    }
                    break;
                default:
                    return -1;
            }
        }

        return val;
    }

    public string AsRoman { get; private set; }
    public int AsArabic { get; private set; }
}

I really hate that humongous switch in RomanNumeralToArabic. Should that be a if/else if/else series, or is there a better way to do it entirely?

Answer 1

It is probably worth exploring other algorithms, if you wish to optimize for speed or brevity. Or just to explore the possibilities.

Another interesting algorithm that I've seen used is first to normalize the roman numerals to a form which excludes their "subtractive" use: so, a string replace of CM CD XC XL IX IV to their equivalents DCCCC CCCC LXXXX XXXX VIIII IIII. Then you have a far easier job, since you can just assign a value to each letter and count how many of that letter there is in the string. Even better, all letters of a type will all be grouped together, and sorted largest to smallest, so you can loop over them until they change.

Pseudocode:

result = 0;
replace CM DCCCC
replace CD CCCC
replace XC LXXXX
replace XL XXXX
replace IX VIIII
replace IV IIII

read nextChar;
while (nextChar == 'I') { result += 1;    read nextChar; }
while (nextChar == 'V') { result += 5;    read nextChar; }
while (nextChar == 'X') { result += 10;   read nextChar; }
while (nextChar == 'L') { result += 50;   read nextChar; }
while (nextChar == 'C') { result += 100;  read nextChar; }
while (nextchar == 'D') { result += 500;  read nextChar; }
while (nextChar == 'M') { result += 1000; read nextChar; }

Best case, this still requires two passes, but it's kinda delightful in my head.

Another algorithm is to work right-to-left, adding or subtracting each entry from a running total, which you can unroll to get the fastest roman numeral parsing algorithm I know of (1 read, 1 cmp, 1 add or subtract per char, plus overhead of 6 cmps per string)

read prevChar;
while (prevChar == 'I') {
    result += 1;
    read prevChar;
}
while (prevChar == 'V') {
    result += 5;
    read prevChar;
    if (prevChar == 'I') { result -= 1; read prevChar; }
}
... repeat above block 5 more times replacing values for X, L, C, D, M.

Answer 2

Note: I don't know any C#, so I'm not able to provide any code samples. All code is pseudo-code.

The way I would implement this is using a hash map and a while loop. The hash map links arabic numerals to roman numerals:

TRANSLATIONS = { 
  1000 => "M", 900 => "CM", 500 => "D", 400 => "CD",
   100 => "C",  90 => "XC",  50 => "L",  40 => "XL",
    10 => "X",   9 => "IX",   5 => "V",   4 => "IV",
     1 => "I"
}

You can then loop through the hash map (from highest key to lowest key). You can check how many times the current numeral should be displayed by dividing. You can find out how to display the rest by using the modulo operation (% in most languages).

number = 64
rest   = number
result = ""

for arabic, numeral in map {
  times = rest / arabic
  rest  = rest % arabic # modulo

  for i = 0, i < times; i = i + 1 {
    result = result + numeral
  }

  if (rest == 0) {
    break
  }
}

return result

I hope this is useful :)

Answer 3

Here's a simple little method for that, that you might find useful:

static string ToRoman(int input)
{
    const string digits = "IVXLCDM";
    int[] number = { 1, 5, 10, 50, 100, 500, 1000 };
    int[] amount = { 0, 0, 0, 0, 0, 0, 0 };
    if (input > 3999)
        return "Invalid input";
    for (int i = 6; i > -1; i -= 2)
    {
        amount[i] = (int)(input / Math.Pow(10, (i / 2)));
        input -= number[i] * amount[i];
        if (amount[i] > 4)
        {
            if (amount[i] < 9)
            {
                amount[i + 1]++;
                amount[i] -= 5;
            }
        }
    }
    string output = "";
    for (int i = 6; i > -1; i--)
    {
        if (amount[i] >= 4)
        {
            output += digits[i];
            output += digits[i + (int)(amount[i] / 4)];
        }
        else
            for (int j = 0; j < amount[i]; j++)
            {
                output += digits[i];
            }
    }
    return output;
}

This is basically in 2 parts. First part determines the number of each digit needed. The second part converts that information to a string of the appropriate letters. Using the collections like this greatly reduces the conditionals needed.