Exercises

Included below are short-answer and programming exercises. Answers are provided for those exercises whose exercise number is a hyperlink. Because college faculty use these exercises in their exams, we have provided answers to roughly half of the exercises included here.


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

22.7 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 should return a reference to the merged list object.

22.8 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.

22.9 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.

22.10 Write a program that inputs a line of text and uses a stack object to print the line reversed.

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

22.12 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 operands–this 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 then evaluate the postfix version of the expression. 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, and in each algorithm the stack is used 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

(6 + 2) * 5 - 8 / 4

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

6 2 + 5 * 8 4 / -

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 on 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 on 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 untila 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:

      + addition
      - subtraction
      * multiplication
      / division
      ^ exponentiation
      % modulus

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:

  1. Method convertToPostfix, which converts the infix expression to postfix notation.
  2. Method isOperator, which determines if c is an operator.
  3. Method precedence, which determines if 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.

22.13 Write class PostfixEvaluator, which evaluates a postfix expression (assume it is valid) such as

6 2 + 5 * 8 4 / -

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. 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:
        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 exercises), 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:

      + addition
      - subtraction
      * multiplication
      / division
      ^ exponentiation
      % modulus

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 on the stack.
  4. Method pop, which pops a value off the stack.
  5. Method isEmpty, which determines if the stack is empty.
  6. Method printStack, which prints the stack.

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

