Roman Numeral Conversion in Java

Question

I have designed this by using the stack data structure (similar to balanced parentheses problem) checking if the previous element is decreasing the number or not.

package test;

import main.algorithms.RomanConversion;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class RomanConversionTest {

    RomanConversion romanConversion;

    @Before
    public void setUp(){
        romanConversion = new RomanConversion();
    }

    @Test
    public void testRomanConversion(){
        Assert.assertEquals(154, romanConversion.convert("CLIV"));
        Assert.assertEquals(101, romanConversion.convert("CI"));
        Assert.assertEquals(43, romanConversion.convert("XLIII"));
    }

}




package main.algorithms;

import java.util.HashMap;
import java.util.Stack;

public class RomanConversion {

    public HashMap createMap(){
        HashMap<String, Integer> romanMap = new HashMap<>();
        romanMap.put("I" , 1);
        romanMap.put("IV",4);
        romanMap.put("V" ,5);
        romanMap.put("IX",9);
        romanMap.put("X" ,10);
        romanMap.put("XL",40);
        romanMap.put("L" ,50);
        romanMap.put("XC",90);
        romanMap.put("C" ,100);
        romanMap.put("CD",400);
        romanMap.put("D" ,500);
        romanMap.put("CM",900);
        romanMap.put("M" ,1000);

        return romanMap;
    }


    public int convert(String letter) {

        int result=0;
        HashMap<String, Integer> map = new HashMap<>();
        map = createMap();
        String str;
        char[] array = letter.toCharArray();
        Stack<Character> stack = new Stack<>();

        for(char c: array){
            if(stack.isEmpty()){
                result += map.get(String.valueOf(c));
                stack.push(c);
            }else{
                char lastElement= stack.peek();
                if(map.containsKey(lastElement+""+c)) {
                    result -= map.get(String.valueOf(lastElement));
                    result += map.get(String.valueOf(lastElement) + String.valueOf(c));
                    stack.push(c);
                }else{
                    result += map.get(String.valueOf(c));
                    stack.push(c);
                }
            }

        }
        return result;
    }
}

Answer 1

I think your code is - in general - good. Your algorithm is working correctly and I really like the idea of using a Hashmap to save the values of the roman numbers.

---

One thing I miss is the handling of edge cases. Especially you should think about the following edge cases:

• letter == null
• Empty String
• Strings that aren't valid roman numbers (for example "IXI" or "MMMM" aren't valid)

The first two problems are pretty easy to solve:

if(letter == null || letter.equals("")) {
        return -1;
}

The third part is a bit more difficult to solve:

if(!letter.matches("M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$")) {
        return -1;
}

As you can see, you can use a regular expression to validate if the string letter contains a valid roman number (as explained for example here).

---

One thought about your testing-class: You are using JUnit, which is good, but I think you are testing much too little (remember the edge cases!).

I wrote a test myself with the following values:

String[] input = {null, "", "I", "V", "XXXIII", "DCCXLVII", "CMXXIX", "MCCXXXII", "MMMCMXCIX", "MMMMXI", "KMXI", "VX", "VL", "VC", "VD", "VM","LC", "LD", "LM", "DM", "IL", "IC", "ID", "IM", "XD", "XM", "CXLV", "MIXI", "IXI", "MXIII", "MMMM", "IIII"}; 

int[] expectedOutput = {-1, -1, 1, 5, 33, 747, 929, 1232, 3999, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 145, -1, -1, 1013, -1, -1};

Answer 2

Technical

• The local variable String str is never used eirhin method convert. So can be removed.
• Since the map is not supposed to change, make it a static final field, initialized directly or in static constructor.

Stylistic

• Central method not only converts, rather than parses a string representation (using a predifined rule set/grammar). So would rename it to more expressive parseRomanNumeral or parseToInt or similar.

Current Approach: Add Values & Undo

You are using the concept of a lookup-table implemented as map of symbols. This solves mainly the translation of roman symbols to arabic numbers (note: whole number values that can be added; not single numeric digits that represent an 10-based exponential magnitude).

The fact that two sorts of special numbers (i.e. 4, 9; 40, 90; 400, 900) can be represented by two symbols is solved by the stack memory structure that allows to memorize the last character (single push and pop, stack size = 1). This memo will serve like an undo operation, that will reduce the running sum by its previous addition in order to correctly add the special number (e.g. if signaling V translated to 5 then previously added I translated to 1 will be subtracted, in order to add 4).

That 2 data-structures (map and stack) used by 2 behavioural concepts (lookup and undo) form the "meat", whereas iterating char by char, adding translated values left as the "bones" (algorithmic skeleton).

The stack is not needed since all symbols of the input string can be accessed by their position in char-array.

Alternative: Grammar for Calculating Numbers

What if you think of roman numerals as a, numerical system, formed by a grammar for calculating numberical values, which form the vocabulary:

1. The vocabulary of roman symbols (I,V) can be translated to numbers (1, 5).
2. The grammar consists of rules for adding (III = 1+1+1) or subtracting (IV = -1+5) values.
3. each symbol belongs to a group of unit or magnitude (ones 10^1, hundreds 10^2, thousands 10^3) wich require to be in a specific sequence in order to form a valid roman numeral. Generally from higher to lower magnitude (e.g. MCDVI), except the special cases of powers-to-4 (e.g. CMIV).
4. Dependent on the symbol's valid position within its magnitude the mathematical operands are evaluated (either plus or minus).
5. There is also a limit of maximum consecutives for each symbol, = 3 (e.g. III for 3, but not more, because 4 is IV)
6. Iteratively translated symbols may be used to build a valid mathematical sum-expression (e.g. -100 +1000 -1 +5).
7. The resulting sum will be the finaly parsed integer (e.g. 904).

Edge cases

Validation is done by rules inherent to the roman numerical system (some explained above). There is also a symbol for zero : N used standalone.