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.)
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.)
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.
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.)
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.
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 StandardFunctionAdd 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)
[ Chapter Index | Main Index ]