19.6 (Concatenating Lists) Write a program that concatenates two linked list objects of characters. The program should include function concatenate, which takes references to both list objects as arguments and concatenates the second list to the first list.

19.7 (Merging Ordered Lists) Write a program that merges two ordered list objects of integers into a single ordered list object of integers. Function merge should receive references to each of the list objects to be merged and a reference to a list object into which the merged elements will be placed.

19.8 (Summing and Averaging Elements in a List) Write a program that inserts 25 random integers from 0 to 100 in order in a linked list object. The program should calculate the sum of the elements and the floating-point average of the elements.

19.9 (Copying a List in Reverse Order) Write a program that creates a linked list object of 10 characters and creates a second list object containing a copy of the first list, but in reverse order.

19.10 (Printing a Sentence in Reverse Order with a Stack) Write a program that inputs a line of text and uses a stack object to print the line reversed.

19.11 (Palindrome Testing with Stacks) Write a program that uses a stack object 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.

19.12 (Infix-to-Postfix Conversion) 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 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’ll write a C++ version of the infix-to-postfix conversion algorithm. In the next exercise, you’ll write a C++ version of the postfix expression evaluation algorithm. Later in the chapter, you’ll discover that code you write in this exercise can help you implement a complete working compiler.

Write a program that converts 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

6 2 + 5 * 8 4 / -

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

1. Push a left parenthesis '(' onto 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, copy it to the next element of 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 insert the popped operators in 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 insert them in 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:

• + addition

• - subtraction

• * multiplication

• / division

• ^ exponentiation

• % remainder

[Note: We assume left-to-right associativity for all operators in this exercise.] The stack should be maintained with stack nodes, each containing a data member and a pointer to the next stack node.

Some of the functional capabilities you may want to provide are:

1. function convertToPostfix that converts the infix expression to postfix notation

2. function isOperator that determines whether c is an operator

3. function precedence that determines whether the precedence of operator1 is greater than or equal to the precedence of operator2, and, if so, returns true

4. function push that pushes a value onto the stack

5. function pop that pops a value off the stack

6. function stackTop that returns the top value of the stack without popping the stack

7. function isEmpty that determines if the stack is empty

8. function printStack that prints the stack

19.13 (Postfix Evaluation) Write a program that evaluates a valid postfix expression such as

6 2 + 5 * 8 4 / -

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

1. While you have not reached the end of the string, read the expression from left to right.

   • If the current character is a digit,

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

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

2. When you reach the end of the string, pop the top value of the stack. This is the result of the postfix expression.

[Note: In Step 2 above, 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 onto the stack. This note also applies to operator '–'.] The arithmetic operations allowed in an expression are

• + addition

• – subtraction

• * multiplication

• / division

• ^ exponentiation

• % remainder

[Note: We assume left-to-right associativity for all operators for the purpose of this exercise.] The stack should be maintained with stack nodes that contain an int data member and a pointer to the next stack node. You may want to provide the following functional capabilities:

1. function evaluatePostfixExpression that evaluates the postfix expression

2. function calculate that evaluates the expression op1 operator op2

3. function push that pushes a value onto the stack

4. function pop that pops a value off the stack

5. function isEmpty that determines if the stack is empty

6. function printStack that prints the stack

19.14 (Postfix Evaluation Enhanced) Modify the postfix evaluator program of Exercise 19.13 so that it can process integer operands larger than 9.

19.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–4 minutes. Also, each customer is served in random integer intervals of 1–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 from 1 to 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 arrival time of 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, and schedule the arrival time of the next customer;

   • If service was completed for the last customer;

     • Say so, dequeue next customer to be serviced and 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’s the maximum number of customers in the queue at any time?

2. What’s the longest wait any one customer experiences?

3. What happens if the arrival interval is changed from 1–4 minutes to 1–3 minutes?

19.16 (Allowing Duplicates in Binary Trees) Modify the program of Figs. 19.20–19.22 to allow the binary tree object to contain duplicates.

19.17 (Binary Tree of Strings) Write a program based on Figs. 19.20–19.22 that inputs a line of text, tokenizes the sentence into separate words (you may want to use the istringstream library class), inserts the words in a binary search tree and prints the inorder, preorder and postorder traversals of the tree. Use an OOP approach.

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

19.19 (Depth of a Binary Tree) Write a function depth that receives a binary tree and determines how many levels it has.

19.20 (Recursively Print a List Backward) Write a member function 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.

19.21 (Recursively Search a List) Write a member function searchList that recursively searches a linked list object for a specified value. The function should return a pointer to the value if it’s found; otherwise, nullptr should be returned. Use your function in a test program that creates a list of integers. The program should prompt the user for a value to locate in the list.

19.22 (Binary Tree Search) Write member function binaryTreeSearch, which attempts to locate a specified value in a binary search tree object. The function should take as arguments a pointer to the binary tree’s root node and a search key to locate. If the node containing the search key is found, the function should return a pointer to that node; otherwise, the function should return a nullptr pointer.

19.23 (Level-Order Binary Tree Traversal) The program of Figs. 19.20–19.22 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 pointer to the left child of the node is not nullptr

     • Insert the left child node in the queue

   • If the pointer to the right child of the node is not nullptr

     • Insert the right child node in the queue.

Write member function levelOrder to perform a level-order traversal of a binary tree object. Modify the program of Figs. 19.20–19.22 to use this function. [Note: You’ll also need to modify and incorporate the queue-processing functions of Fig. 19.16 in this program.]

19.24 (Printing Trees) Write a recursive member function outputTree to display a binary tree object on the screen. The function 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. 19.24 is output as shown in Fig. 19.25. 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 previous column. Function 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 function 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 pointer to the current node is not nullptr

  • Recursively call outputTree with the current node’s right subtree 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 pointer to the current node to point to the left subtree of the current node Increment totalSpaces by 5.

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

19.26 (List and Queues without Tail Pointers) Our implementation of a linked list (Figs. 19.4–19.5) used both a firstPtr and a lastPtr. The lastPtr was useful for the insertAtBack and removeFromBack member functions of the List class. The insertAtBack function corresponds to the enqueue member function of the Queue class. Rewrite the List class so that it does not use a lastPtr. 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. 19.16)?

19.27 (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?

19.28 (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 pointers to various 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 first search the index to determine where the "Y" entries begin and “jump into” the list at that point and search linearly until the desired name was found. This would be much faster than searching the linked list from the beginning. Use the List class of Figs. 19.4–19.5 as the basis of an IndexedList class. Write a program that demonstrates the operation of indexed lists. Be sure to include member functions insertInIndexedList, searchIndexedList and deleteFromIndexedList.