22.15 (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 1 to 4 minutes. Also, each customer is serviced in random integer intervals of 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:
    Determine customer’s service time (random integer from 1 to 4).
    Begin servicing the customer.
    Schedule the arrival time of the next customer (random integer 1 to 4 added to the current
    time).
  3. For each minute of the day:
      If the next customer arrives:
        Say so.
        Enqueue the customer.
        Schedule the arrival time of the next customer.
      If service was completed for the last customer:
        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?

22.16 Modify the program of Fig. 22.15 to allow the binary tree object to contain duplicates.

22.17 Write a program based on the program of Fig. 22.16 that inputs a line of text, tokenizes the sentence into separate words (you may 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 post- order traversals of the tree.

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

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

22.20 (Recursively Print a List Backwards) Write a method printListBackwards 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.

22.21 (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.

22.22 (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. There are three cases that are encountered when deleting an item–the 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 adhere to 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? 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 be deleted. Method deleteNode should locate in the tree the node containing the value to be deleted 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 or not the value is deleted. Modify the program of Fig. 22.16 to use this method. After deleting an item, call the methods inorderTraversal, preorderTraversal and postorderTraversal to confirm that the delete operation was performed correctly.

22.23 (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, the method should return a null reference.

22.24 (Level-Order Binary Tree Traversal) The program of Fig. 22.16 illustrated three recursive methods of traversing a binary tree–inorder, preorder, and postorder traversals. This exercise presents the level-order traversal of a binary tree, in which the node values are printed level-by-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:
      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 22.16 to use this method. [Note: You will also need to use queue-processing methods of Fig. 22.12 in this program.]

22.25 (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. 22.19 is output as follows:

               99

          97

               92

     83

               72

          71

               69

49

               44

          40

               32

     28

               19

          18

               11

 

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 the root node is output at the left of the screen). The method uses a modified inorder traversal to output the tree– it 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:
      Recursively call outputTree with the right subtree of the current node and totalSpaces + 5.
      Use a for structure 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.

Special Section: Building Your Own Compiler

In Exercises 7.42 and 7.43, we introduced Simpletron Machine Language (SML) and you implemented a Simpletron computer simulator to execute programs written in SML. In this section, we build a compiler that converts programs written in a high-level programming language to SML. This section "ties" together the entire programming process. You will write programs in this new high-level language, compile these programs on the compiler you build and run the programs on the simulator you built in Exercise 7.43. You should make every effort to implement your compiler in an object-oriented manner.

22.26 (The Simple Language) Before we begin building the compiler, we discuss a simple, yet powerful high-level language similar to early versions of the popular language Basic. We call the language Simple. Every Simple statement consists of a line number and a Simple instruction. Line numbers must appear in ascending order. Each instruction begins with one of the following Simple commands: rem, input, let, print, goto, if/goto or end (see Fig. 22.20). All commands except end can be used repeatedly. Simple evaluates only integer expressions using the +, -, * and / operators. These operators have the same precedence as in Java. Parentheses can be used to change the order of evaluation of an expression.

    Fig. 22.20

    Simple commands. 

    Command Example statement Description
    rem 50 rem this is a remark Any text following the command rem is for documentation purposes only and is ignored by the compiler.
    input 30 input x Display a question mark to prompt the user to enter an integer. Read that integer from the keyboard and store the integer in x.
    let 80 let u = 4 * (j - 56) Assign u the value of 4 * (j - 56). Note that an arbitrarily complex expression can appear to the right of the equal sign.
    print 10 print w Display the value of w.
    goto 70 goto 45 Transfer program control to line 45.
    if/goto 35 if i == z goto 80 Compare i and z for equality and transfer program control to line 80 if the condition is true; otherwise, continue execution with the next statement.
    end 99 end Terminate program execution.

 

Our Simple compiler recognizes only lowercase letters. All characters in a Simple file should be lowercase (uppercase letters result in a syntax error unless they appear in a rem statement, in which case they are ignored). A variable name is a single letter. Simple does not allow descriptive variable names, so variables should be explained in remarks to indicate their use in a program. Simple uses only integer variables. Simple does not have variable declarations–merely mentioning a variable name in a program causes the variable to be declared and initialized to zero automatically. The syntax of Simple does not allow string manipulation (reading a string, writing a string, comparing strings, etc.). If a string is encountered in a Simple program (after a command other than rem), the compiler generates a syntax error. The first version of our compiler assumes that Simple programs are entered correctly. Exercise 22.29 asks the reader to modify the compiler to perform syntax error checking.

Simple uses the conditional if/goto statement and the unconditional goto statement to alter the flow of control during program execution. If the condition in the if/goto statement is true, control is transferred to a specific line of the program. The following relational and equality operators are valid in an if/goto statement: <, >, <=, >=, == or !=. The precedence of these operators is the same as in Java.

Let us now consider several programs that demonstrate Simple’s features. The first program (Fig. 22.21) reads two integers from the keyboard, stores the values in variables a and b and computes and prints their sum (stored in variable c).

    Fig. 22.21

    Simple program that determines the sum of two integers.

    1. 10 rem determine and print the sum of two integers
    2. 15 rem
    3. 20 rem input the two integers
    4. 30 input a
    5. 40 input b
    6. 45 rem
    7. 50 rem add integers and store result in c
    8. 60 let c = a + b
    9. 65 rem
    10. 70 rem print the result
    11. 80 print c
    12. 90 rem terminate program execution
    13. 99 end

The program of Fig. 22.22 determines and prints the larger of two integers. The integers are input from the keyboard and stored in s and t. The if/goto statement tests the condition s >= t. If the condition is true, control is transferred to line 90 and s is output; otherwise, t is output and control is transferred to the end statement in line 99, where the program terminates.

    Fig. 22.22

    Simple program that finds the larger of two integers.

    1. 10 rem determine and print the larger of two integers
    2. 20 input s
    3. 30 input t
    4. 32 rem
    5. 35 rem test if s >= t
    6. 40 if s >= t goto 90
    7. 45 rem
    8. 50 rem t is greater than s, so print t
    9. 60 print t
    10. 70 goto 99
    11. 75 rem
    12. 80 rem s is greater than or equal to t, so print s
    13. 90 print s
    14. 99 end

Simple does not provide a repetition structure (such as Java’s for, while or do/while). However, Simple can simulate each of Java's repetition structures using the if/goto and goto statements. Figure 22.23 uses a sentinel-controlled loop to calculate the squares of several integers. Each integer is input from the keyboard and stored in variable j. If the value entered is the sentinel value -9999, control is transferred to line 99, where the program terminates. Otherwise, k is assigned the square of j, k is output to the screen and control is passed to line 20, where the next integer is input.

    Fig. 22.23

    Calculate the squares of several integers.

    1. 10 rem calculate the squares of several integers
    2. 20 input j
    3. 23 rem
    4. 25 rem test for sentinel value
    5. 30 if j == -9999 goto 99
    6. 33 rem
    7. 35 rem calculate square of j and assign result to k
    8. 40 let k = j * j
    9. 50 print k
    10. 53 rem
    11. 55 rem loop to get next j
    12. 60 goto 20
    13. 99 end

Using the sample programs of Figs. 22.21, 22.22 and 22.23 as your guide, write a Simple program to accomplish each of the following:

  1. Input three integers, determine their average and print the result.
  2. Use a sentinel-controlled loop to input 10 integers and compute and print their sum.
  3. Use a counter-controlled loop to input 7 integers, some positive and some negative, and compute and print their average.
  4. Input a series of integers and determine and print the largest. The first integer input indicates how many numbers should be processed.
  5. Input 10 integers and print the smallest.
  6. Calculate and print the sum of the even integers from 2 to 30.
  7. Calculate and print the product of the odd integers from 1 to 9.

22.27 (Building A Compiler; Prerequisite: Complete Exercises 7.42, 7.43, 22.12, 22.13, and 22.26) Now that the Simple language has been presented (Exercise 22.26), we discuss how to build a Simple compiler. First, we consider the process by which a Simple program is converted to SML and executed by the Simpletron simulator (see Fig. 22.24). A file containing a Simple program is read by the compiler and converted to SML code. The SML code is output to a file on disk, in which SML instructions appear one per line. The SML file is then loaded into the Simpletron simulator, and the results are sent to a file on disk and to the screen. Note that the Simpletron program developed in Exercise 7.43 took its input from the keyboard. It must be modified to read from a file so it can run the programs produced by our compiler.

    Fig. 22.24

    Writing, compiling and executing a Simple language program.

The Simple compiler performs two passes of the Simple program to convert it to SML. The first pass constructs a symbol table (object) in which every line number (object), variable name (object) and constant (object) of the Simple program is stored with its type and corresponding location in the final SML code (the symbol table is discussed in detail below). The first pass also produces the corresponding SML instruction object(s) for each of the Simple statements (object, etc.). If the Simple program contains statements that transfer control to a line later in the program, the first pass results in an SML program containing some "unfinished" instructions. The second pass of the compiler locates and completes the unfinished instructions, and outputs the SML program to a file.

First Pass

The compiler begins by reading one statement of the Simple program into memory. The line must be separated into its individual tokens (i.e., "pieces" of a statement) for processing and compilation (the StreamTokenizer class from the java.io package can be used). Recall that every statement begins with a line number followed by a command. As the compiler breaks a statement into tokens, if the token is a line number, a variable or a constant, it is placed in the symbol table. A line number is placed in the symbol table only if it is the first token in a statement. The symbolTable object is an array of tableEntry objects representing each symbol in the program. There is no restriction on the number of symbols that can appear in the program. Therefore, the symbolTable for a particular program could be large. Make the symbolTable a 100-element array for now. You can increase or decrease its size once the program is working.

Each tableEntry object contains three members. Member symbol is an integer containing the Unicode representation of a variable (remember that variable names are single characters), a line number or a constant. Member type is one of the following characters indicating the symbol’s type: 'C' for constant, 'L' for line number or 'V' for variable. Member location contains the Simpletron memory location (00 to 99) to which the symbol refers. Simpletron memory is an array of 100 integers in which SML instructions and data are stored. For a line number, the location is the element in the Simpletron memory array at which the SML instructions for the Simple statement begin. For a variable or constant, the location is the element in the Simpletron memory array in which the variable or constant is stored. Variables and constants are allocated from the end of Simpletron’s memory backwards. The first variable or constant is stored at location 99, the next at location 98, etc.

The symbol table plays an integral part in converting Simple programs to SML. We learned in Chapter 7 that an SML instruction is a four-digit integer comprised of two parts–the operation code and the operand. The operation code is determined by commands in Simple. For example, the simple command input corresponds to SML operation code 10 (read), and the Simple command print corresponds to SML operation code 11 (write). The operand is a memory location containing the data on which the operation code performs its task (e.g., operation code 10 reads a value from the keyboard and stores it in the memory location specified by the operand). The compiler searches symbolTable to determine the Simpletron memory location for each symbol, so the corresponding location can be used to complete the SML instructions.

The compilation of each Simple statement is based on its command. For example, after the line number in a rem statement is inserted in the symbol table, the remainder of the statement is ignored by the compiler because a remark is for documentation purposes only. The input, print, goto and end statements correspond to the SML read, write, branch (to a specific location) and halt instructions. Statements containing these Simple commands are converted directly to SML (note that a goto statement may contain an unresolved reference if the specified line number refers to a statement further into the Simple program file; this is sometimes called a forward reference).

When a goto statement is compiled with an unresolved reference, the SML instruction must be flagged to indicate that the second pass of the compiler must complete the instruction. The flags are stored in 100-element array flags of type int in which each element is initialized to -1. If the memory location to which a line number in the Simple program refers is not yet known (i.e., it is not in the symbol table), the line number is stored in array flags in the element with the same subscript as the incomplete instruction. The operand of the incomplete instruction is set to 00 temporarily. For example, an unconditional branch instruction (making a forward reference) is left as +4000 until the second pass of the compiler. The second pass of the compiler will be described shortly.

Compilation of if/goto and let statements is more complicated than other statements– they are the only statements that produce more than one SML instruction. For an if/goto statement, the compiler produces code to test the condition and to branch to another line if necessary. The result of the branch could be an unresolved reference. Each of the relational and equality operators can be simulated using SML’s branch zero and branch negative instructions (or possibly a combination of both).

For a let statement, the compiler produces code to evaluate an arbitrarily complex arithmetic expression consisting of integer variables and/or constants. Expressions should separate each operand and operator with spaces. Exercises 22.12 and 22.13 presented the infix-to-postfix conversion algorithm and the postfix evaluation algorithm used by compilers to evaluate expressions. Before proceeding with your compiler, you should complete each of these exercises. When a compiler encounters an expression, it converts the expression from infix notation to postfix notation, then evaluates the postfix expression.

How is it that the compiler produces the machine language to evaluate an expression containing variables? The postfix evaluation algorithm contains a "hook" where the compiler can generate SML instructions rather than actually evaluating the expression. To enable this "hook" in the compiler, the postfix evaluation algorithm must be modified to search the symbol table for each symbol it encounters (and possibly insert it), determine the symbol’s corresponding memory location and push the memory location on the stack (instead of the symbol). When an operator is encountered in the postfix expression, the two memory locations at the top of the stack are popped and machine language for effecting the operation is produced using the memory locations as operands. The result of each subexpression is stored in a temporary location in memory and pushed back onto the stack so the evaluation of the postfix expression can continue. When postfix evaluation is complete, the memory location containing the result is the only location left on the stack. This is popped and SML instructions are generated to assign the result to the variable at the left of the let statement.

Second Pass

The second pass of the compiler performs two tasks: resolve any unresolved references and output the SML code to a file. Resolution of references occurs as follows:

  1. Search the flags array for an unresolved reference (i.e., an element with a value other than -1).
  2. Locate the object in array symbolTable containing the symbol stored in the flags array (be sure that the type of the symbol is 'L' for line number).
  3. Insert the memory location from member location into the instruction with the unresolved reference (remember that an instruction containing an unresolved reference has operand 00).
  4. Repeat steps 1, 2, and 3 until the end of the flags array is reached.

After the resolution process is complete, the entire array containing the SML code is output to a disk file with one SML instruction per line. This file can be read by the Simpletron for execution (after the simulator is modified to read its input from a file). Compiling your first Simple program into an SML file and then executing that file should give you a real sense of personal accomplishment.

A Complete Example

The following example illustrates complete conversion of a Simple program to SML as it will be performed by the Simple compiler. Consider a Simple program that inputs an integer and sums the values from 1 to that integer. The program and the SML instructions produced by the first pass of the Simple compiler are illustrated in Fig. 22.25. The symbol table constructed by the first pass is shown in Fig. 22.26.

    Fig. 22.25

    SML instructions produced after the compiler’s first pass

    Simple program SML location
    and instruction
    Description
    5 rem sum 1 to x none rem ignored
    10 input x 00 +1099 read x into location 99
    15 rem check y == x none rem ignored
    20 if y == x goto 60 01 +2098 load y (98) into accumulator
      02 +3199 sub x (99) from accumulator
      03 +4200 branch zero to unresolved location
    25 rem increment y none rem ignored
    30 let y = y + 1 04 +2098 load y into accumulator
      05 +3097 add 1 (97) to accumulator
      06 +2196 store in temporary location 96
      07 +2096 load from temporary location 96
      08 +2198 store accumulator in y
    35 rem add y to total none rem ignored
    40 let t = t + y 09 +2095 load t (95) into accumulator
      10 +3098 add y to accumulator
      11 +2194 store in temporary location 94
      12 +2094 load from temporary location 94
      13 +2195 store accumulator in t
    45 rem loop y none rem ignored
    50 goto 20 14 +4001 branch to location 01
    55 rem output result none rem ignored
    60 print t 15 +1195 output t to screen
    99 end 16 +4300 terminate execution

.

    Fig. 22.26

    Symbol table for program of Fig. 22.25. 

    Symbol Type Location
    5 L 00
    10 L 00
    'x' V 99
    15 L 01
    20 L 01
    'y' V 98
    25 L 04
    30 L 04
    1 C 97
    35 L 09
    40 L 09
    't' V 95
    45 L 14
    50 L 14
    55 L 15
    60 L 15
    99 L 16

Most Simple statements convert directly to single SML instructions. The exceptions in this program are remarks, the if/goto statement in line 20 and the let statements. Remarks do not translate into machine language. However, the line number for a remark is placed in the symbol table in case the line number is referenced in a goto statement or an if/goto statement. Line 20 of the program specifies that if the condition y == x is true, program control is transferred to line 60. Because line 60 appears later in the program, the first pass of the compiler has not as yet placed 60 in the symbol table (statement line numbers are placed in the symbol table only when they appear as the first token in a statement). Therefore, it is not possible at this time to determine the operand of the SML branch zero instruction at location 03 in the array of SML instructions. The compiler places 60 in location 03 of the flags array to indicate that the second pass completes this instruction.

We must keep track of the next instruction location in the SML array because there is not a one-to-one correspondence between Simple statements and SML instructions. For example, the if/ goto statement of line 20 compiles into three SML instructions. Each time an instruction is produced, we must increment the instruction counter to the next location in the SML array. Note that the size of Simpletron’s memory could present a problem for Simple programs with many statements, variables and constants. It is conceivable that the compiler will run out of memory. To test for this case, your program should contain a data counter to keep track of the location at which the next variable or constant will be stored in the SML array. If the value of the instruction counter is larger than the value of the data counter, the SML array is full. In this case, the compilation process should terminate and the compiler should print an error message indicating that it ran out of memory during compilation. This serves to emphasize that although the programmer is freed from the burdens of managing memory by the compiler, the compiler itself must carefully determine the placement of instructions and data in memory and must check for such errors as memory being exhausted during the compilation process.

A Step-by-Step View of the Compilation Process

Let us now walk through the compilation process for the Simple program in Fig. 22.25. The compiler reads the first line of the program

5 rem sum 1 to x

into memory. The first token in the statement (the line number) is determined using the StreamTokenizer class (see Chapter 10 for a discussion of Java’s string manipulation methods). The token returned by the StreamTokenizer is converted to an integer using static method Integer.parseInt() so the symbol 5 can be located in the symbol table. If the symbol is not found, it is inserted in the symbol table.

Since we are at the beginning of the program and this is the first line, no symbols are in the table yet. So, 5 is inserted into the symbol table as type L (line number) and assigned the first location in SML array (00). Although this line is a remark, a space in the symbol table is still allocated for the line number (in case it is referenced by a goto or an if/goto). No SML instruction is generated for a rem statement, so the instruction counter is not incremented.

The statement

10 input x

is tokenized next. The line number 10 is placed in the symbol table as type L and assigned the first location in the SML array (00 because a remark began the program, so the instruction counter is currently 00). The command input indicates that the next token is a variable (only a variable can appear in an input statement). Because input corresponds directly to an SML operation code, the compiler simply has to determine the location of x in the SML array. Symbol x is not found in the symbol table. So, it is inserted into the symbol table as the Unicode representation of x, given type V, and assigned location 99 in the SML array (data storage begins at 99 and is allocated backwards). SML code can now be generated for this statement. Operation code 10 (the SML read operation code) is multiplied by 100, and the location of x (as determined in the symbol table) is added to complete the instruction. The instruction is then stored in the SML array at location 00. The instruction counter is incremented by one because a single SML instruction was produced.

The statement

15 rem check y == x

is tokenized next. The symbol table is searched for line number 15 (which is not found). The line number is inserted as type L and assigned the next location in the array, 01 (remember that rem statements do not produce code, so the instruction counter is not incremented).

The statement

20 if y == x goto 60

is tokenized next. Line number 20 is inserted in the symbol table and given type L with the next location in the SML array 01. The command if indicates that a condition is to be evaluated. The variable y is not found in the symbol table, so it is inserted and given the type V and the SML location 98. Next, SML instructions are generated to evaluate the condition. Since there is no direct equivalent in SML for the if/goto, it must be simulated by performing a calculation using x and y and branching based on the result. If y is equal to x, the result of subtracting x from y is zero, so the branch zero instruction can be used with the result of the calculation to simulate the if/goto statement. The first step requires that y be loaded (from SML location 98) into the accumulator. This produces the instruction 01 +2098. Next, x is subtracted from the accumulator. This produces the instruction 02 +3199. The value in the accumulator may be zero, positive or negative. Since the operator is ==, we want to branch zero. First, the symbol table is searched for the branch location (60 in this case), which is not found. So, 60 is placed in the flags array at location 03, and the instruction 03 +4200 is generated (we cannot add the branch location because we have not yet assigned a location to line 60 in the SML array). The instruction counter is incremented to 04.

The compiler proceeds to the statement

25 rem increment y

The line number 25 is inserted in the symbol table as type L and assigned SML location 04. The instruction counter is not incremented.

When the statement

30 let y = y + 1

is tokenized, the line number 30 is inserted in the symbol table as type L and assigned SML location 04. Command let indicates that the line is an assignment statement. First, all the symbols on the line are inserted in the symbol table (if they are not already there). The integer 1 is added to the symbol table as type C and assigned SML location 97. Next, the right side of the assignment is converted from infix to postfix notation. Then the postfix expression (y 1 +) is evaluated. Symbol y is located in the symbol table and its corresponding memory location is pushed onto the stack. Symbol 1 is also located in the symbol table and its corresponding memory location is pushed onto the stack. When the operator + is encountered, the postfix evaluator pops the stack into the right operand of the operator and pops the stack again into the left operand of the operator, then produces the SML instructions

04 +2098 (load y)
05 +3097 (add 1)

The result of the expression is stored in a temporary location in memory (96) with instruction

06 +2196 (store temporary)

and the temporary location is pushed on the stack. Now that the expression has been evaluated, the result must be stored in y (i.e., the variable on the left side of =). So, the temporary location is loaded into the accumulator and the accumulator is stored in y with the instructions

07 +2096 (load temporary)
08 +2198 (store y)

The reader will immediately notice that SML instructions appear to be redundant. We will discuss this issue shortly.

When the statement

35 rem add y to total

is tokenized, line number 35 is inserted in the symbol table as type L and assigned location 09.

The statement

40 let t = t + y

is similar to line 30. The variable t is inserted in the symbol table as type V and assigned SML location 95. The instructions follow the same logic and format as line 30, and the instructions 09 +2095, 10 +3098, 11 +2194, 12 +2094 and 13 +2195 are generated. Note that the result of t + y is assigned to temporary location 94 before being assigned to t (95). Once again, the reader will note that the instructions in memory locations 11 and 12 appear to be redundant. Again, we will discuss this shortly.

The statement

45 rem loop y

is a remark, so line 45 is added to the symbol table as type L and assigned SML location 14.

The statement

50 goto 20

transfers control to line 20. Line number 50 is inserted in the symbol table as type L and assigned SML location 14. The equivalent of goto in SML is the unconditional branch (40) instruction that transfers control to a specific SML location. The compiler searches the symbol table for line 20 and finds that it corresponds to SML location 01. The operation code (40) is multiplied by 100 and location 01 is added to it to produce the instruction 14 +4001.

The statement

55 rem output result

is a remark, so line 55 is inserted in the symbol table as type L and assigned SML location 15.

The statement

60 print t

is an output statement. Line number 60 is inserted in the symbol table as type L and assigned SML location 15. The equivalent of print in SML is operation code 11 (write). The location of t is determined from the symbol table and added to the result of the operation code multiplied by 100.

The statement

99 end

is the final line of the program. Line number 99 is stored in the symbol table as type L and assigned SML location 16. The end command produces the SML instruction +4300 (43 is halt in SML) which is written as the final instruction in the SML memory array.

This completes the first pass of the compiler. We now consider the second pass. The flags array is searched for values other than -1. Location 03 contains 60, so the compiler knows that instruction 03 is incomplete. The compiler completes the instruction by searching the symbol table for 60, determining its location, and adding the location to the incomplete instruction. In this case, the search determines that line 60 corresponds to SML location 15, so the completed instruction 03 +4215 is produced, replacing 03 +4200. The Simple program has now been compiled successfully.

    To build the compiler, you will have to perform each of the following tasks:

  1. Modify the Simpletron simulator program you wrote in Exercise 5.43 to take its input from a file specified by the user (see Chapter 17). The simulator should output its results to a disk file in the same format as the screen output. Convert the simulator to be an object-oriented program. In particular, make each part of the hardware an object. Arrange the instruction types into a class hierarchy using inheritance. Then execute the program polymorphically simply by telling each instruction to execute itself with an executeInstruction message.
  2. Modify the infix-to-postfix evaluation algorithm of Exercise 22.12 to process multidigit integer operands and single-letter variable name operands. (Hint: Class StreamTokenizer can be used to locate each constant and variable in an expression, and constants can be converted from strings to integers using Integer class method parseInt.) [Note: The data representation of the postfix expression must be altered to support variable names and integer constants.]
  3. Modify the postfix evaluation algorithm to process multidigit integer operands and variable name operands. Also, the algorithm should now implement the "hook" discussed above so that SML instructions are produced rather than directly evaluating the expression. (Hint: Class StreamTokenizer can be used to locate each constant and variable in an expression, and constants can be converted from strings to integers using Integer class method parseInt.) [Note: The data representation of the postfix expression must be altered to support variable names and integer constants.]
  4. Build the compiler. Incorporate parts b) and c) for evaluating expressions in let statements. Your program should contain a method that performs the first pass of the compiler and a method that performs the second pass of the compiler. Both methods can call other methods to accomplish their tasks. Make your compiler as object oriented as possible.

22.28 (Optimizing the Simple Compiler) When a program is compiled and converted into SML, a set of instructions is generated. Certain combinations of instructions often repeat themselves, usually in triplets called productions. A production normally consists of three instructions, such as load, add and store. For example, Fig. 22.27 illustrates five of the SML instructions that were produced in the compilation of the program in Fig. 22.25. The first three instructions are the production that adds 1 to y. Note that instructions 06 and 07 store the accumulator value in temporary location 96, then load the value back into the accumulator so instruction 08 can store the value in location 98. Often a production is followed by a load instruction for the same location that was just stored. This code can be optimized by eliminating the store instruction and the subsequent load instruction that operate on the same memory location, thus enabling the Simpletron to execute the program faster. Figure 22.28 illustrates the optimized SML for the program of Fig. 22.25. Note that there are four fewer instructions in the optimized code–a memory-space savings of 25%.

    Fig. 22.27

    Unoptimized code from the program of Fig. 22.25.

  1. 04 +2098 (load)
  2. 05 +3097 (add)
  3. 06 +2196 (store)
  4. 07 +2096 (load)
  5. 08 +2198 (store)

 

    Fig. 22.28

    Optimized code for the program of Fig. 22.25. 

Simple program SML location
and instruction
Description
5 rem sum 1 to x none rem ignored
10 input x 00 +1099 read x into location 99
15 rem check y == x none rem ignored
20 if y == x goto 60 01 +2098 load y (98) into accumulator
  02 +3199 sub x (99) from accumulator
  03 +4211 branch to location 11 if zero
25 rem increment y none rem ignored
30 let y = y + 1 04 +2098 load y into accumulator
  05 +3097 add 1 (97) to accumulator
  06 +2198 store accumulator in y (98)
35 rem add y to total none rem ignored
40 let t = t + y 07 +2096 load t from location (96 )
  08 +3098 add y (98) accumulator
  09 +2196 store accumulator in t (96)
45 rem loop y none rem ignored
50 goto 20 10 +4001 branch to location 01
55 rem output result none rem ignored
60 print t 11 +1196 output t (96) to screen
99 end 12 +4300 terminate execution

Modify the compiler to provide an option for optimizing the Simpletron Machine Language code it produces. Manually compare the nonoptimized code with the optimized code, and calculate the percentage reduction.

22.29 (Modifications to the Simple Compiler) Perform the following modifications to the Simple compiler. Some of these modifications may also require modifications to the Simpletron simulator program written in Exercise 5.43.

  1. Allow the modulus operator (%) to be used in let statements. Simpletron Machine Language must be modified to include a modulus instruction.
  2. Allow exponentiation in a let statement using ^ as the exponentiation operator. Simpletron Machine Language must be modified to include an exponentiation instruction.
  3. Allow the compiler to recognize uppercase and lowercase letters in Simple statements (e.g., 'A' is equivalent to 'a'). No modifications to the Simpletron simulator are required.
  4. Allow input statements to read values for multiple variables such as input x, y. No modifications to the Simpletron simulator are required to perform this enhancement to the Simple compiler.
  5. Allow the compiler to output multiple values using a single print statement such as print a, b, c. No modifications to the Simpletron simulator are required to perform this enhancement.
  6. Add syntax-checking capabilities to the compiler so error messages are output when syntax errors are encountered in a Simple program. No modifications to the Simpletron simulator are required.
  7. Allow arrays of integers. No modifications to the Simpletron simulator are required to perform this enhancement.
  8. Allow subroutines specified by the Simple commands gosub and return. Command gosub passes program control to a subroutine and command return passes control back to the statement after the gosub. This is similar to a method call in Java. The same subroutine can be called from many gosub commands distributed throughout a program. No modifications to the Simpletron simulator are required.
  9. Allow repetition structures of the form

    for x = 2 to 10 step 2
    Simple statements
    next

  10. This for statement loops from 2 to 10 with an increment of 2. The next line marks the end of the body of the for line. No modifications to the Simpletron simulator are required.
  11. Allow repetition structures of the form

    for x = 2 to 10
    Simple statements
    next

  12. This for statement loops from 2 to 10 with a default increment of 1. No modifications to the Simpletron simulator are required.
  13. Allow the compiler to process string input and output. This requires the Simpletron simulator to be modified to process and store string values. [Hint: Each Simpletron word can be divided into two groups, each holding a two-digit integer. Each two-digit integer represents the Unicode decimal equivalent of a character. Add a machine-language instruction that will print a string beginning at a certain Simpletron memory location. The first half of the word at that location is a count of the number of characters in the string (i.e., the length of the string). Each succeeding half word contains one Unicode character expressed as two decimal digits. The machine language instruction checks the length and prints the string by translating each two-digit number into its equivalent character.]
  14. Allow the compiler to process floating-point values in addition to integers. The Simpletron Simulator must also be modified to process floating-point values.

22.30 (A Simple Interpreter) An interpreter is a program that reads a high-level language program statement, determines the operation to be performed by the statement and executes the operation immediately. The high-level language program is not converted into machine language first. Interpreters execute slower than compilers do because each statement encountered in the program being interpreted must first be deciphered at execution time. If statements are contained in a loop, the statements are deciphered each time they are encountered in the loop. Early versions of the Basic programming language were implemented as interpreters. Most Java programs are run interpretively.

Write an interpreter for the Simple language discussed in Exercise 22.26. The program should use the infix-to-postfix converter developed in Exercise 22.12 and the postfix evaluator developed in Exercise 22.13 to evaluate expressions in a let statement. The same restrictions placed on the Simple language in Exercise 22.26 should be adhered to in this program. Test the interpreter with the Simple programs written in Exercise 22.26. Compare the results of running these programs in the interpreter with the results of compiling the Simple programs and running them in the Simpletron simulator built in Exercise 7.43

22.31 (Insert/Delete Anywhere in a Linked List) Our linked list class allowed insertions and deletions at only the front and the back of the linked list. These capabilities were convenient for us when we used inheritance or composition to produce a stack class and a queue class with a minimal amount of code simply by reusing the list class. Linked lists are normally more general than those we provided. Modify the linked list class we developed in this chapter to handle insertions and deletions anywhere in the list.

22.32 (Lists and Queues without Tail References) Our implementation of a linked list (Fig. 22.3) used both a firstNode and a lastNode. The lastNode was useful for the insertAtBack and removeFromBack methods of the List class. The insertAtBack method corresponds to the enqueue method of the Queue class.

Rewrite the List class so that it does not use a lastNode. Thus, any operations on the tail of a list must begin searching the list from the front. Does this affect our implementation of the Queue class (Fig. 22.12)?


22.33 (Performance of Binary Tree Sorting and Searching) One problem with the binary tree sort is that the order in which the data is inserted affects the shape of the tree–for the same collection of data, different orderings can yield binary trees of dramatically different shapes. The performance of the binary tree sorting and searching algorithms is sensitive to the shape of the binary tree. What shape would a binary tree have if its data were inserted in increasing order? in decreasing order? What shape should the tree have to achieve maximal searching performance?

22.34 (Indexed Lists) As presented in the text, linked lists must be searched sequentially. For large lists, this can result in poor performance. A common technique for improving list searching performance is to create and maintain an index to the list. An index is a set of references to key places in the list. For example, an application that searches a large list of names could improve performance by creating an index with 26 entries–one for each letter of the alphabet. A search operation for a last name beginning with ‘Y’ would then first search the index to determine where the ‘Y’ entries begin, and then "jump into" the list at that point and search linearly until the desired name is found. This would be much faster than searching the linked list from the beginning. Use the List class of Fig. 22.3 as the basis of an IndexedList class.

Write a program that demonstrates the operation of indexed lists. Be sure to include methods insertInIndexedList, searchIndexedList and deleteFromIndexedList.


Selected Answers

Included below are answers to approximately half the of the exercises in the Cyber Classroom. We are not able to include answers to every exercise because college faculty use these exercises in their classroom exams.


22.6

// Exercise 22.6 Solution// ListConcat.java// Program concatenates two lists// NOTE: definitins for List, ListNode, and// EmptyListException are in the data_structures// directory.import com.deitel.jhtp3.ch22.EmptyListException;import com.deitel.jhtp3.ch22.List;import com.deitel.jhtp3.ch22.ListNode;public class ListConcat {   public static void main( String args[] )   {      List list1 = new List();        List list2 = new List();            // Create objects to store in list1      Character a = new Character( '5' );      Character b = new Character( '@' );      Character c = new Character( 'V' );      Character d = new Character( '+' );      // Use the List insert methods      System.out.println( "List 1:" );      list1.insertAtFront( a );      list1.print();      list1.insertAtFront( b );      list1.print();      list1.insertAtBack( c );      list1.print();      list1.insertAtBack( d );      list1.print();      // Create objects to store in list2      Character a2 = new Character( 'P' );      Character b2 = new Character( 'c' );      Character c2 = new Character( 'M' );      Character d2 = new Character( '&' );      // Use the List insert methods      System.out.println( "List 2:" );      list2.insertAtFront( a2 );      list2.print();      list2.insertAtFront( b2 );      list2.print();      list2.insertAtBack( c2 );      list2.print();      list2.insertAtBack( d2 );      list2.print();      concatenate( list1, list2 );      System.out.println( "Concatenated list is:" );      list1.print();   }   public static void concatenate( List one, List two )   {      ListNode temp = two.getFirstNode();      while ( temp != null ) {         one.insertAtBack( temp.getData() );         temp = temp.getNext();      }         }}

22.8

// Exercise 22.8 Solution// ListTest.java// Program inserts and sorts numbers in a list,// prints the sum, and displays the averageimport com.deitel.jhtp3.ch22.List;import com.deitel.jhtp3.ch22.ListNode;import com.deitel.jhtp3.ch22.EmptyListException;class List2 extends List {   public List2( String s ) { super( s ); }   public List2() { super(); }   public void insert( Integer i )   {      if ( isEmpty() ) {         ListNode newNode = new ListNode( i );         firstNode = lastNode = newNode;      }      else {         if ( ( ( Integer ) firstNode.getData() ).intValue() > i.intValue() )            insertAtFront( i );         else if ( ( ( Integer ) lastNode.getData() ).intValue() < i.intValue() )            insertAtBack( i );         else {            ListNode current = firstNode.getNext(), previous = firstNode,                     newNode = new ListNode( i );            while ( current != lastNode && ( ( Integer ) current.getData() ).intValue() <                    i.intValue() ) {               previous = current;               current = current.getNext();            }            previous.setNext( newNode );            newNode.setNext( current );         }      }            }   public int add()   {      int sum = 0;      ListNode current = firstNode;      while ( current != null ) {         sum += ( ( Integer ) current.getData() ).intValue();         current = current.getNext();      }      return sum;   }}public class ListTest {   public static void main( String args[] )   {      List2 x = new List2();                   Integer y = null;      // Create objects to store in the List      for ( int k = 1; k <= 25; k++ ) {         y = new Integer( ( int ) ( Math.random() * 101 ) );         x.insert( y );      }            x.print();      int s = x.add();      System.out.println( "Sum is: " + s + "\nAverage: " +                          ( ( float ) s / 25.0f ) );   }}

22.10

// Exercise 22.10 Solution// StackInheritanceTest.java// Program prints the words of a line in reverseimport javax.swing.*;import java.awt.*;import java.util.*;import java.awt.event.*;import com.deitel.jhtp3.ch22.EmptyListException;import com.deitel.jhtp3.ch22.StackInheritance;public class StackInheritanceTest extends JFrame {   public StackInheritanceTest()   {      super( "Reversing a string" );      final StackInheritance objStack = new StackInheritance();      final JTextField output = new JTextField( 20 );      final JLabel prompt = new JLabel( "Enter String:" );      final JTextField input = new JTextField( 20 );      input.addActionListener(         new ActionListener() {            public void actionPerformed( ActionEvent e )            {               String text = input.getText();               StringTokenizer s = new StringTokenizer( text );               StringBuffer buffer = new StringBuffer( text.length() );               while ( s.hasMoreTokens() )                  objStack.push( s.nextToken() );               // build reverse string               Object removedObj = null;               try {                  while ( !objStack.isEmpty() ) {                     removedObj = objStack.pop();                     buffer.append( removedObj.toString() + " " );                  }               }               catch ( EmptyListException ex ) {                  System.err.println( "\n" + ex.toString() );               }               output.setText( buffer.toString() );                     }         }      );            output.setEditable( false );      Container c = getContentPane();      c.setLayout( new FlowLayout() );      JPanel p = new JPanel();      p.add( prompt );      p.add( input );            c.add( p );        c.add( output );      setSize( 400, 100 );      show();   }   public static void main( String args[] )    {      StackInheritanceTest app = new StackInheritanceTest();      app.addWindowListener(         new WindowAdapter() {            public void windowClosing( WindowEvent e )            {               System.exit( 0 );            }         }      );   }}

22.11

// Exercise 22.11 Solution// StackInheritanceText.java// Program tests for a palindromeimport javax.swing.*;import java.awt.*;import java.util.*;import java.awt.event.*;import com.deitel.jhtp3.ch22.EmptyListException;import com.deitel.jhtp3.ch22.StackInheritance;public class StackInheritanceTest extends JFrame {   public StackInheritanceTest()   {            final StackInheritance objStack = new StackInheritance();      final JLabel prompt = new JLabel( "Enter String:" );      final JTextField input = new JTextField( 20 );             input.addActionListener(         new ActionListener() {            public void actionPerformed( ActionEvent e )            {               String text = input.getText();               char m = '\0';               for ( int i = 0; i < text.length(); i++ ) {                  m = text.charAt( i );                  if ( Character.isLetter( m ) )                     objStack.push( new Character( m ) );                                    Object removedObj = null;                  boolean flag = false;                  char letter = '\0';                  try {                     for ( int c = 0; c < text.length() &&                           !objStack.isEmpty(); c++ ) {                        letter = text.charAt( c );                        if ( !Character.isLetter( letter ) )                           continue;                                       removedObj = objStack.pop();                        if ( letter != ( ( Character ) removedObj ).charValue() ) {                           flag = true;                                             break;                        }                     }                     if ( flag == false )                        setTitle( "Palindrome" );                     else                        setTitle( "Not a Palindrome" );                  }                  catch ( EmptyListException ex ) {                     System.err.println( "\n" + ex.toString() );                  }               }            }         }      );      Container c = getContentPane();      c.setLayout( new BorderLayout() );      c.add( prompt, BorderLayout.NORTH );      c.add( input, BorderLayout.SOUTH );      setSize( 400, 75 );      show();   }   public static void main( String args[] )    {      StackInheritanceTest app = new StackInheritanceTest();      app.addWindowListener(         new WindowAdapter() {            public void windowClosing( WindowEvent e )            {               System.exit( 0 );            }         }      );   }}

22.16

// Exercise 22.16 Solution// TreeTest.java// This program tests the Tree class.import java.util.*;import com.deitel.jhtp3.ch22.Tree;public class TreeTest {   public static void main( String args[] )   {      Tree tree = new Tree();      int intVal;      System.out.println( "Inserting the following values: " );      for ( int i = 1; i <= 10; i++ ) {         intVal = ( int ) ( Math.random() * 100 );         System.out.print( intVal + " " );         tree.insertNode( new Integer( intVal ) );      }      System.out.println ( "\n\nPreorder traversal" );      tree.preorderTraversal();      System.out.println ( "\n\nInorder traversal" );      tree.inorderTraversal();      System.out.println ( "\n\nPostorder traversal" );      tree.postorderTraversal();      System.out.println();   }}

22.17

// Exercise 22.17 Solution// TreeTest.java// This program tests the Tree class.import javax.swing.*;import java.awt.*;import java.util.*;import java.awt.event.*;public class TreeTest extends JFrame {   public TreeTest()   {      super( "Tokenizer" );      final JLabel prompt = new JLabel( "Enter String:" );      final JTextField input = new JTextField( 25 );      input.addActionListener(         new ActionListener() {            public void actionPerformed( ActionEvent e )            {               Tree2 tree = new Tree2();               StringTokenizer s = new StringTokenizer( input.getText() );               while ( s.hasMoreTokens() )                               tree.insertNode( s.nextToken() );                                 System.out.println( "\n\nPreorder traversal" );               tree.preorderTraversal();               System.out.println( "\n\nInorder traversal" );               tree.inorderTraversal();               System.out.println( "\n\nPostorder traversal" );               tree.postorderTraversal();                }         }      );      Container c = getContentPane();      c.add( prompt, BorderLayout.NORTH );      c.add( input, BorderLayout.SOUTH );            setSize( 400, 100 );      show();   }   public static void main( String args[] )   {      TreeTest app = new TreeTest();      app.addWindowListener(         new WindowAdapter() {            public void windowClosing( WindowEvent e )            {               System.exit( 0 );            }         }      );   }}import com.deitel.jhtp3.ch22.TreeNode;// Class TreeNode definitionpublic class TreeNode2 extends TreeNode {   public TreeNode2( String s ) { super( s ); }   public void insert( String s )   {      if ( s.compareTo( data.toString() ) < 0 ) {         if ( left == null )            left = new TreeNode2( s );         else            ( ( TreeNode2 ) left ).insert( s );      }      else if ( s.compareTo( data.toString() ) > 0 ) {              if ( right == null )                 right = new TreeNode2( s );         else            ( ( TreeNode2 ) right ).insert( s );      }   }}import com.deitel.jhtp3.ch22.Tree;// Class Tree definitionpublic class Tree2 extends Tree {   public void insertNode( String s )   {      if ( root == null )         root = new TreeNode2( s );      else         ( ( TreeNode2 ) root ).insert( s );   }}

22.19

// Exercise 22.19 Solution// TreeTest.java// This program tests the Tree class.import java.util.*;import com.deitel.jhtp3.ch22.Tree3;public class TreeTest {   public static void main( String args[] )   {      Tree3 tree = new Tree3();      int intVal;      System.out.println( "Inserting the following values: " );      for ( int i = 1; i <= 10; i++ ) {         intVal = ( int ) ( Math.random() * 100 );         System.out.print( intVal + " " );         tree.insertNode( new Integer( intVal ) );      }      System.out.println ( "\n\nPreorder traversal" );      tree.preorderTraversal();      System.out.println ( "\n\nInorder traversal" );      tree.inorderTraversal();      System.out.println ( "\n\nPostorder traversal" );      tree.postorderTraversal();      System.out.println( "\nTree has a depth of: " +                          tree.depth() );   }}package com.deitel.jhtp3.ch22;// Class Tree definitionpublic class Tree3 {   protected TreeNode root;   private int treeDepth;   private boolean b = true;   // Construct an empty Tree of integers   public Tree3() { root = null; }   // Insert a new node in the binary search tree.   // If the root node is null, create the root node here.   // Otherwise, call the insert method of class TreeNode.   public synchronized void insertNode( Integer d )   {      if ( root == null )         root = new TreeNode( d );      else         root.insert( d );   }   // Preorder Traversal   public synchronized void preorderTraversal() { preorderHelper( root ); }   // Recursive method to perform preorder traversal   private synchronized void preorderHelper( TreeNode node )   {      if ( node == null )         return;      System.out.print( node.data + " " );      preorderHelper( node.left );      preorderHelper( node.right );   }   // Inorder Traversal   public synchronized void inorderTraversal()   {      inorderHelper( root, 0 );   }   // Recursive method to perform inorder traversal   private synchronized void inorderHelper( TreeNode node, int depthCount )   {      if ( node == null ) {         if ( depthCount > treeDepth )            treeDepth = depthCount;         return;      }      inorderHelper( node.left, depthCount + 1 );      if ( b ) {         System.out.print( node.data + " " );         b = true;      }      inorderHelper( node.right, depthCount + 1 );   }   // Postorder Traversal   public synchronized void postorderTraversal() { postorderHelper( root ); }   // Recursive method to perform postorder traversal   private synchronized void postorderHelper( TreeNode node )   {      if ( node == null )         return;         postorderHelper( node.left );      postorderHelper( node.right );      System.out.print( node.data + " " );   }   public int depth()   {      b = false;      inorderTraversal();      return treeDepth;   }}

22.20

// Exercise 22.20 Solution// ListTest.java// Program recursively prints a list backwardspublic class ListTest {   public static void main( String args[] )   {      List2 x = new List2();                   Integer y = null;      // Create objects to store in the List      for ( int k = 1; k <= 25; k++ ) {         y = new Integer( ( int ) ( Math.random() * 101 ) );         x.insert( y );      }            x.print();      System.out.println( "\nReverse ordered list:" );      x.printListBackwards();   }}import com.deitel.jhtp3.ch22.List;import com.deitel.jhtp3.ch22.ListNode;// Class List definitionpublic class List2 extends List {   public List2( String s ) { super( s ); }   public List2() { this( "list" ); }                                public void insert( Integer i )   {      if ( isEmpty() ) {         ListNode newNode = new ListNode( i );         firstNode = lastNode = newNode;      }      else {         if ( ( ( Integer ) firstNode.getData() ).intValue() > i.intValue() )            insertAtFront( i );         else if ( ( ( Integer ) lastNode.getData() ).intValue() < i.intValue() )            insertAtBack( i );         else {            ListNode current = firstNode.getNext(), previous = firstNode,                     newNode = new ListNode( i );            while ( current != lastNode && ( ( Integer ) current.getData() ).intValue() <                    i.intValue() ) {               previous = current;               current = current.getNext();            }            previous.setNext( newNode );            newNode.setNext( current );         }      }            }   public void printListBackwards()   {      reverse( firstNode );      System.out.println();   }   private void reverse( ListNode currentNode )   {      if ( currentNode == null )         return;      else         reverse( currentNode.getNext() );      System.out.print( ( ( Integer ) currentNode.getData() ).intValue() + " " );   }}

22.23

// Exercise 22.23 Solution// TreeTest.java// Program performs a binary tree search.import java.util.*;import com.deitel.jhtp3.ch22.TreeNode;public class TreeTest {   public static void main( String args[] )   {      Tree2 tree = new Tree2();      int intVal;      System.out.println( "Inserting the following values: " );      for ( int i = 1; i <= 10; i++ ) {         intVal = ( int ) ( Math.random() * 100 );         System.out.print( intVal + " " );         tree.insertNode( new Integer( intVal ) );      }      int num = ( int ) ( Math.random() * 100 );      TreeNode myNode = tree.binarySearch( new Integer( num ) );            if ( myNode == null )         System.out.println( "\n" + num + " is not in the tree." );      else         System.out.println( "\n" + num + " found in the tree." );   }}import com.deitel.jhtp3.ch22.Tree;import com.deitel.jhtp3.ch22.TreeNode;// Class Tree definitionpublic class Tree2 extends Tree {   public TreeNode binarySearch( Integer v ) { return search( root, v ); }   private TreeNode search( TreeNode rootNode, Integer value )   {      if ( rootNode == null )         return null;      if ( value.intValue() == ( ( Integer ) rootNode.getData() ).intValue() )          return rootNode;      else if ( value.intValue() < ( ( Integer ) rootNode.getData() ).intValue() )         return search(  rootNode.getLeft(), value );      else   //  val > rootNode.data          return search(  rootNode.getRight(), value );   }}

22.25

// Exercise 22.25 Solution// TreeTest.java// This program tests the Tree class.import java.util.*;public class TreeTest {   public static void main( String args[] )   {      Tree2 tree = new Tree2();      int intVal;      System.out.println( "Inserting the following values: " );      for ( int i = 1; i <= 10; i++ ) {         intVal = ( int ) ( Math.random() * 100 );         System.out.print( intVal + " " );         tree.insertNode( new Integer( intVal ) );      }      System.out.println ( "\n\nPreorder traversal" );      tree.preorderTraversal();      System.out.println ( "\n\nInorder traversal" );      tree.inorderTraversal();      System.out.println ( "\n\nPostorder traversal" );      tree.postorderTraversal();      System.out.println( "\n\n" );      tree.printTree();   }}import com.deitel.jhtp3.ch22.Tree;import com.deitel.jhtp3.ch22.TreeNode;// Class Tree definitionpublic class Tree2 extends Tree {   public void printTree() { printTreeHelper( root, 0 ); }   private void printTreeHelper( TreeNode node, int spaces )   {      if ( node != null ) {         printTreeHelper( node.getRight(), spaces + 5 );         for ( int k = 1; k <= spaces; k++ )            System.out.print( " " );         System.out.println( node.getData().toString() );         printTreeHelper( node.getLeft(), spaces + 5 );      }   }}

22.31

// Exercise 22.31 Solution// ListTest.java// Program allows insertions or deletions// anywhere inside the linked listimport com.deitel.jhtp2.ch17.EmptyListException;public class ListTest {   public static void main( String args[] )   {      List2 objList = new List2();  // create the List container      // Create objects to store in the List      for ( int a = 20; a >= 2; a -= 2 )         objList.insertInOrder( new Integer( a ) );      System.out.println( "Before insertion:" );      objList.print();      Integer i = new Integer( 7 );      objList.insertInOrder( i );      System.out.println( "After insertion:" );      objList.print();      try {         Integer temp = i;         if ( objList.deleteNode( i ) )            System.out.println( temp.toString() + " removed" );         else            System.out.println( temp.toString() + " not deleted." );         System.out.println( "After delete:" );         objList.print();         System.out.println();      }      catch ( EmptyListException e ) {         System.err.println( "\n" + e.toString() );      }   }}import com.deitel.jhtp2.ch17.List;import com.deitel.jhtp2.ch17.ListNode;// Class List definitionclass List2 extends List {   public boolean deleteNode( Integer x )   {      if ( isEmpty() )         return false;      else {         if ( ( ( Integer ) firstNode.getData() ).intValue() == x.intValue() ) {            removeFromFront();            return true;         }         else if ( ( ( Integer ) lastNode.getData() ).intValue() == x.intValue() ) {            removeFromBack();            return true;         }         else {            ListNode current = firstNode.getNext(),                     previous = firstNode;            while ( current != lastNode && ( ( Integer ) current.getData() ).intValue() < x.intValue() ) {               previous = current;               current = current.getNext();            }            if ( ( ( Integer ) current.getData() ).intValue() == x.intValue() ) {               previous.setNext( current.getNext() );               return true;            }            else               return false;         }      }   }   public void insertInOrder( Integer y )   {      if ( isEmpty() ) {         ListNode newNode = new ListNode( y );          firstNode = lastNode = newNode;      }      else {         if ( ( ( Integer ) firstNode.getData() ).intValue() > y.intValue() )             insertAtFront( y );         else if ( ( ( Integer ) lastNode.getData() ).intValue() < y.intValue() )             insertAtBack( y );         else {            ListNode current = firstNode.getNext(),                     previous = firstNode,                     newNode = new ListNode( y );            while ( current != lastNode && ( ( Integer ) current.getData() ).intValue() < y.intValue() ) {               previous = current;               current = current.getNext();            }            previous.setNext( newNode );            newNode.setNext( current );         }      }   }}

Data Structures

package com.deitel.jhtp3.ch22;// Class TreeNode definitionpublic class TreeNode {      protected TreeNode left;   // left node   protected Object data;     // data item   protected TreeNode right;  // right node                              public TreeNode( Object d )   {       data = d;                    left = right = null;     }   public synchronized void insert( Integer d )   {      if ( d.intValue() < ( ( Integer ) data ).intValue() ) {         if ( left == null )            left = new TreeNode( d );         else            left.insert( d );      }  // assignment operator allows duplicate values      else if ( d.intValue() >= ( ( Integer ) data ).intValue() ) {          if ( right == null )                 right = new TreeNode( d );         else            right.insert( d );      }   }   public synchronized TreeNode getRight() { return right; }   public synchronized TreeNode getLeft() { return left; }   public synchronized Object getData() { return data; }}package com.deitel.jhtp3.ch22;// Class List definitionpublic class List {   protected ListNode firstNode;   protected ListNode lastNode;   private String name;  // String like "list" used in printing   // Constructor: Construct an empty List with s as the name   public List( String s )   {      name = s;      firstNode = lastNode = null;   }   // Constructor: Construct an empty List with   // "list" as the name   public List() { this( "list" ); }                                // Insert an Object at the front of the List   // If List is empty, firstNode and lastNode refer to   // same Object. Otherwise, firstNode refers to new node.   public synchronized void insertAtFront( Object insertItem )   {      if ( isEmpty() )         firstNode = lastNode = new ListNode( insertItem );      else          firstNode = new ListNode( insertItem, firstNode );   }   // Insert an Object at the end of the List   // If List is empty, firstNode and lastNode refer to   // same Object. Otherwise, lastNode's next instance   // variable refers to new node.   public synchronized void insertAtBack( Object insertItem )   {      if ( isEmpty() )         firstNode = lastNode = new ListNode( insertItem );      else          lastNode = lastNode.next = new ListNode( insertItem );   }   // Remove the first node from the List.   public synchronized Object removeFromFront() throws EmptyListException   {      Object removeItem = null;      if ( isEmpty() )         throw new EmptyListException( name );      removeItem = firstNode.data;  // retrieve the data      // reset the firstNode and lastNode references      if ( firstNode.equals( lastNode ) )         firstNode = lastNode = null;      else         firstNode = firstNode.next;      return removeItem;     }   // Remove the last node from the List.   public synchronized Object removeFromBack() throws EmptyListException   {      Object removeItem = null;      if ( isEmpty() )         throw new EmptyListException( name );      removeItem = lastNode.data;  // retrieve the data      // reset the firstNode and lastNode references      if ( firstNode.equals( lastNode ) )         firstNode = lastNode = null;      else {         ListNode current = firstNode;         while ( current.next != lastNode )            current = current.next;            lastNode = current;         current.next = null;      }      return removeItem;   }   // Return true if the List is empty   public synchronized boolean isEmpty() { return firstNode == null; }   // Output the List contents   public synchronized void print()   {      if ( isEmpty() ) {         System.out.println( "Empty " + name );         return;      }      System.out.print( "The " + name + " is: " );      ListNode current = firstNode;      while ( current != null ) {         System.out.print( current.data.toString() + " " );         current = current.next;      }      System.out.println( "\n" );   }   public synchronized ListNode getFirstNode() { return firstNode; }}package com.deitel.jhtp3.ch22;// Class ListNode definitionpublic class ListNode {   // friendly data so class List can access it directly   Object data;       ListNode next;   // Constructor: Create a ListNode that refers to Object o.   public ListNode( Object o )   {      data = o;     // this node refers to Object o      next = null;  // set next to null   }   // Constructor: Create a ListNode that refers to Object o and   // to the next ListNode in the List.   public ListNode( Object o, ListNode nextNode )   {      data = o;         // this node refers to Object o      next = nextNode;  // set next to refer to next   }   // Return the Object in this node   public synchronized Object getData() { return data; }   // Return the next node   public synchronized ListNode getNext() { return next; }   // Set the next node   public synchronized void setNext( ListNode n ) { next = n; }}package com.deitel.jhtp3.ch22;// Class StackInheritance definition// Derived from class Listpublic class StackInheritance extends List {   public StackInheritance() { super( "stack" ); }   public void push( Object o ) { insertAtFront( o ); }   public Object pop() throws EmptyListException      { return removeFromFront(); }}package com.deitel.jhtp3.ch22;// Class Tree definitionpublic class Tree {   protected TreeNode root;   // Construct an empty Tree of integers   public Tree() { root = null; }   // Insert a new node in the binary search tree.   // If the root node is null, create the root node here.   // Otherwise, call the insert method of class TreeNode.   public synchronized void insertNode( Integer d )   {      if ( root == null )         root = new TreeNode( d );      else         root.insert( d );   }   // Preorder Traversal   public synchronized void preorderTraversal() { preorderHelper( root ); }   // Recursive method to perform preorder traversal   private synchronized void preorderHelper( TreeNode node )   {      if ( node == null )         return;      System.out.print( node.data + " " );      preorderHelper( node.left );      preorderHelper( node.right );   }   // Inorder Traversal   public synchronized void inorderTraversal() { inorderHelper( root ); }   // Recursive method to perform inorder traversal   private synchronized void inorderHelper( TreeNode node )   {      if ( node == null )         return;      inorderHelper( node.left );      System.out.print( node.data + " " );      inorderHelper( node.right );   }   // Postorder Traversal   public synchronized void postorderTraversal() { postorderHelper( root ); }   // Recursive method to perform postorder traversal   private synchronized void postorderHelper( TreeNode node )   {      if ( node == null )         return;      postorderHelper( node.left );      postorderHelper( node.right );      System.out.print( node.data + " " );   }}package com.deitel.jhtp3.ch22;// Class EmptyListException definitionpublic class EmptyListException extends RuntimeException {   public EmptyListException( String name )   {      super( "The " + name + " is empty" );   }}