Chapter 21

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 \((+\text { or } / \text { here })\) is written between its operandsthis is called infix notation. Computers "prefer" postfix notation in which the operator is written to the right of its two operands. The preceding infix expressions would appear in postfix notation as \(34+\) and \(79 /,\) 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 will write a \(\mathrm{C}++\) version of the infix-to- postfix conversion algorithm. In the next exercise, you will write a \(\mathrm{C}++\) version of the postfix expression evaluation algorithm. Later in the chapter, you will 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 \(62+5 * 84 /\) The program should read the expression into character array infix and use modified versions of the stack functions implemented in this chapter to help create the postfix expression in character array 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. \([\text { Page } 1039]\) 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 post \(f\) ix. 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 ' modulus [Note: We assume left to right associativity for all operators for the purpose of 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: a. function convertToPostfix that converts the infix expression to postfix notation b. function isoperator that determines whether \(c\) is an operator c. function precedence that determines whether the precedence of operator1 is less than, equal to or greater than the precedence of operator2 (the function returns1, 0 and \(1,\) respectively d. function push that pushes a value onto the stack e. function pop that pops a value off the stack f. function stackTop that returns the top value of the stack without popping the stack g. function isEmpty that determines if the stack is empty h. function printstack that prints the stack

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 one-dimensional array. Compare the performance of array-based duplicate elimination with the performance of binary-searchtree- based duplicate elimination.

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

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

(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 itemthe item is contained in a leaf node (i.e., it has no children), the item is contained in a node that has one child or the item is contained in a node that has two children. If the item to be deleted is contained in a leaf node, the node is deleted and the pointer in the parent node is set to null. If the item to be deleted is contained in a node with one child, the pointer in the parent node is set to point to 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 pointer in the parent node cannot be assigned to point to 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 pointer to the right child of the current node is null. We are now pointing to 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 pointer to the node to be deleted in a temporary pointer variable (this pointer is used to delete the dynamically allocated memory 2\. Set the pointer in the parent of the node being deleted to point to the replacement node. [Page \(1042]\) 3\. Set the pointer in the parent of the replacement node to null. 4\. Set the pointer to the right subtree in the replacement node to point to the right subtree of the node to be deleted. 5\. Delete the node to which the temporary pointer variable points. 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 pointer to the node to be deleted in a temporary pointer variable. 2\. Set the pointer in the parent of the node being deleted to point to the replacement node. 3\. Set the pointer in the parent of the replacement node to point to the left child of the replacement node. 4\. Set the pointer to the right subtree in the replacement node to point to the right subtree of the node to be deleted. 5\. Delete the node to which the temporary pointer variable points. Write member function deleteNode, which takes as its arguments a pointer to the root node of the tree object and the value to be deleted. The function should locate in the tree the node containing the value to be deleted and use the algorithms discussed here to delete the node. The function should print a message that indicates whether the value is deleted. Modify the program of Figs. 21.2021 .22 to use this function. After deleting an item, call the inorder, preorder and postorder TRaversal functions to confirm that the delete operation was performed correctly.

(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 8.19 a. Allow the modulus operator (s) to be used in let statements. Simpletron Machine Language must be modified to include a modulus instruction. b. Allow exponentiation in a let statement using \(\wedge\) as the exponentiation operator. Simpletron Machine Language must be modified to include an exponentiation instruction. c. Allow the compiler to recognize uppercase and lowercase letters in Simple statements (e.g., 'A' is equivalent to 'a'). No modifications to the Simulator are required. d. Allow input statements to read values for multiple variables such as input \(x, y .\) No modifications to the Simpletron Simulator are required. [Page \(1055]\) e. Allow the compiler to output multiple values in a single print statement such as print a, \(b, c .\) No modifications to the Simpletron Simulator are required. f. 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. g. Allow arrays of integers. No modifications to the Simpletron Simulator are required. h. 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 function call in \(\mathrm{C}++.\) The same subroutine can be called from many gosub commands distributed throughout a program. No modifications to the Simpletron Simulator are required. i. Allow repetition statements of the form for \(x=2\) to \(1 \theta\) step 2 simple statements next This for statement loops from 2 to 18 with an increment of \(2 .\) The next line marks the end of the body of the for. No modifications to the Simpletron Simulator are required. j. Allow repetition statements of the form for \(x=2\) to 10 simple statements next This for statement loops from 2 to 10 with a default increment of \(1 .\) No modifications to the Simpletron Simulator are required. k. 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 ASCII 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 ASCII 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. I. Allow the compiler to process floating-point values in addition to integers. The Simpletron Simulator must also be modified to process floating- point values. (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 slowly because each statement encountered in the program must first be deciphered. 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.

(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 treefor 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 was inserted in increasing order? in decreasing order? What shape should the tree have to achieve maximal searching performance?