Solution for Programmming Exercise 8.3
This page contains a sample solution to one of the exercises from Introduction to Programming Using Java.
Exercise 8.3:
A Roman numeral represents an integer using letters. Examples are XVII to represent 17, MCMLIII for 1953, and MMMCCCIII for 3303. By contrast, ordinary numbers such as 17 or 1953 are called Arabic numerals. The following table shows the Arabic equivalent of all the single-letter Roman numerals:
M 1000 X 10 D 500 V 5 C 100 I 1 L 50
When letters are strung together, the values of the letters are just added up, with the following exception. When a letter of smaller value is followed by a letter of larger value, the smaller value is subtracted from the larger value. For example, IV represents 5 - 1, or 4. And MCMXCV is interpreted as M + CM + XC + V, or 1000 + (1000 - 100) + (100 - 10) + 5, which is 1995. In standard Roman numerals, no more than thee consecutive copies of the same letter are used. Following these rules, every number between 1 and 3999 can be represented as a Roman numeral made up of the following one- and two-letter combinations:
M 1000 X 10 CM 900 IX 9 D 500 V 5 CD 400 IV 4 C 100 I 1 XC 90 L 50 XL 40
Write a class to represent Roman numerals. The class should have two constructors. One constructs a Roman numeral from a string such as "XVII" or "MCMXCV". It should throw a NumberFormatException if the string is not a legal Roman numeral. The other constructor constructs a Roman numeral from an int. It should throw a NumberFormatException if the int is outside the range 1 to 3999.
In addition, the class should have two instance methods. The method toString() returns the string that represents the Roman numeral. The method toInt() returns the value of the Roman numeral as an int.
At some point in your class, you will have to convert an int into the string that represents the corresponding Roman numeral. One way to approach this is to gradually "move" value from the Arabic numeral to the Roman numeral. Here is the beginning of a routine that will do this, where number is the int that is to be converted:
String roman = "";
int N = number;
while (N >= 1000) {
// Move 1000 from N to roman.
roman += "M";
N -= 1000;
}
while (N >= 900) {
// Move 900 from N to roman.
roman += "CM";
N -= 900;
}
.
. // Continue with other values from the above table.
.
(You can save yourself a lot of typing in this routine if you use arrays in a clever way to represent the data in the above table.)
Once you've written your class, use it in a main program that will read both Arabic numerals and Roman numerals entered by the user. If the user enters an Arabic numeral, print the corresponding Roman numeral. If the user enters a Roman numeral, print the corresponding Arabic numeral. (You can tell the difference by using TextIO.peek() to peek at the first character in the user's input. If that character is a digit, then the user's input is an Arabic numeral. Otherwise, it's a Roman numeral.) The program should end when the user inputs an empty line. Here is an applet that simulates my solution to this problem:
My class is called RomanNumeral. An object of type RomanNumeral has a private instance variable of type int that stores the integer value of the Roman numeral. When the toString() method is called, it computes the string that represents the Roman number based on the value of this int. By contrast, the toInt() method simply returns the value of the instance variable. This is not the only way that things could be done. I might have stored the string representation of the Roman numeral in an instance variable. In that case, the toString() method would simply return the stored value, while the toInt() method would have to compute the int value from the stored String. It would even be possible to store both the int and String representations in the object. (The point, though, is that it's not necessary to do so. The two representations hold exactly the same information.)
In my version of the class, the constructor which takes a parameter of type int simply has to store the parameter value in the instance variable, after checking that it is in the legal range of values.
The constructor that takes a parameter of type String must interpret the string as a Roman numeral and convert it to the corresponding int value. This is done by adding up the integer value associated with each character or pair of characters in the string. The fact that characters sometimes need to be considered in pairs complicates things a bit. An algorithm for converting a String, roman, to an int, arabic, is:
Let arabic = 0
Let i = 0 // representing a position in the string
while i is a legal position in the string:
Let ch be the character in position i
Let N be the numeric equivalent of ch
i++ // to account for the character, ch
if there are no addition characters in the string:
Add N to arabic
else: // Try pairing the ch with the next character
Let N2 be the numeric equivalent of the NEXT character
If N < N2: // Evaluate the characters as a pair
Add (N2 - N) to arabic
i++ // to account for the extra character
else:
Add N to arabic
This algorithm does not take into account that the string might not be a legal Roman numeral. If a character in the string is not one of the characters M, D, C, L, X, V, or I, then a NumberFormatException must be thrown.
The job of converting an int into an equivalent Roman numeral is handled in my toString() method. The exercise shows how to write this method as a long sequence of while loops. Consider the loop
while (N >= 1000) {
roman += "M";
N -= 1000;
}
After this loop, all the 1000's in N have been converted to M's in roman, and we can be sure that N is 999 or less. So what's left of N can be expressed in terms of the smaller numbers in the table: 900, 500, 400, and so on. Each of these numbers must be processed by a while loop. Note that the numbers in these loops must be in decreasing order for this to work.
However, all thee loops in this algorithm have the same form. They just use different numbers and letters. In my program, I use two arrays to store the numbers and letters from the table:
private static int[] numbers = { 1000, 900, 500, 400, 100, 90,
50, 40, 10, 9, 5, 4, 1 };
private static String[] letters = { "M", "CM", "D", "CD", "C", "XC",
"L", "XL", "X", "IX", "V", "IV", "I" };
For each index i, numbers[i] is the int equivalent of the Roman numeral letters[i]. All the processing can then be done with a for loop that does all the required while loops one after the other:
public String toString() {
// Return the standard representation of this Roman numeral.
String roman = ""; // The roman numeral.
int N = num; // N represents the part of num that still has
// to be converted to Roman numeral representation.
for (int i = 0; i < numbers.length; i++) {
while (N >= numbers[i]) {
roman += letters[i];
N -= numbers[i];
}
}
return roman;
}
An algorithm for the main program is given by:
while (true):
Prompt the user for input
If the first thing on the line is the end-of-line:
break
else if the first character on the line is a digit:
Let arabic = TextIO.getlnInt()
Let roman = new RomanNumeral(arabic)
Print out roman.toString()
else:
Let str = TextIO.getln();
Let roman = new RomanNumeral(str);
Print out roman.toInt();
This algorithm ignores the possiblilty that the user's input might be illegal. If it is, then the RomanNumeral constructor will throw a NumberFormatException. This exception must be caught and handled. With this in mind, the algorithm becomes:
while (true):
Prompt the user for input
If the first thing on the line is the end-of-line:
break
else if the first character on the line is a digit:
Let arabic = TextIO.getlnInt()
try {
Let roman = new RomanNumeral(arabic)
Print out roman.toString()
}
catch (NumberFormatException e) {
Print an error message
}
else:
Let str = TextIO.getln();
try {
Let roman = new RomanNumeral(str);
Print out roman.toInt();
}
catch (NumberFormatException e) {
Print an error message
}
This can be easily coded into Java. By the way, the test as to whether the first character on the input line is a digit can be performed using the standard boolean-valued function Character.isDigit(ch), which returns true if the character ch is a digit.
The Roman numerals class:
/**
* An object of type RomanNumeral is an integer between 1 and 3999. It can
* be constructed either from an integer or from a string that represents
* a Roman numeral in this range. The function toString() will return a
* standardized Roman numeral representation of the number. The function
* toInt() will return the number as a value of type int.
*/
public class RomanNumeral {
private final int num; // The number represented by this Roman numeral.
/* The following arrays are used by the toString() function to construct
the standard Roman numeral representation of the number. For each i,
the number numbers[i] is represented by the corresponding string, letters[i].
*/
private static int[] numbers = { 1000, 900, 500, 400, 100, 90,
50, 40, 10, 9, 5, 4, 1 };
private static String[] letters = { "M", "CM", "D", "CD", "C", "XC",
"L", "XL", "X", "IX", "V", "IV", "I" };
/**
* Constructor. Creates the Roman number with the int value specified
* by the parameter. Throws a NumberFormatException if arabic is
* not in the range 1 to 3999 inclusive.
*/
public RomanNumeral(int arabic) {
if (arabic < 1)
throw new NumberFormatException("Value of RomanNumeral must be positive.");
if (arabic > 3999)
throw new NumberFormatException("Value of RomanNumeral must be 3999 or less.");
num = arabic;
}
/*
* Constructor. Creates the Roman number with the given representation.
* For example, RomanNumeral("xvii") is 17. If the parameter is not a
* legal Roman numeral, a NumberFormatException is thrown. Both upper and
* lower case letters are allowed.
*/
public RomanNumeral(String roman) {
if (roman.length() == 0)
throw new NumberFormatException("An empty string does not define a Roman numeral.");
roman = roman.toUpperCase(); // Convert to upper case letters.
int i = 0; // A position in the string, roman;
int arabic = 0; // Arabic numeral equivalent of the part of the string that has
// been converted so far.
while (i < roman.length()) {
char letter = roman.charAt(i); // Letter at current position in string.
int number = letterToNumber(letter); // Numerical equivalent of letter.
if (number < 0)
throw new NumberFormatException("Illegal character \"" + letter + "\" in roman numeral.");
i++; // Move on to next position in the string
if (i == roman.length()) {
// There is no letter in the string following the one we have just processed.
// So just add the number corresponding to the single letter to arabic.
arabic += number;
}
else {
// Look at the next letter in the string. If it has a larger Roman numeral
// equivalent than number, then the two letters are counted together as
// a Roman numeral with value (nextNumber - number).
int nextNumber = letterToNumber(roman.charAt(i));
if (nextNumber > number) {
// Combine the two letters to get one value, and move on to next position in string.
arabic += (nextNumber - number);
i++;
}
else {
// Don't combine the letters. Just add the value of the one letter onto the number.
arabic += number;
}
}
} // end while
if (arabic > 3999)
throw new NumberFormatException("Roman numeral must have value 3999 or less.");
num = arabic;
} // end constructor
/**
* Find the integer value of letter considered as a Roman numeral. Return
* -1 if letter is not a legal Roman numeral. The letter must be upper case.
*/
private int letterToNumber(char letter) {
switch (letter) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return -1;
}
}
/**
* Return the standard representation of this Roman numeral.
*/
public String toString() {
String roman = ""; // The roman numeral.
int N = num; // N represents the part of num that still has
// to be converted to Roman numeral representation.
for (int i = 0; i < numbers.length; i++) {
while (N >= numbers[i]) {
roman += letters[i];
N -= numbers[i];
}
}
return roman;
}
/**
* Return the value of this Roman numeral as an int.
*/
public int toInt() {
return num;
}
} // end class RomanNumeral
The main program class:
/**
* This program will convert Roman numerals to ordinary arabic numerals
* and vice versa. The user can enter a numerals of either type. Arabic
* numerals must be in the range from 1 to 3999 inclusive. The user ends
* the program by entering an empty line.
*/
public class RomanConverter {
public static void main(String[] args) {
TextIO.putln("Enter a Roman numeral and I will convert it to an ordinary");
TextIO.putln("arabic integer. Enter an integer in the range 1 to 3999");
TextIO.putln("and I will convert it to a Roman numeral. Press return when");
TextIO.putln("you want to quit.");
while (true) {
TextIO.putln();
TextIO.put("? ");
/* Skip past any blanks at the beginning of the input line.
Break out of the loop if there is nothing else on the line. */
while (TextIO.peek() == ' ' || TextIO.peek() == '\t')
TextIO.getAnyChar();
if ( TextIO.peek() == '\n' )
break;
/* If the first non-blank character is a digit, read an arabic
numeral and convert it to a Roman numeral. Otherwise, read
a Roman numeral and convert it to an arabic numeral. */
if ( Character.isDigit(TextIO.peek()) ) {
int arabic = TextIO.getlnInt();
try {
RomanNumeral N = new RomanNumeral(arabic);
TextIO.putln(N.toInt() + " = " + N.toString());
}
catch (NumberFormatException e) {
TextIO.putln("Invalid input.");
TextIO.putln(e.getMessage());
}
}
else {
String roman = TextIO.getln();
try {
RomanNumeral N = new RomanNumeral(roman);
TextIO.putln(N.toString() + " = " + N.toInt());
}
catch (NumberFormatException e) {
TextIO.putln("Invalid input.");
TextIO.putln(e.getMessage());
}
}
} // end while
TextIO.putln("OK. Bye for now.");
} // end main()
} // end class RomanConverter