Wrap-Up

Write a program that concatenates two linked-list objects of characters. Class ListConcatenate should include a method concatenate that takes references to both list objects as arguments and concatenates the second list to the first list.

Write a program that merges two ordered-list objects of integers into a single ordered-list object of integers. Method merge of class ListMerge should receive references to each of the list objects to be merged and return a reference to the merged list object.

Write a program that inserts 25 random integers from 0 to 100 in order into a linked-list object. The program should calculate the sum of the elements and the floating-point average of the elements.

Write a program that creates a linked-list object of 10 characters, then creates a second list object containing a copy of the first list, but in reverse order.

Write a program that inputs a line of text and uses a stack object to print the words of the line in reverse order.

Write a program that uses a stack to determine whether a string is a palindrome (i.e., the string is spelled identically backward and forward). The program should ignore spaces and punctuation.

Stacks are used by compilers to help in the process of evaluating expressions and generating machine-language code. In this and the next exercise, we investigate how compilers evaluate arithmetic expressions consisting only of constants, operators and parentheses.

Humans generally write expressions like 3 + 4 and 7 / 9 in which the operator (+ or / here) is written between its operandsthis is called infix notation. Computers "prefer" postfix notation, in which the operator is written to the right of its two operands. The preceding infix expressions would appear in postfix notation as 3 4 + and 7 9 /, respectively.

To evaluate a complex infix expression, a compiler would first convert the expression to postfix notation and evaluate the postfix version. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack object in support of its operation, but each uses the stack for a different purpose.

In this exercise, you will write a Java version of the infix-to-postfix conversion algorithm. In the next exercise, you will write a Java version of the postfix expression evaluation algorithm. In a later exercise, you will discover that code you write in this exercise can help you implement a complete working compiler.

Write class InfixToPostfixConverter to convert an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers such as

to a postfix expression. The postfix version of the preceding infix expression is (note that no parentheses are needed)

The program should read the expression into StringBuffer infix and use one of the stack classes implemented in this chapter to help create the postfix expression in StringBuffer postfix. The algorithm for creating a postfix expression is as follows:

1. Push a left parenthesis '(' on the stack.
2. Append a right parenthesis ')' to the end of infix.
3. While the stack is not empty, read infix from left to right and do the following:

   If the current character in infix is a digit, append it to postfix.

   If the current character in infix is a left parenthesis, push it onto the stack.

   If the current character in infix is an operator:

   Pop operators (if there are any) at the top of the stack while they have equal or higher precedence than the current operator, and append the popped operators to postfix.

   Push the current character in infix onto the stack.

   If the current character in infix is a right parenthesis:

   Pop operators from the top of the stack and append them to postfix until a left parenthesis is at the top of the stack.

   Pop (and discard) the left parenthesis from the stack.

The following arithmetic operations are allowed in an expression:

The stack should be maintained with stack nodes that each contain an instance variable and a reference to the next stack node. Some of the methods you may want to provide are as follows:

1. Method convertToPostfix, which converts the infix expression to postfix notation.
2. Method isOperator, which determines whether c is an operator.
3. Method precedence, which determines whether the precedence of operator1 (from the infix expression) is less than, equal to or greater than the precedence of operator2 (from the stack). The method returns true if operator1 has lower precedence than operator2. Otherwise, false is returned.
4. Method stackTop (this should be added to the stack class), which returns the top value of the stack without popping the stack.

Write class PostfixEvaluator, which evaluates a postfix expression such as

The program should read a postfix expression consisting of digits and operators into a StringBuffer. Using modified versions of the stack methods implemented earlier in this chapter, the program should scan the expression and evaluate it (assume it is valid). The algorithm is as follows:

1. Append a right parenthesis ')' to the end of the postfix expression. When the right-parenthesis character is encountered, no further processing is necessary.
2. When the right-parenthesis character has not been encountered, read the expression from left to right.

   If the current character is a digit, do the following:

   Push its integer value on the stack (the integer value of a digit character is its value in the computer's character set minus the value of '0' in Unicode).

   Otherwise, if the current character is an operator:

   Pop the two top elements of the stack into variables x and y.

   Calculate y operator x.

   Push the result of the calculation onto the stack.

3. When the right parenthesis is encountered in the expression, pop the top value of the stack. This is the result of the postfix expression.

[Note: In b) above (based on the sample expression at the beginning of this exercise), if the operator is '/', the top of the stack is 2 and the next element in the stack is 8, then pop 2 into x, pop 8 into y, evaluate 8 / 2 and push the result, 4, back on the stack. This note also applies to operator '-'.] The arithmetic operations allowed in an expression are:

The stack should be maintained with one of the stack classes introduced in this chapter. You may want to provide the following methods:

1. Method evaluatePostfixExpression, which evaluates the postfix expression.
2. Method calculate, which evaluates the expression op1 operator op2.
3. Method push, which pushes a value onto the stack.
4. Method pop, which pops a value off the stack.
5. Method isEmpty, which determines whether the stack is empty.
6. Method printStack, which prints the stack.

Modify the postfix evaluator program of Exercise 17.13 so that it can process integer operands larger than 9.

(Supermarket Simulation)Write a program that simulates a checkout line at a supermarket. The line is a queue object. Customers (i.e., customer objects) arrive in random integer intervals of from 1 to 4 minutes. Also, each customer is serviced in random integer intervals of from 1 to 4 minutes. Obviously, the rates need to be balanced. If the average arrival rate is larger than the average service rate, the queue will grow infinitely. Even with "balanced" rates, randomness can still cause long lines. Run the supermarket simulation for a 12-hour day (720 minutes), using the following algorithm:

1. Choose a random integer between 1 and 4 to determine the minute at which the first customer arrives.
2. At the first customer's arrival time, do the following:

   Determine customer's service time (random integer from 1 to 4).

   Begin servicing the customer.

   Schedule arrival time of next customer (random integer 1 to 4 added to the current time).

3. For each minute of the day, consider the following:

   If the next customer arrives, proceed as follows:

   Say so.

   Enqueue the customer.

   Schedule the arrival time of the next customer.

   If service was completed for the last customer, do the following:

   Say so.

   Dequeue next customer to be serviced.

   Determine customer's service completion time (random integer from 1 to 4 added to the current time).

Now run your simulation for 720 minutes and answer each of the following:

1. What is the maximum number of customers in the queue at any time?
2. What is the longest wait any one customer experiences?
3. What happens if the arrival interval is changed from 1 to 4 minutes to 1 to 3 minutes?

Modify Fig. 17.17 and Fig. 17.18 to allow the binary tree to contain duplicates.

Write a program based on the program of Fig. 17.17 and Fig. 17.18 that inputs a line of text, tokenizes the sentence into separate words (you might want to use the StreamTokenizer class from the java.io package), inserts the words in a binary search tree and prints the inorder, preorder and postorder traversals of the tree.

In this chapter, we saw that duplicate elimination is straightforward when creating a binary search tree. Describe how you would perform duplicate elimination when using only a one-dimensional array. Compare the performance of array-based duplicate elimination with the performance of binary-search-tree-based duplicate elimination.

Write a method depth that receives a binary tree and determines how many levels it has.

(Recursively Print a List Backward) Write a method printListBackward that recursively outputs the items in a linked list object in reverse order. Write a test program that creates a sorted list of integers and prints the list in reverse order.

(Recursively Search a List) Write a method searchList that recursively searches a linked list object for a specified value. Method searchList should return a reference to the value if it is found; otherwise, null should be returned. Use your method in a test program that creates a list of integers. The program should prompt the user for a value to locate in the list.

(Binary Tree Delete) In this exercise, we discuss deleting items from binary search trees. The deletion algorithm is not as straightforward as the insertion algorithm. Three cases are encountered when deleting an itemthe item is contained in a leaf node (i.e., it has no children), the item is contained in a node that has one child or the item is contained in a node that has two children.

If the item to be deleted is contained in a leaf node, the node is deleted and the reference in the parent node is set to null.

If the item to be deleted is contained in a node with one child, the reference in the parent node is set to reference the child node and the node containing the data item is deleted. This causes the child node to take the place of the deleted node in the tree.

The last case is the most difficult. When a node with two children is deleted, another node in the tree must take its place. However, the reference in the parent node cannot simply be assigned to reference one of the children of the node to be deleted. In most cases, the resulting binary search tree would not embody the following characteristic of binary search trees (with no duplicate values): The values in any left subtree are less than the value in the parent node, and the values in any right subtree are greater than the value in the parent node.

