Code Only: Bidirectional roman numeral parsing.
/*
Copyright (c) 2004 DigiTec Web Consultants, LLC. All rights reserved.
The use of this software is for test and performance purposes only.
You may not use this software in any commercial applications without
the express permission of the copyright holder. You may add to or
modify the code contained here-in to cause it to run slower without
contacting the copyright holder, however, any attempts to make this
code run faster should be documented on:
http://weblogs.asp.net/justin_rogers/articles/132739.aspx
I reserve the right to change or modify the publicly available version
of this code at any time. I will not provide version protection, so
if you have reliance on a particular build of this software, then make
your own back-ups.
You must laugh, at least a little, when reading this licensing agreement,
unless of course you don't have a sense of humor. In all seriousness,
excluding the laughter, laughter in itself does not void this license
agreement, nor compromise it's ability to legally bind you.
You must not remove this notice, or any other, from this software.
*/
/*
VERSION 1.1, October 25th, 2004
Int2RomTable() -
Converts an integer to a roman numeral using a mapping table.
Added thousands expansion for performance, 800% peformance
gain on large integers.
Rom2Int() -
Added thousands reduction for performance on large roman numerals.
Main() -
Added round-trip testing for Int2RomTable()
Added performance screening for Int2Rom() and Int2RomTable()
VERSION 1.0, October 24th, 2004
Int2Rom() -
Converts an integer to a roman numeral with thousands expansion
Rom2Int() -
Converts a roman numeral to an integer with validation
Main() -
Round-trip testing and validation of both functions.
Test cases up to 50,000
*/
using System;
public class RomanNumeralConverter {
private static void Main(string[] args) {
for(int i = 1; i < 50000; i++) {
if ( i != Rom2Int(Int2Rom(i)) ) {
Console.WriteLine("Failure in Switch {0}", i);
break;
}
if ( i != Rom2Int(Int2RomTable(i)) ) {
Console.WriteLine("Failure in Table {0}", i);
break;
}
}
/*
Careful with the GC...
*/
DateTime start, end;
start = DateTime.Now;
for(int i = 0; i < 100000; i++) {
Int2RomTable(i);
}
end = DateTime.Now;
Console.WriteLine("Timing for Int2RomTable: {0}", end - start);
start = DateTime.Now;
for(int i = 0; i < 100000; i++) {
Int2Rom(i);
}
end = DateTime.Now;
Console.WriteLine("Timing for Int2Rom: {0}", end - start);
}
public struct Int2RomMap {
public int Decimal;
public string Roman;
public Int2RomMap(int dec, string rom) {
this.Decimal = dec;
this.Roman = rom;
}
}
public static Int2RomMap[] MappingTable = new Int2RomMap[] {
new Int2RomMap(900, "CM"), new Int2RomMap(500, "D"),
new Int2RomMap(400, "CD"), new Int2RomMap(100, "C"),
new Int2RomMap(90, "XC"), new Int2RomMap(50, "L"),
new Int2RomMap(40, "XL"), new Int2RomMap(10, "X"),
new Int2RomMap(9, "IX"), new Int2RomMap(5, "V"),
new Int2RomMap(4, "IV"), new Int2RomMap(1, "I")
};
public static string Int2RomTable(int integer) {
string roman = string.Empty;
int bottom = integer % 1000;
int top = integer / 1000;
for ( int i = 0; i < MappingTable.Length; i++) {
while(bottom >= MappingTable[i].Decimal ) {
bottom -= MappingTable[i].Decimal;
roman += MappingTable[i].Roman;
}
}
return (new string('M', top)) + roman;
}
public static string Int2Rom(int integer) {
if ( integer < 1 ) { return null; }
string output = string.Empty;
int scale = 1;
int bottom = integer % 1000;
int top = integer / 1000;
while(bottom > 0) {
int value = bottom % 10; bottom /= 10;
switch(value) {
case 1:
switch(scale) {
case 1:
output = "I" + output;
break;
case 2:
output = "X" + output;
break;
case 3:
output = "C" + output;
break;
}
break;
case 2:
switch(scale) {
case 1:
output = "II" + output;
break;
case 2:
output = "XX" + output;
break;
case 3:
output = "CC" + output;
break;
}
break;
case 3:
switch(scale) {
case 1:
output = "III" + output;
break;
case 2:
output = "XXX" + output;
break;
case 3:
output = "CCC" + output;
break;
}
break;
case 4:
switch(scale) {
case 1:
output = "IV" + output;
break;
case 2:
output = "XL" + output;
break;
case 3:
output = "CD" + output;
break;
}
break;
case 5:
switch(scale) {
case 1:
output = "V" + output;
break;
case 2:
output = "L" + output;
break;
case 3:
output = "D" + output;
break;
}
break;
case 6:
switch(scale) {
case 1:
output = "VI" + output;
break;
case 2:
output = "LX" + output;
break;
case 3:
output = "DC" + output;
break;
}
break;
case 7:
switch(scale) {
case 1:
output = "VII" + output;
break;
case 2:
output = "LXX" + output;
break;
case 3:
output = "DCC" + output;
break;
}
break;
case 8:
switch(scale) {
case 1:
output = "VIII" + output;
break;
case 2:
output = "LXXX" + output;
break;
case 3:
output = "DCCC" + output;
break;
}
break;
case 9:
switch(scale) {
case 1:
output = "IX" + output;
break;
case 2:
output = "XC" + output;
break;
case 3:
output = "CM" + output;
break;
}
break;
}
scale++;
}
return (new string('M', top)) + output;
}
public static int Rom2Int(string roman) {
// Romans had no option for 0.
if ( roman == null || roman.Length == 0 ) { return 0; }
// Accumulator for final value
int accumulator = 0;
// Prior character handling
char lastCharacter = '\0'; // Placeholder
// Prior character scale checks
int scale = 4;
int i = 0;
/*
Performance optimization for leading thousands
*/
for(; i < roman.Length; i++) {
if ( roman[i] != 'm' && roman[i] != 'M' ) {
break;
}
accumulator += 1000;
}
for(; i < roman.Length; i++) {
switch(roman[i]) {
case 'i': case 'I':
switch(lastCharacter) {
case 'i': case 'I':
scale = 0;
goto default;
default:
accumulator++;
if ( accumulator % 5 == 0 ) { return -1; }
break;
}
break;
case 'v': case 'V':
switch(lastCharacter) {
case 'i': case 'I':
if ( scale < 1 ) { return -1; }
accumulator += 3;
scale = 0;
break;
case 'v': case 'V':
return -1; // Error
default:
accumulator += 5;
scale = 0;
break;
}
break;
case 'x': case 'X':
switch(lastCharacter) {
case 'i': case 'I':
if ( scale < 1 ) { return -1; }
accumulator += 8;
scale = 0;
break;
case 'v': case 'V':
return -1; // Error
case 'x': case 'X':
scale = 1;
goto default;
default:
accumulator += 10;
if ( accumulator % 50 == 0 ) { return -1; }
break;
}
break;
case 'l': case 'L':
switch(lastCharacter) {
case 'x': case 'X':
if ( scale < 2 ) { return -1; }
accumulator += 30;
scale = 1;
break;
case 'v': case 'V': case 'i': case 'I': case 'l': case 'L':
return -1; // Error
default:
if ( scale < 2 ) { return -1; }
accumulator += 50;
scale = 1;
break;
}
break;
case 'c': case 'C':
switch(lastCharacter) {
case 'x': case 'X':
if ( scale < 2 ) { return -1; }
accumulator += 80;
scale = 1;
break;
case 'v': case 'V': case 'i': case 'I': case 'l': case 'L':
return -1; // Error
case 'c': case 'C':
scale = 3;
goto default;
default:
if ( scale < 3 ) { return -1; }
accumulator += 100;
if ( accumulator % 500 == 0 ) { return -1; }
break;
}
break;
case 'd': case 'D':
switch(lastCharacter) {
case 'c': case 'C':
if ( scale < 4 ) { return -1; }
accumulator += 300;
scale = 2;
break;
case 'v': case 'V': case 'i': case 'I': case 'l': case 'L':
case 'x': case 'X': case 'd': case 'D':
return -1; // Error
default:
if ( scale < 4 ) { return -1; }
accumulator += 500;
scale = 3;
break;
}
break;
case 'm': case 'M':
if ( lastCharacter != 'c' && lastCharacter != 'C' ) {
return -1;
}
if ( scale < 4 ) { return -1; }
accumulator += 800;
scale = 2;
break;
/*
switch(lastCharacter) {
case 'c': case 'C':
if ( scale < 4 ) { return -1; }
accumulator += 800;
scale = 2;
break;
case 'v': case 'V': case 'i': case 'I': case 'l': case 'L':
case 'x': case 'X': case 'd': case 'D':
return -1; // Error
default:
if ( scale < 4 ) { return -1; }
accumulator += 1000;
break;
default:
return -1;
}
break;
*/
default:
return -1; // Error, consider whitespace trimming
}
lastCharacter = roman[i];
}
return accumulator;
}
}