A friend once mentioned she had trouble Creating a Roman Numeral Converter for a competition at school. I have always thought it was an interesting problem. Recently, I was thinking of working on a puzzle and decided on this one, so I had a crack at it.
Creating a Roman Numeral Converter: Defining the Problem
Roman numerals are nearly descending characters representing different numerical values. The numerical values for each symbol are:
- I = 1
- V = 5
- X = 10
- L = 50
- C = 100
- D = 500
- M = 1000
I say nearly descending, because they use a shortcut for writing numbers near the next boundary. For example IV = 4. This is because when you have an ascension, you subtract the first value of the pair, so in the example you subtract 1 from 5.
The rule to this seems to be clearly followed, although I’ve never found where it’s defined, but it can only be one character and there are limits to how far up the number can ascend. For example, I would expect 99 to be IC, which makes perfect sense to me, but it’s XCIX, which is readable but a lot more complicated.
So now, we want to build a general converter that will translate roman numerals into Arabic numerals. Sounds fun, right?
(Okay, only sick people like me like this stuff, but here we are nevertheless.)
Creating a Roman Numeral Converter: Designing the Solution
When Creating a Roman Numeral Converter, clearly we need a RomanNumeral class that is going to be the heart of the system. This is going to be an immutable, so the constructor will need to take a string that is a roman numeral. We will also need to retrieve an integer value of the roman numeral. Finally, for robustness, we will need a toString method that returns the roman numeral. These seem to fill the entire interface. We could add addition, subtraction, etc. to use with other RomanNumeral instances, but, following Booch‘s rule of minimal but complete, it feels like overkill since you can just get the integer and do all those functions with it.
Finally, we’re going to need a class level int to store the value. So the beginning of our class looks like this:
public class RomanNumeral {
private int value;
/**
* Create a roman numeral from a String
* @param romanNumeral the roman numeral, e.g., "IX"
*/
public RomanNumeral(String romanNumeral) {
value = 0;
}
/**
* Return the integer value
* @return the value
*/
public int getValue() {
return value;
}
Parsing the Value
We are going to need to parse the value and it might be useful to clients to simply convert a roman numeral into an integer. In addition, it’s good form to break out complex logic into a separate method, so I’m going to create a static method to parse the value and call it from our constructor.
Now, generally, when parsing Strings, the first thing I think of is using a state machine. I started down the path of this and realized that it was overkill. You simply need to compare the current value with the previous value. If it ascended, then the previous value needs to be subtracted twice from the current total since we already added it on the previous step. Then we add this value.
This calls for two helper methods, one that converts a roman numeral character into an int and one that compares the values. For speed and simplicity, I’m electing to put these into a map at the beginning.
Here’s what all of this looks like.
private static final Map<Character, Integer> characterValues = new HashMap<>();
static {
characterValues.put('I', 1);
characterValues.put('V', 5);
characterValues.put('X', 10);
characterValues.put('L', 50);
characterValues.put('C', 100);
characterValues.put('D', 500);
characterValues.put('M', 1000);
}
/**
* Return the value of a single roman numeral character
* @param romNum a roman numeral character
* @return the int value or zero if not valid
*/
private static int getNumeralValue(char romNum) {
int result = 0;
Integer val = characterValues.get(romNum);
if (val != null) {
result = val;
}
return result;
}
/**
* Parse a roman numeral String into an int
* @param romanNumeral the roman numeral
* @return the int value
*/
public static int parseValue(String romanNumeral) {
int idx = 0;
char ch;
char lastChar = Character.MAX_VALUE;
int result = 0;
boolean done = false;
while (!done) {
ch = romanNumeral.charAt(idx);
int val = getNumeralValue(ch);
if (compare(lastChar, ch) < 0) {
result -= (getNumeralValue(lastChar) * 2);
}
else {
result += val;
idx++;
}
lastChar = ch;
if (idx >= romanNumeral.length()) {
done = true;
}
}
return result;
}
/**
* Compare to roman numeral characters
* @param c1 the first value
* @param c2 the second value
* @return an integer that is less than, equal to, or greater than zero as the first value is greater than, equal to, or less than
* second value.
*/
protected static int compare(char c1, char c2) {
int val1 = getNumeralValue(c1);
if (val1 == 0) {
val1 = Integer.MAX_VALUE;
}
int val2 = getNumeralValue(c2);
int result = val1 - val2;
return result;
}
Converting it Back
A truly complete implementation requires us to convert this value back into a roman numeral. This process requires us to take away the largest possible roman numeral each time until the value hits zero and then returning that. Java’s toString() is perfect for this.
This is another method that would be useful to the client classes, so I’m going to create a static toString(String romNum) that does the heavy lifting. Here’s that part.
public static final String ROM_NUM_1000 = "M";
public static final String ROM_NUM_900 = "CM";
public static final String ROM_NUM_500 = "D";
public static final String ROM_NUM_400 = "CD";
public static final String ROM_NUM_100 = "C";
public static final String ROM_NUM_90 = "XC";
public static final String ROM_NUM_50 = "L";
public static final String ROM_NUM_40 = "XL";
public static final String ROM_NUM_10 = "X";
public static final String ROM_NUM_9 = "IX";
public static final String ROM_NUM_5 = "V";
public static final String ROM_NUM_4 = "IV";
public static final String ROM_NUM_1 = "I";
@Override
public String toString() {
return toString(value);
}
/**
* Convert a value into a roman numeral
* @param val the value
* @return the roman numeral
*/
public static String toString(int val) {
StringBuilder sb = new StringBuilder(10);
int num = val;
while(num > 0) {
if (num >= 1000) {
sb.append(ROM_NUM_1000);
num -= 1000;
}
else if (num >= 900) {
sb.append(ROM_NUM_900);
num -= 900;
}
else if (num >= 500) {
sb.append(ROM_NUM_500);
num -= 500;
}
else if (num >= 400) {
sb.append(ROM_NUM_400);
num -= 400;
}
else if (num >= 100) {
sb.append(ROM_NUM_100);
num -= 100;
}
else if (num >= 90) {
sb.append(ROM_NUM_90);
num -= 90;
}
else if (num >= 50) {
sb.append(ROM_NUM_50);
num -= 50;
}
else if (num >= 40) {
sb.append(ROM_NUM_40);
num -= 40;
}
else if (num >= 10) {
sb.append(ROM_NUM_10);
num -= 10;
}
else if (num >= 9) {
sb.append(ROM_NUM_9);
num -= 9;
}
else if (num >= 5) {
sb.append(ROM_NUM_5);
num -= 5;
}
else if (num >= 4) {
sb.append(ROM_NUM_4);
num -= 4;
}
else {
sb.append(ROM_NUM_1);
num -= 1;
}
}
return sb.toString();
}
Named Constants
You will notice that I used named constants for the strings. This is good form as it is not an “X” but the representation for a 10. This would be magic string. Conversely, I didn’t use named constants for the values because they represent the integer value and not a magic number, and so it isn’t necessary.
Testing
Groovy/Spock
It is critical that we have a good unit test for this. I use Spock for my unit tests. It is a good framework and has some nice features, but using groovy costs us in that changes to method names and such don’t generate compile errors but runtime errors. This downside is offset for me by the fact that it lets me test protected and private methods without changing my class like I used to have to do with junit just to support good testing.
That said, here is my unit test.
package com.heavyweightsoftware.romannumeralconverter
import spock.lang.Specification
class RomanNumeralTest extends Specification {
def "GetNumeralValue"() {
expect:
amt == RomanNumeral.getNumeralValue((char) romNum)
where:
romNum | amt
'I' | 1
'V' | 5
'X' | 10
'L' | 50
'C' | 100
'D' | 500
'M' | 1000
"G" | 0
}
def "ParseValue"() {
expect:
amt == RomanNumeral.parseValue(romNum)
where:
romNum | amt
"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
"XXI" | 21
"XXII" | 22
"XXIII" | 23
"XXIV" | 24
"XXV" | 25
"XX" | 20
"XXV" | 25
"XXX" | 30
"XXXV" | 35
"XL" | 40
"XLV" | 45
"L" | 50
"LV" | 55
"LX" | 60
"LXV" | 65
"LXX" | 70
"LXXV" | 75
"LXXX" | 80
"LXXXV" | 85
"XC" | 90
"XCV" | 95
"XCIX" | 99
"C" | 100
"CV" | 105
"CX" | 110
"CXV" | 115
"CXX" | 120
"CXXV" | 125
"CXXX" | 130
"CXXXV" | 135
"CXL" | 140
"C" | 100
"CXXV" | 125
"CL" | 150
"CLXXV" | 175
"CC" | 200
"CCXXV" | 225
"CCL" | 250
"CCLXXV" | 275
"CCC" | 300
"CCCXXV" | 325
"CCCL" | 350
"CCCLXXV" | 375
"CD" | 400
"CDXXV" | 425
"CDL" | 450
"CDLXXV" | 475
"D" | 500
"DXXV" | 525
"DL" | 550
"DLXXV" | 575
"DC" | 600
"DCXXV" | 625
"DCL" | 650
"DCLXXV" | 675
"DCC" | 700
"DCCL" | 750
"DCCCXXV" | 825
"CM" | 900
"CMLXXV" | 975
"ML" | 1050
"MCXXV" | 1125
"MCC" | 1200
"MCCLXXV" | 1275
"MCCCL" | 1350
"MCDXXV" | 1425
"MD" | 1500
"MDLXXV" | 1575
"MDCL" | 1650
"MDCCXXV" | 1725
"MDCCC" | 1800
"MDCCCLXXV" | 1875
"MCML" | 1950
"MCMXCIX" | 1999
"MMXXV" | 2025
"MMC" | 2100
"MMCLXXV" | 2175
"MMCCL" | 2250
"MMCCCXXV" | 2325
"MMCD" | 2400
"MMCDLXXV" | 2475
"MMDL" | 2550
}
def "ToString"() {
expect:
RomanNumeral romanNumeral = new RomanNumeral(romIn)
romOut == romanNumeral.toString()
where:
romIn | romOut
"I" | "I"
"II" | "II"
"III" | "III"
"IV" | "IV"
"V" | "V"
"VI" | "VI"
"VII" | "VII"
"VIII" | "VIII"
"IX" | "IX"
"X" | "X"
"XI" | "XI"
"XII" | "XII"
"XIII" | "XIII"
"XIV" | "XIV"
"XV" | "XV"
"XVI" | "XVI"
"XVII" | "XVII"
"XVIII" | "XVIII"
"XIX" | "XIX"
"XX" | "XX"
"XXI" | "XXI"
"XXII" | "XXII"
"XXIII" | "XXIII"
"XXIV" | "XXIV"
"XXV" | "XXV"
"XX" | "XX"
"XXV" | "XXV"
"XXX" | "XXX"
"XXXV" | "XXXV"
"XL" | "XL"
"XLV" | "XLV"
"L" | "L"
"LV" | "LV"
"LX" | "LX"
"LXV" | "LXV"
"LXX" | "LXX"
"LXXV" | "LXXV"
"LXXX" | "LXXX"
"LXXXV" | "LXXXV"
"XC" | "XC"
"XCV" | "XCV"
"XCIX" | "XCIX"
"C" | "C"
"CV" | "CV"
"CX" | "CX"
"CXV" | "CXV"
"CXX" | "CXX"
"CXXV" | "CXXV"
"CXXX" | "CXXX"
"CXXXV" | "CXXXV"
"CXL" | "CXL"
"C" | "C"
"CXXV" | "CXXV"
"CL" | "CL"
"CLXXV" | "CLXXV"
"CC" | "CC"
"CCXXV" | "CCXXV"
"CCL" | "CCL"
"CCLXXV" | "CCLXXV"
"CCC" | "CCC"
"CCCXXV" | "CCCXXV"
"CCCL" | "CCCL"
"CCCLXXV" | "CCCLXXV"
"CD" | "CD"
"CDXXV" | "CDXXV"
"CDL" | "CDL"
"CDLXXV" | "CDLXXV"
"D" | "D"
"DXXV" | "DXXV"
"DL" | "DL"
"DLXXV" | "DLXXV"
"DC" | "DC"
"DCXXV" | "DCXXV"
"DCL" | "DCL"
"DCLXXV" | "DCLXXV"
"DCC" | "DCC"
"DCCL" | "DCCL"
"DCCCXXV" | "DCCCXXV"
"CM" | "CM"
"CMLXXV" | "CMLXXV"
"ML" | "ML"
"MCXXV" | "MCXXV"
"MCC" | "MCC"
"MCCLXXV" | "MCCLXXV"
"MCCCL" | "MCCCL"
"MCDXXV" | "MCDXXV"
"MD" | "MD"
"MDLXXV" | "MDLXXV"
"MDCL" | "MDCL"
"MDCCXXV" | "MDCCXXV"
"MDCCC" | "MDCCC"
"MDCCCLXXV" | "MDCCCLXXV"
"MCML" | "MCML"
"MCMXCIX" | "MCMXCIX"
"MMXXV" | "MMXXV"
"MMC" | "MMC"
"MMCLXXV" | "MMCLXXV"
"MMCCL" | "MMCCL"
"MMCCCXXV" | "MMCCCXXV"
"MMCD" | "MMCD"
"MMCDLXXV" | "MMCDLXXV"
"MMDL" | "MMDL"
}
}
Test First
Despite the fact that I have waited until the end to talk about the test, I started with the unit test and it was indispensable in writing my parser. I do not always write the test first, but almost always. You will find it useful in these circumstances.
Creating a Roman Numeral Converter: The Driver
Now that that’s all done, we simply need to write a driver program that reads an input file and parse all of the roman numerals. Here it is.
package com.heavyweightsoftware.romannumeralconverter;
import java.io.*;
import java.net.URL;
public class Main {
public static final String fileName = "/romanNumerals.txt";
public static void main(String[] args) throws IOException {
BufferedReader reader = openInputFile(fileName);
String line = "";
while ((line = reader.readLine()) != null) {
RomanNumeral romanNumeral = new RomanNumeral(line);
System.out.print(line);
System.out.print('\t');
System.out.println(romanNumeral.getValue());
}
reader.close();
}
private static BufferedReader openInputFile(String fileName) throws FileNotFoundException {
URL url = Main.class.getResource(fileName);
if (url == null) {
throw new FileNotFoundException(fileName);
}
File file = new File(url.getFile());
FileReader fileReader = new FileReader(file);
BufferedReader bufferedReader = new BufferedReader(fileReader);
return bufferedReader;
}
}
Final Thoughts
A truly robust solution would include a compare, equals, and hashcode function. I have decided to leave these as an exercise for the reader. Good luck and happy coding. Full code is available here.
For other tutorials, you can check out my FixedDecimal class.
Thanks for playing!
Creating a Roman Numeral Converter