Solution for
Programming Exercise 9.3
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 9.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:
Discussion
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 Solution
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" };
public RomanNumeral(int arabic) {
// 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.
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;
}
public RomanNumeral(String roman) {
// 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.
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
private int letterToNumber(char letter) {
// 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.
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;
}
}
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;
}
public int toInt() {
// Return the value of this Roman numeral as an int.
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
[ Exercises
| Chapter Index
| Main Index
]
