53 Javanotes 9.0, Exercises for Chapter 10
Programming Exercises for Chapter 10
Exercise 10.1:
Rewrite the PhoneDirectory class
from Subsection 7.5.2 so that it uses a TreeMap
to store directory entries, instead of an array. (Doing this was suggested
in Subsection 10.3.1.) You should also write a short program
to test the class.
Exercise 10.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:
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.) For input and output, a set of such integers will be written 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.print(A). I’ve chosen
the syntax for sets to be the same as that used by the system for outputting a
set.)
Exercise 10.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, that programmer is a
computer science student.
For this exercise, you should write a hash table in which both the keys and the values are of
type String. (This is not an exercise in generic programming;
do not try to write a generic class.)
Write an implementation of hash tables from scratch. Define the following
methods: get(key), put(key,value), remove(key),
containsKey(key), and size().
Remember that every object, obj, has a method obj.hashCode()
that can be used for computing a hash code for the object,
so at least you don’t have to define your own hash function.
Do not use any of Java’s built-in generic types; create your own linked
lists using nodes as covered in Subsection 9.2.2. However,
you are not required to increase the size of the table when
it becomes too full.
You should also write a short program to test your solution.
Exercise 10.4:
A predicate is a boolean-valued function with one parameter.
Java has the parameterized functional interface Predicate<T>,
from package java.util.function,
to represent predicates. The definition of Predicate<T> could be:
public interface Predicate<T> {
public boolean test( T obj );
}
The idea is that an object that implements this interface knows how to
“test” objects of type T
in some way. Java already has some methods that use predicates, such as the
removeIf(p) method that is defined for any Collection.
(See Subsection 10.6.1). However, this exercise asks you to write
a few similar methods yourself. Define a class that contains
the following generic static methods for working with predicate objects.
The name of the class should be Predicates, in analogy
with the standard class Collections that provides various
static methods for working with collections. You should
not use the stream API for this exercise.
public static <T> void remove(Collection<T> coll, Predicate<T> pred) // Remove every object, obj, from coll for which pred.test(obj) // is true. (This does the same thing as coll.removeIf(pred).) public static <T> void retain(Collection<T> coll, Predicate<T> 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 <T> List<T> collect(Collection<T> coll, Predicate<T> pred) // Return a List that contains all the objects, obj, // from the collection, coll, such that pred.test(obj) // is true. public static <T> int find(ArrayList<T> list, Predicate<T> 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.
Exercise 10.5:
This is a short exercise in using the stream API.
Suppose that the class Score is defined as
/**
* Data for one student about a score on a test.
*/
private record ScoreInfo(
String lastName,
String firstName,
int score
) { };
defined here as a record class for convenience (see Section 7.4).
And suppose that scoreData is an array of ScoreInfos
containing information about the scores of students on a test.
Use the stream API to do each of the following tasks:
- print the number of students (without using scoreData.length)
- print the average score for all of the students
- print the number of students who got an A (score greater than or equal to 90)
- use the collect() stream operation to create
a List<String> that contains the names of students whose score was less than 70;
the names should be in the form first name followed by last name - print the names from the List that was generated in the previous task
- print out the students’ names and scores, ordered by last name
- print out the students’ names and scores, ordered by score
You can put all of the code in main() routine and include
ScoreInfo as a nested class.
Do not use any for loops or other control structures. Do everything
using the stream API. For testing your code, you can use this array:
private static ScoreInfo[] scoreData = new ScoreInfo[] {
new ScoreInfo("Smith","John",70),
new ScoreInfo("Doe","Mary",85),
new ScoreInfo("Page","Alice",82),
new ScoreInfo("Cooper","Jill",97),
new ScoreInfo("Flintstone","Fred",66),
new ScoreInfo("Rubble","Barney",80),
new ScoreInfo("Smith","Judy",48),
new ScoreInfo("Dean","James",90),
new ScoreInfo("Russ","Joe",55),
new ScoreInfo("Wolfe","Bill",73),
new ScoreInfo("Dart","Mary",54),
new ScoreInfo("Rogers","Chris",78),
new ScoreInfo("Toole","Pat",51),
new ScoreInfo("Khan","Omar",93),
new ScoreInfo("Smith","Ann",95)
};
Exercise 10.6:
An example in
Subsection 10.4.2 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
Subsection 10.4.2 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. You can use the indexing
subroutines from Subsection 10.4.2, modified to write the data to TextIO
instead of to System.out. (You will need to make these subroutines
static.) The input and output files should be selected by the user when
the program is run. The sample program WordCount.java,
from Subsection 10.4.4, can be used as a model of how to use files.
That program also has a useful subroutine that reads one word from input.
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. Keeping track of
the line numbers is one of the trickiest parts of the problem. In an input file,
the end of each line in the file is
marked by the newline character, ‘\n’. Every time you encounter this
character, you have to add one to the line number. WordCount.java
ignores ends of lines. Because you need to
find and count the end-of-line characters, your program cannot
process the input file in exactly the same way as does WordCount.java.
Also, you will need to detect the end of the file. The function
TextIO.peek(), which is used to look ahead at the next character
in the input, returns the value TextIO.EOF at end-of-file,
after all the characters in the file have been read.
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 10.7:
The sample program
SimpleInterpreter.java from Subsection 10.4.1
can carry out commands of the form “let variable = expression” or “print expression”.
That program can handle expressions that contain variables,
numbers, operators, and parentheses. Extend the 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. Note that the name of a function
must be followed by an expression that is enclosed in parentheses.
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 the following nested
enumerated type and class for this purpose:
private enum Functions { SIN, COS, TAN, ABS, SQRT, LOG }
/**
* An object of this class represents one of the standard functions.
*/
private static class StandardFunction {
/**
* Tells which function this is.
*/
Functions functionCode;
/**
* Constructor creates an object to represent one of
* the standard functions
* @param code which function is represented.
*/
StandardFunction(Functions code) {
functionCode = code;
}
/**
* Finds the value of this function for the specified
* parameter value, x.
*/
double evaluate(double x) {
// (This uses the "switch expression" syntax)
return switch(functionCode) {
case SIN -> Math.sin(x);
case COS -> Math.cos(x);
case TAN -> Math.tan(x);
case ABS -> Math.abs(x);
case SQRT -> Math.sqrt(x);
default -> 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(Function.SIN));
In SimpleInterpreter.java, the symbol table is a map of type
HashMap<String,Double>. It’s not legal to
use a StandardFunction as the value in such a map,
so you will have to change the type of the map. The map has to hold two
different types of objects. The easy way to make this possible is to create
a map of type HashMap<String,Object>.
(A better way is to create a general type to represent objects that
can be values in the symbol table, and to define two subclasses of that
class, one to represent variables and one to represent standard functions,
but for this exercise, you should do it the easy way.)
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 object 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).