## 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 aLinkedListcan be used as a queue by using theaddLast()andremoveFirst()methods to enqueue and dequeue items. But, if we are going to work with queues, it's better to have aQueueclass. The data for the queue could still be represented as aLinkedList, but theLinkedListobject would be hidden as a private instance variable in theQueueobject. Use this idea to write a genericQueueclass for representing queues ofObjects. Also write a genericStackclass that uses either aLinkedListor anArrayListto 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 Aexceptfor those elements that are also in B.Suppose that

AandBare variables of typesetin Java. The mathematical operations onAandBcan be computed using methods from theSetinterface. In particular: The setA.addAll(B)is theunionofAandB;A.retainAll(B)is theintersectionofAandB; andA.removeAll(B)is thedifferenceofAandB. (These operations change the contents of the setA, while the mathematical operations create a new set without changingA, 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

TreeSetscontaining objects belonging to the wrapper classInteger. Read the user's input, create twoTreeSets, and use the appropriateTreeSetmethod 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 aSet,A, ofIntegers, you can just saySystem.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 aHashMapclass 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), andsize(). Do not useanyof Java's generic data structures. Assume that both keys and values are of typeObject, just as forHashMaps. EveryObjecthas a hash code, so at least you don't have to define your own hash functions. Also, you donothave 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

Predicatesthat 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 subroutinesstatic. 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 theTextReader, skips over end-of-lines. Since you don't want to skip end-of-line characters, you should not usein.eof()-- at least, you should not use it in the same way that it is used in the programWordCount.java. The functionin.peek()from theTextReaderclass returns the nul character '\0' at the end of the file. Use this function instead ofin.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 functionssin,cos,tan,abs,sqrt, andlog. For example, the program should be able to evaluate an expression such assin(3*x-7)+log(sqrt(y)), assuming that the variablesxandyhave 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

StandardFunctionthat 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 typeStandardFunction, then the word is a function. Remember that you can test the type of an object using theinstanceofoperator. For example:if (obj instanceof Double)

[ Chapter Index | Main Index ]