3
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Technically, both Roman and Arabic numerals are string representations of a mathematical value. In other words, what you're really doing is formatting/parsing a value, not creating a new type as such. If you want to make a new type, you should really have two - one for just the "Roman" representation, and one for the "Arabic", then have a Value method that returns an int or whatever. This should be a value type (struct), and you shouldn't allow the creation of invalid values (throw during creation). \$\endgroup\$ – Clockwork-Muse Feb 15 '15 at 8:45
  • \$\begingroup\$ I wouldn't measure the cyclomatic complexity on this one... just sayin' .... \$\endgroup\$ – Radu Murzea Feb 15 '15 at 12:24
5
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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 :)

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy