> ### 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 ]