Solution for
Programming Exercise 12.2
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 12.2:
In mathematics, several operations are defined on sets.
The union of two sets A and B is a set
that contains all the elements that are in A together with all the
elements that are in B. The intersection
of A and B is the set that contains elements that are in both
A and B. The difference of A and B
is the set that contains all the elements of A except
for those elements that are also in B.
Suppose that A and B are variables of type set in
Java. The mathematical operations on A and B can be computed
using methods from the Set interface. In particular:
The set A.addAll(B) is the union of A and B;
A.retainAll(B) is the intersection of A and B;
and A.removeAll(B) is the difference of A and B.
(These operations change the contents of the set A, while the mathematical
operations create a new set without changing A, but that difference
is not relevant to this exercise.)
For this exercise, you should write a program that can be used as
a "set calculator" for simple operations on sets of non-negative integers.
(Negative integers are not allowed.) A set of such
integers will be represented as a list of integers, separated by commas and, optionally, spaces
and enclosed in square brackets. For example: [1,2,3]
or [17, 42, 9, 53,108]. The characters
+, *, and - will be used for the union,
intersection, and difference operations. The user of the program will
type in lines of input containing two sets, separated by an operator.
The program should perform the operation and print the resulting set.
Here are some examples:
Input Output
------------------------- -------------------
[1, 2, 3] + [3, 5, 7] [1, 2, 3, 5, 7]
[10,9,8,7] * [2,4,6,8] [8]
[ 5, 10, 15, 20 ] - [ 0, 10, 20 ] [5, 15]
To represent sets of non-negative integers, use TreeSets containing
objects belonging to the wrapper class Integer. Read the user's
input, create two TreeSets, and use the appropriate TreeSet
method to perform the requested operation on the two sets.
Your program should be able to read and process any number of lines of
input. If a line contains a syntax error, your program should
not crash. It should report the error and move on to the next
line of input. (Note: To print out a Set, A,
of Integers, you can just say System.out.println(A).
I've chosen the syntax for sets to be the same as that used by the
system for outputting a set.)
Discussion
This program would be much easier to write if
we could assume that the user's input was in the correct format.
Unfortunately, the exercise says that we have to detect errors
in the user's input and handle them by printing error messages.
To do this we have to constantly look ahead while reading the
user's input, to see whether the input agrees with what we are
expecting. The techniques for doing this were covered for the
example LengthConverter2.java
from Section 9.2. We can use
the function TextIO.peek() to look ahead at the next
character in the user's input. The user can put any number of
blanks between two items in the input, so before looking ahead
at the next item, we should always skip over any blanks in
the input. Since this has to be done many times, it's useful
to define a subroutine to do it. The subroutine skips over
tab characters, represented by '\t', as well as blanks:
static void skipBlanks() {
while (TextIO.peek() == ' ' || TextIO.peek() == '\t')
TextIO.getAnyChar();
}
My program uses another technique from Chapter 9 -- exceptions -- to
handle the errors. Exceptions make it possible to organize the
error-handling code in a straightforward way. When an error is
discovered, an exception is thrown. The main program uses
a try...catch statement to try to process one line
of input. If an error occurs, the program does not crash.
The error is caught, an error message is printed, and the
program continues. I throw an error of type IllegalArgumentException
when an error is found. This exception is a standard part of Java,
but it might be better style to define a new error class to represent
the error.
My program uses a method named calc() to read and process
one line of input. This method in turn uses another method,
readSet() to read each of the two sets of integers from
the input line. Without error handling, an algorithm for readSet()
would be:
Start with an empty set.
Read the '[' that begins the set.
Repeat:
Read the next number and add it to the set.
If the next character is ']':
break.
Read the comma that separates one number from the next.
Read the ']'.
Return the set.
To turn this into a robust routine, we just have to check, before
reading anything, that the next character is legal. If not, throw
an exception. This adds a lot of code, but the nice thing about
throwing exceptions is that it doesn't disturb the logical flow of
the routine.
There is one possible bug in the algorithm. It assumes that there
is at least one number in the set. But in mathematics, a set can be
empty. I decided to allow for the possibility of empty sets in my
program. See the solution, below.
An algorithm for the calc() method is even more straightforward.
Again, the algorithm ignores the possibility of errors:
Read the first set, A.
Read the operator.
Read the second set, B.
if the operator is '+'
A.addAll(B) // Sets A equal to the union of A and B.
else if the operator is '*'
A.retainAll(B) // Sets A to the intersection.
else
A.removeAll(B) // Sets A to the difference.
Print A.
An error check has to be added to make sure that there is a legal operator
in the correct position. I also add an error check to make sure that there
is no extra data on the line.
The Solution
/*
This program is a very simple "set calculator" that can compute
the intersection, union, and set difference of two sets of
non-negative integers. Each line of the user's input contains two
such sets, separated by one of the operators +, *, or -, standing
for union, intersection, and set difference respectively. A set
must be given in the form of a list of non-negative integers, separated
by commas, and enclosed in square brackets. For example:
[1, 2, 3] + [4, 3, 10, 0]. Spaces can occur anywhere in the input.
If an error is found in the input, the program will report it.
The program ends when the user inputs an empty line.
This program is mainly a demonstration of Sets.
*/
import java.util.TreeSet;
public class SetCalc {
public static void main(String[] args) {
System.out.println("This program will compute union, intersection,");
System.out.println("and set difference of sets of integers.");
System.out.println("");
System.out.println("");
System.out.println("Enter set computations (press return to end):");
while (true) {
char ch;
System.out.print("\n? ");
skipBlanks();
if (TextIO.peek() == '\n') {
// The input line is empty.
// Exit the loop and end the program.
break;
}
try {
calc(); // Reads and processes one line of input.
}
catch (IllegalArgumentException e) {
// An error was found in the input line.
System.out.println("Error in input: " + e.getMessage());
System.out.print("Discarding input: ");
}
do { // Copy extra characters on line to output. If there
// was no error, then the only character that is copied
// is the end-of-line character.
ch = TextIO.getAnyChar();
System.out.print(ch);
} while (ch != '\n');
}
} // end main()
static void calc() {
// Read a line of input, consisting of two sets separated by
// an operator. Perform the operation and output the value.
// If any syntax error is found in the input, an
// IllegalArgumentException is thrown
TreeSet A, B; // The two sets of integers.
char op; // The operator, +, *, or -.
A = readSet(); // Read the first set.
skipBlanks();
if (TextIO.peek() != '*' && TextIO.peek() != '+'
&& TextIO.peek() != '-')
throw new IllegalArgumentException(
"Expected *, +, or - after first set.");
op = TextIO.getAnyChar(); // Read the operator.
B = readSet(); // Read the second set.
skipBlanks();
if (TextIO.peek() != '\n')
throw new IllegalArgumentException("Extra unexpected input.");
// Perform the operation. This modifies set A to represent
// the answer. Display the answer by printing out A. The
// output format for a set of integers is the same as the
// input format used by this program.
if (op == '+')
A.addAll(B); // Union.
else if (op == '*')
A.retainAll(B); // Intersection.
else
A.removeAll(B); // Set difference.
System.out.print("Value: " + A);
} // end calc()
static TreeSet readSet() {
// Reads a set of non-negative integers from standard input,
// and stores them in a TreeSet that contains objects belonging
// to the wrapper class Integer. The set must be enclosed
// between square brackets and must contain a list of zero or
// more non-negative integers, separated by commas. Spaces
// are allowed anywhere. If the input is not of the correct
// form, an IllegalArgumentException is thrown.
TreeSet set = new TreeSet(); // The set that will be read.
skipBlanks();
if (TextIO.peek() != '[')
throw new IllegalArgumentException("Expected '[' at start of set.");
TextIO.getAnyChar(); // Read the '['.
skipBlanks();
if (TextIO.peek() == ']') {
// The set has no integers. This is the empty set, which
// is legal. Return the value.
TextIO.getAnyChar(); // Read the ']'.
return set;
}
while (true) {
// Read the next integer and add it to the set.
skipBlanks();
if (! Character.isDigit(TextIO.peek()))
throw new IllegalArgumentException("Expected an integer.");
int n = TextIO.getInt(); // Read the integer.
set.add( new Integer(n) );
skipBlanks();
if (TextIO.peek() == ']')
break; // ']' marks the end of the set.
else if (TextIO.peek() == ',')
TextIO.getAnyChar(); // Read a comma and continue.
else
throw new IllegalArgumentException("Expected ',' or ']'.");
}
TextIO.getAnyChar(); // Read the ']' that ended the set.
return set;
} // end readSet()
static void skipBlanks() {
while (TextIO.peek() == ' ' || TextIO.peek() == '\t')
TextIO.getAnyChar();
}
} // end class SetCalc
[ Exercises
| Chapter Index
| Main Index
]