Which node is used as a replacement node to maintain this characteristic? It is either the node containing the largest value in the tree less than the value in the node being deleted, or the node containing the smallest value in the tree greater than the value in the node being deleted. Let us consider the node with the smaller value. In a binary search tree, the largest value less than a parent's value is located in the left subtree of the parent node and is guaranteed to be contained in the rightmost node of the subtree. This node is located by walking down the left subtree to the right until the reference to the right child of the current node is null. We are now referencing the replacement node, which is either a leaf node or a node with one child to its left. If the replacement node is a leaf node, the steps to perform the deletion are as follows:

1. Store the reference to the node to be deleted in a temporary reference variable.
2. Set the reference in the parent of the node being deleted to reference the replacement node.
3. Set the reference in the parent of the replacement node to null.
4. Set the reference to the right subtree in the replacement node to reference the right subtree of the node to be deleted.
5. Set the reference to the left subtree in the replacement node to reference the left subtree of the node to be deleted.

The deletion steps for a replacement node with a left child are similar to those for a replacement node with no children, but the algorithm also must move the child into the replacement node's position in the tree. If the replacement node is a node with a left child, the steps to perform the deletion are as follows:

1. Store the reference to the node to be deleted in a temporary reference variable.
2. Set the reference in the parent of the node being deleted to reference the replacement node.
3. Set the reference in the parent of the replacement node reference to the left child of the replacement node.
4. Set the reference to the right subtree in the replacement node reference to the right subtree of the node to be deleted.
5. Set the reference to the left subtree in the replacement node to reference the left subtree of the node to be deleted.

Write method deleteNode, which takes as its argument the value to delete. Method deleteNode should locate in the tree the node containing the value to delete and use the algorithms discussed here to delete the node. If the value is not found in the tree, the method should print a message that indicates whether the value is deleted. Modify the program of Fig. 17.17 and Fig. 17.18 to use this method. After deleting an item, call the methods inorderTraversal, preorderTraversal and postorderTraversal to confirm that the delete operation was performed correctly.

(Binary Tree Search) Write method binaryTreeSearch, which attempts to locate a specified value in a binary search tree object. The method should take as an argument a search key to be located. If the node containing the search key is found, the method should return a reference to that node; otherwise, it should return a null reference.

(Level-Order Binary Tree Traversal) The program of Fig. 17.17 and Fig. 17.18 illustrated three recursive methods of traversing a binary treeinorder, preorder and postorder traversals. This exercise presents the level-order traversal of a binary tree, in which the node values are printed levelby-level, starting at the root node level. The nodes on each level are printed from left to right. The level-order traversal is not a recursive algorithm. It uses a queue object to control the output of the nodes. The algorithm is as follows:

1. Insert the root node in the queue.
2. While there are nodes left in the queue, do the following:

   Get the next node in the queue.

   Print the node's value.

   If the reference to the left child of the node is not null:

   Insert the left child node in the queue.

   If the reference to the right child of the node is not null:

   Insert the right child node in the queue.

Write method levelOrder to perform a level-order traversal of a binary tree object. Modify the program of Fig. 17.17 and Fig. 17.18 to use this method. [Note: You will also need to use queue-processing methods of Fig. 17.13 in this program.]

(Printing Trees) Write a recursive method outputTree to display a binary tree object on the screen. The method should output the tree row by row, with the top of the tree at the left of the screen and the bottom of the tree toward the right of the screen. Each row is output vertically. For example, the binary tree illustrated in Fig. 17.20 is output as shown in Fig. 17.21.

Figure 17.21. Sample output of recursive method outputTree.

(This item is displayed on page 855 in the print version)

Note that the rightmost leaf node appears at the top of the output in the rightmost column and the root node appears at the left of the output. Each column of output starts five spaces to the right of the preceding column. Method outputTree should receive an argument totalSpaces representing the number of spaces preceding the value to be output. (This variable should start at zero so that the root node is output at the left of the screen.) The method uses a modified inorder traversal to output the treeit starts at the rightmost node in the tree and works back to the left. The algorithm is as follows:

While the reference to the current node is not null, perform the following:

Recursively call outputTree with the right subtree of the current node and totalSpaces + 5.

Use a for statement to count from 1 to totalSpaces and output spaces.

Output the value in the current node.

Set the reference to the current node to refer to the left subtree of the current node.

Increment totalSpaces by 5.