Programmatic solution to convert Roman numerals to Decimals

It has been a long weekend. While browsing around, I came across the Alien Numbers1 problem which is part of the Google Code Jam practice problem set.

Though I am yet to figure out a right algorithm to solve the ‘Alien Numbers’ problem, it turns out that it is similar to a problem of converting numerals into different base systems.

This drove me to think on a possiblity of programming a solution to convert Roman Numerals2 into their respective decimal notation. Here is the algorithm that I ended up with.

  1. Create a dictionary of critical mappings.
    • The critical Roman numerals are I, V, X, L, C, D, M which represent 1, 5, 10, 50, 100, 500 and 1000 respectively.
  2. Understand the numbering sequence.
    • A Roman numeral written before another indicates substraction of value where as a Roman numeral after the current one indicates addition.
    • For example:
      • XC is 90 i.e. C=100, X=10; since X is before C, substract 10 from 100 resulting in 90.
      • Similarly, XCX is 100 because the first two characters, XC result in 90 which is followed by X, therefore, add 10 to 90 resulting in 100.
  3. To support the logic mentioned in point 2 above, I decided to use a stack.
    • Whenever the input contains a Roman numeral whose value is less than the next Roman numeral in the input sequence, it is pushed to the stack.
  4. If the current Roman numeral is greater than the next one, the contents of the stack are popped and the cumulative sum of the values of the Roman numerals popped from the stack is substracted from the value of the current Roman numeral under consideration.
    • For example:
      • Consider the Roman numerals to be converted to decimal as XCV.
      • The input pointer starts reading input from X and finds that the next numeral is C whose value is greater than X. Therefore, X is pushed to the stack.
      • During the next iteration, the input pointer reads C and finds V as the next successive numeral.
      • Since V is lesser than C in value, the contents of the stack are popped, the value X is substracted from C and the result is stored in a variable (named, output in the program below).
  5. If you have some suggestions for improvement, please feel free to share your thoughts as comments to this post.
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class NumberSystem {
    public static long romanToBaseTen(String roman) {
        Map<Character, Integer> m = new HashMap<>();
        long output = 0;

        // Stack to store numerals that should be considered to be substracted.
        Stack<Character> s = new Stack<>();

        // Store decimal values of critical Roman Numerals.
        m.put('I', 1);
        m.put('V', 5);
        m.put('X', 10);
        m.put('L', 50);
        m.put('C', 100);
        m.put('D', 500);
        m.put('M', 1000);

        for (int i = 0; i < roman.length(); i++) {
            int curCharValue = m.get(roman.charAt(i));
            int nextCharValue = 0;

            // Boundary check - so that we do not cause an exception testing
            // beyond array limits.
            if (i < roman.length() - 1) {
                nextCharValue = m.get(roman.charAt(i + 1));
            }

            if (curCharValue < nextCharValue) {
                s.push(roman.charAt(i));
            } else {
                long temp = 0;
                while (s.isEmpty() == false) {
                    temp += m.get(s.pop());
                }

                // Safety check. Cumulative sum of the contents of the stack
                // should never be more than the current char value. If its
                // true, we have an invalid Roman Numeral representation.
                if (temp > curCharValue) {
                    System.err
                            .println("Invalid Roman Numeral representation found while scanning the Roman Numeral: "
                                    + roman.charAt(i)
                                    + " at position: "
                                    + i
                                    + ".");
                    System.exit(1);
                }
                curCharValue -= temp;
                output += curCharValue;
            }
        }
        return output;
    }

    // Test the conversation logic.
    public static void main(String[] args) {
        org.junit.Assert.assertEquals(romanToBaseTen("I"), 1);
        org.junit.Assert.assertEquals(romanToBaseTen("II"), 2);
        org.junit.Assert.assertEquals(romanToBaseTen("III"), 3);
        org.junit.Assert.assertEquals(romanToBaseTen("IV"), 4);
        org.junit.Assert.assertEquals(romanToBaseTen("V"), 5);
        org.junit.Assert.assertEquals(romanToBaseTen("VI"), 6);
        org.junit.Assert.assertEquals(romanToBaseTen("VII"), 7);
        org.junit.Assert.assertEquals(romanToBaseTen("VIII"), 8);
        org.junit.Assert.assertEquals(romanToBaseTen("IX"), 9);
        org.junit.Assert.assertEquals(romanToBaseTen("X"), 10);
        org.junit.Assert.assertEquals(romanToBaseTen("XI"), 11);
        org.junit.Assert.assertEquals(romanToBaseTen("XII"), 12);
        org.junit.Assert.assertEquals(romanToBaseTen("XIII"), 13);
        org.junit.Assert.assertEquals(romanToBaseTen("XIV"), 14);
        org.junit.Assert.assertEquals(romanToBaseTen("XV"), 15);
        org.junit.Assert.assertEquals(romanToBaseTen("XVI"), 16);
        org.junit.Assert.assertEquals(romanToBaseTen("XVII"), 17);
        org.junit.Assert.assertEquals(romanToBaseTen("XVIII"), 18);
        org.junit.Assert.assertEquals(romanToBaseTen("XIX"), 19);
        org.junit.Assert.assertEquals(romanToBaseTen("XX"), 20);
        org.junit.Assert.assertEquals(romanToBaseTen("XXI"), 21);
        org.junit.Assert.assertEquals(romanToBaseTen("XXII"), 22);
        org.junit.Assert.assertEquals(romanToBaseTen("XXIII"), 23);
        org.junit.Assert.assertEquals(romanToBaseTen("XXIV"), 24);
        org.junit.Assert.assertEquals(romanToBaseTen("XXV"), 25);
        org.junit.Assert.assertEquals(romanToBaseTen("XXVI"), 26);
        org.junit.Assert.assertEquals(romanToBaseTen("XXVII"), 27);
        org.junit.Assert.assertEquals(romanToBaseTen("XXVIII"), 28);
        org.junit.Assert.assertEquals(romanToBaseTen("XXIX"), 29);
        org.junit.Assert.assertEquals(romanToBaseTen("XXX"), 30);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXI"), 31);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXII"), 32);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXIII"), 33);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXIV"), 34);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXV"), 35);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXVI"), 36);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXVII"), 37);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXVIII"), 38);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXIX"), 39);
        org.junit.Assert.assertEquals(romanToBaseTen("XL"), 40);
        org.junit.Assert.assertEquals(romanToBaseTen("XLI"), 41);
        org.junit.Assert.assertEquals(romanToBaseTen("XLII"), 42);
        org.junit.Assert.assertEquals(romanToBaseTen("XLIII"), 43);
        org.junit.Assert.assertEquals(romanToBaseTen("XLIV"), 44);
        org.junit.Assert.assertEquals(romanToBaseTen("XLV"), 45);
        org.junit.Assert.assertEquals(romanToBaseTen("XLVI"), 46);
        org.junit.Assert.assertEquals(romanToBaseTen("XLVII"), 47);
        org.junit.Assert.assertEquals(romanToBaseTen("XLVIII"), 48);
        org.junit.Assert.assertEquals(romanToBaseTen("XLIX"), 49);
        org.junit.Assert.assertEquals(romanToBaseTen("L"), 50);
        org.junit.Assert.assertEquals(romanToBaseTen("LI"), 51);
        org.junit.Assert.assertEquals(romanToBaseTen("LII"), 52);
        org.junit.Assert.assertEquals(romanToBaseTen("LIII"), 53);
        org.junit.Assert.assertEquals(romanToBaseTen("LIV"), 54);
        org.junit.Assert.assertEquals(romanToBaseTen("LV"), 55);
        org.junit.Assert.assertEquals(romanToBaseTen("LVI"), 56);
        org.junit.Assert.assertEquals(romanToBaseTen("LVII"), 57);
        org.junit.Assert.assertEquals(romanToBaseTen("LVIII"), 58);
        org.junit.Assert.assertEquals(romanToBaseTen("LIX"), 59);
        org.junit.Assert.assertEquals(romanToBaseTen("LX"), 60);
        org.junit.Assert.assertEquals(romanToBaseTen("LXI"), 61);
        org.junit.Assert.assertEquals(romanToBaseTen("LXII"), 62);
        org.junit.Assert.assertEquals(romanToBaseTen("LXIII"), 63);
        org.junit.Assert.assertEquals(romanToBaseTen("LXIV"), 64);
        org.junit.Assert.assertEquals(romanToBaseTen("LXV"), 65);
        org.junit.Assert.assertEquals(romanToBaseTen("LXVI"), 66);
        org.junit.Assert.assertEquals(romanToBaseTen("LXVII"), 67);
        org.junit.Assert.assertEquals(romanToBaseTen("LXVIII"), 68);
        org.junit.Assert.assertEquals(romanToBaseTen("LXIX"), 69);
        org.junit.Assert.assertEquals(romanToBaseTen("LXX"), 70);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXI"), 71);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXII"), 72);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXIII"), 73);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXIV"), 74);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXV"), 75);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXVI"), 76);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXVII"), 77);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXVIII"), 78);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXIX"), 79);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXX"), 80);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXI"), 81);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXII"), 82);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXIII"), 83);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXIV"), 84);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXV"), 85);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXVI"), 86);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXVII"), 87);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXVIII"), 88);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXIX"), 89);
        org.junit.Assert.assertEquals(romanToBaseTen("XC"), 90);
        org.junit.Assert.assertEquals(romanToBaseTen("XCI"), 91);
        org.junit.Assert.assertEquals(romanToBaseTen("XCII"), 92);
        org.junit.Assert.assertEquals(romanToBaseTen("XCIII"), 93);
        org.junit.Assert.assertEquals(romanToBaseTen("XCIV"), 94);
        org.junit.Assert.assertEquals(romanToBaseTen("XCV"), 95);
        org.junit.Assert.assertEquals(romanToBaseTen("XCVI"), 96);
        org.junit.Assert.assertEquals(romanToBaseTen("XCVII"), 97);
        org.junit.Assert.assertEquals(romanToBaseTen("XCVIII"), 98);
        org.junit.Assert.assertEquals(romanToBaseTen("XCIX"), 99);
        org.junit.Assert.assertEquals(romanToBaseTen("C"), 100);
        org.junit.Assert.assertEquals(romanToBaseTen("DI"), 501);
        org.junit.Assert.assertEquals(romanToBaseTen("DL"), 550);
        org.junit.Assert.assertEquals(romanToBaseTen("DXXX"), 530);
        org.junit.Assert.assertEquals(romanToBaseTen("DCCVII"), 707);
        org.junit.Assert.assertEquals(romanToBaseTen("DCCCXC"), 890);
        org.junit.Assert.assertEquals(romanToBaseTen("MD"), 1500);
        org.junit.Assert.assertEquals(romanToBaseTen("MDCCC"), 1800);
        org.junit.Assert.assertEquals(romanToBaseTen("CM"), 900);

        System.out.println("All done!");
    }
}

References:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s