Programming Exercises
For Chapter 12
THIS PAGE CONTAINS programming exercises based on
material from Chapter 12 of this on-line
Java textbook. Each exercise has a link to a discussion of one possible solution of that
exercise.
Exercise 12.1:
In Section 12.2, I mentioned that a
LinkedList can be used as a queue by using the
addLast() and removeFirst() methods to enqueue
and dequeue items. But, if we are going to work with queues,
it's better to have a Queue class. The data for the
queue could still be represented as a LinkedList,
but the LinkedList object would be hidden as a
private instance variable in the Queue object.
Use this idea to write a generic Queue class for
representing queues of Objects. Also write a generic
Stack class that uses either a LinkedList
or an ArrayList to store its data. (Stacks and queues
were introduced in Section 11.3.)
See the solution!
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.)
See the solution!
Exercise 12.3:
The fact that Java has a HashMap class means that no Java
programmer has to write an implementation of hash tables from
scratch -- unless, of course, you are a computer science student.
Write an implementation of hash tables from scratch. Define the
following methods: get(key), put(key,value),
remove(key), containsKey(key), and size(). Do not
use any of Java's generic data structures. Assume that both
keys and values are of type Object, just as for HashMaps.
Every Object has a hash code, so at least you don't have to
define your own hash functions. Also, you do not have to
worry about increasing the size of the table when it becomes too full.
You should also write a short program to test your solution.
See the solution!
Exercise 12.4:
A predicate is a boolean-valued function
with one parameter. Some languages use predicates in
generic programming. Java doesn't, but this exercise looks
at how predicates might work in Java.
In Java, we could use "predicate objects" by defining an
interface:
public interface Predicate {
public boolean test(Object obj);
}
The idea is that an object that implements this interface knows
how to "test" objects in some way. Define a class
Predicates that contains the following generic methods
for working with predicate objects:
public static void remove(Collection coll, Predicate pred)
// Remove every object, obj, from coll for which
// pred.test(obj) is true.
public static void retain(Collection coll, Predicate pred)
// Remove every object, obj, from coll for which
// pred.test(obj) is false. (That is, retain the
// objects for which the predicate is true.)
public static List collect(Collection coll, Predicate pred)
// Return a List that contains all the objects, obj,
// from the collection, coll, such that pred.test(obj)
// is true.
public static int find(ArrayList list, Predicate pred)
// Return the index of the first item in list
// for which the predicate is true, if any.
// If there is no such item, return -1.
(In C++, methods similar to these are included as a standard
part of the generic programming framework.)
See the solution!
Exercise 12.5:
One of the examples in Section 12.4 concerns the
problem of making an index for a book. A related problem is making
a concordance for a document. A
concordance lists every word that occurs in the document, and for each
word it gives the line number of every line in the document where
the word occurs. All the subroutines for creating an index
that were presented in Section 12.4 can also be used to create
a concordance. The only real difference is that the integers
in a concordance are line numbers rather than page numbers.
Write a program that can create a concordance. The document should
be read from an input file, and the concordance data should be written
to an output file. The names of the input file and output file should
be specified as command line arguments when the program is run.
You can use the indexing subroutines from Section 12.4, modified to
write the data to a file instead of to System.out. You
will also need to make the subroutines static. If you need
some help with using files and command-line arguments, you can find an
example in the
sample program WordCount.java,
which was also discussed in Section 12.4.
As you read the file, you want to take each word that you encounter
and add it to the concordance along with the current line number.
Your program will need to keep track of the line number. The end of each line
in the file is marked by the newline character, '\n'. Every time you encounter
this character, add one to the line number. One warning: The method
in.eof(), which is defined in the TextReader, skips over
end-of-lines. Since you don't want to skip end-of-line characters, you
should not use in.eof() -- at least, you should not use it
in the same way that it is used in the program WordCount.java.
The function in.peek() from the TextReader class returns
the nul character '\0' at the end of the file. Use this function
instead of in.eof() to test for end-of-file.
Because it is so common, don't include the word "the" in your
concordance. Also, do not include words that have length less than 3.
See the solution!
Exercise 12.6:
The sample program SimpleParser5.java
from Section 12.4 can handle expressions that contain
variables, numbers, operators, and parentheses. Extend this program so that
it can also handle the standard mathematical functions sin, cos,
tan, abs, sqrt, and log. For example, the program should
be able to evaluate an expression such as sin(3*x-7)+log(sqrt(y)),
assuming that the variables x and y have been given values.
In the original program, a symbol table holds a value for each variable that
has been defined. In your program, you should add another type of symbol to
the table to represent standard functions. You can use objects belonging
to the following class:
class StandardFunction {
// An object of this class represents
// one of the standard functions.
static final int SIN = 0, COS = 1, // Code numbers for each
TAN = 2, ABS = 3, // of the functions.
SQRT = 4, LOG = 5;
int functionCode; // Tells which function this is.
// The value is one of the above codes.
StandardFunction(int code) {
// Constructor creates the standard function specified
// by the given code, which should be one of the
// above code numbers.
functionCode = code;
}
double evaluate(double x) {
// Finds the value of this function for the
// specified parameter value, x.
switch(functionCode) {
case SIN:
return Math.sin(x);
case COS:
return Math.cos(x);
case TAN:
return Math.tan(x);
case ABS:
return Math.abs(x);
case SQRT:
return Math.sqrt(x);
default:
return Math.log(x);
}
}
} // end class StandardFunction
Add a symbol to the symbol table to represent each function.
The key is the name of the function and the value is an object
of type StandardFunction that represents the function.
For example:
symbolTable.put("sin", new StandardFunction(StandardFunction.SIN));
In your parser, when you encounter a word, you have to be able to
tell whether it's a variable or a standard function. Look up the
word in the symbol table. If the associated value is non-null
and is of type Double, then the word is a variable.
If it is of type StandardFunction, then
the word is a function. Remember that you can test the type
of an object using the instanceof operator.
For example: if (obj instanceof Double)
See the solution!
