Unions and Generics Challenge
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: A.addAll(B) computes the union of A and B; A.retainAll(B) computes the intersection of A and B; and A.removeAll(B) computes 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 sets of type TreeSet<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.)
I/O Format
The first line of input will contain n, the number of test cases. n cases will follow, where each case consists of a line with a set operation. Print out the result of each operation on its own line.
This program would be easier to write if we could assume that the user's input was in the correct format. In this challenge you can, but if you create the program for other users, you need 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 Subsection 8.2.2. We can use the function TextIO.peek() to look ahead at the next character in the user's input. We need to be able to skip past any blanks in the input. Instead of writing my own method to do that, I use the method TextIO.skipBlanks() in my program.
My program uses 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 specific type of error that occurs in this program.
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 basic 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.
In the program, 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.
Challenge
Output the results of the set operations given as input.
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.
Comments
Goh Hong Yi
May 4, 4:57 AMHow do I read the '[' that begins the set?
I have tried using nextInt() and keep getting an inputmismatchexception.
Learneroo
May 4, 5:00 PMThere are many other scanner methods, such as
.next(). See the Learneroo Scanner reference or the official Scanner docs.