Chapter 17

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 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 \(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. Each of these algorithms requires only a single left-toright pass of the expression. Each algorithm uses a stack object in support of its operation, but each uses the stack for a different purpose. In this exercise, you will write a Java version of the infix-to-postfix conversion algorithm. In the next exercise, you will write a Java version of the postfix expression evaluation algorithm. In a later exercise, you will discover that code you write in this exercise can help you implement a complete working compiler. Write class InfixToPostfixConverter to convert an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers such as $$(6+2) * 5-8 / 4$$ to a postfix expression. The postfix version of the preceding infix expression is (note that no parentheses are needed $$62+5 * 84 /-$$ 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: a) Push a left parenthesis '(' on the stack. b) Append a right parenthesis ')' to the end of infix. c) While the stack is not empty, read infix from left to right and do the following: If the current character in infix is a digit, append it to postfix. If the current character in infix is a left parenthesis, push it onto the stack. If the current character in infix is an operator: Pop operators (if there are any) at the top of the stack while they have equal or higher precedence than the current operator, and append the popped operators to postfix. Push the current character in infix onto the stack. If the current character in infix is a right parenthesis: Pop operators from the top of the stack and append them to postfix until a left parenthesis is at the top of the stack. Pop (and discard) the left parenthesis from the stack. The following arithmetic operations are allowed in an expression: \+ addition \- subtraction * multiplication / division ^ exponentiation % remainder The stack should be maintained with stack nodes that each contain an instance variable and a reference to the next stack node. Some of the methods you may want to provide are as follows: a) Method convertToPostfix, which converts the infix expression to postfix notation. b) Method isOperator, which determines whether c is an operator. c) Method precedence, which determines whether the precedence of operator1 (from the infix expression) is less than, equal to or greater than the precedence of operator2 (from the stack). The method returns true if operator1 has lower precedence than operator2. Otherwise, false is returned. d) Method stackTop (this should be added to the stack class), which returns the top value of the stack without popping the stack.

Write class PostfixEvaluator, which evaluates a postfix expression such as $$62+5=84 /-$$ The program should read a postfix expression consisting of digits and operators into a String- Buffer. Using modified versions of the stack methods implemented earlier in this chapter, the pro- gram should scan the expression and evaluate it (assume it is valid). The algorithm is as follows: a) Append a right parenthesis ')' to the end of the postfix expression. When the right- parenthesis character is encountered, no further processing is necessary. b) When the right-parenthesis character has not been encountered, read the expression from left to right. If the current character is a digit, do the following: Push its integer value on the stack (the integer value of a digit character is its value in the computer’s character set minus the value of '0' in Unicode). Otherwise, if the current character is an operator: Pop the two top elements of the stack into variables x and y. Calculate y operator x. Push the result of the calculation onto the stack. c) When the right parenthesis is encountered in the expression, pop the top value of the stack. This is the result of the postfix expression. [Note: In b) above (based on the sample expression at the beginning of this exercise), if the operator is '/', the top of the stack is 2 and the next element in the stack is 8, then pop 2 into x, pop 8 into y, evaluate 8/2 and push the result, 4, back on the stack. This note also applies to operator '-'.] The arithmetic operations allowed in an expression are: \+ addition \- subtraction * multiplication / division ^ exponentiation % remainder The stack should be maintained with one of the stack classes introduced in this chapter. You may want to provide the following methods: a) Method evaluatePostfixExpression, which evaluates the postfix expression. b) Method calculate, which evaluates the expression op1 operator op2. c) Method push, which pushes a value onto the stack. d) Method pop, which pops a value off the stack. e) Method isEmpty, which determines whether the stack is empty. f) Method printStack, which prints the stack.

(Supermarket Simulation) Write a program that simulates a checkout line at a supermarket. The line is a queue object. Customers (i.e., customer objects) arrive in random integer intervals of from 1 to 4 minutes. Also, each customer is serviced in random integer intervals of from 1 to 4 minutes. Obviously, the rates need to be balanced. If the average arrival rate is larger than the average service rate, the queue will grow infinitely. Even with "balanced" rates, randomness can still cause long lines. Run the supermarket simulation for a 12 -hour day \((720 \text { minutes }),\) using the following algorithm: a) Choose a random integer between 1 and 4 to determine the minute at which the first customer arrives. b) At the first customer's arrival time, do the following: Determine customer's service time (random integer from 1 to 4). Begin servicing the customer. Schedule arrival time of next customer (random integer 1 to 4 added to the current time). c) For each minute of the day, consider the following: If the next customer arrives, proceed as follows: Say so. Enqueue the customer. Schedule the arrival time of the next customer. If service was completed for the last customer, do the following: Say so. Dequeue next customer to be serviced. Determine customer's service completion time (random integer from 1 to 4 added to the current time). Now run your simulation for 720 minutes and answer each of the following: a) What is the maximum number of customers in the queue at any time? b) What is the longest wait any one customer experiences? c) What happens if the arrival interval is changed from 1 to 4 minutes to 1 to 3 minutes?

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

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

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

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

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

\((\) Printing Trees) Write a recursive method outputTree to display a binary tree object on the screen. The method should output the tree row by row, with the top of the tree at the left of the screen and the bottom of the tree toward the right of the screen. Each row is output vertically. For example, the binary tree illustrated in Fig. 17.20 is output as shown in Fig. 17.21 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 starts five spaces to the right of the preceding column. Method outputTree should receive an argument total Spaces representing the number of spaces preceding the value to be output. (This variable should start at zero so that the root node is output at the left of the screen.) The method uses a modified inorder traversal to output the 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, perform the following: Recursively call outputTree with the right subtree of the current node and totalSpaces +5 Use a for statement to count from 1 to totalSpaces and output spaces. Output the value in the current node. Set the reference to the current node to refer to the left subtree of the current node. Increment totalSpaces by 5

In Exercises \(7.34-7.35,\) we introduced Simpletron Machine Language \((\mathrm{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 them on the compiler you build and run them on the simulator you built in Exercise \(7.35 .\) You should make every effort to implement your compiler in an object-oriented manner. (\text { 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, 1 et, print, goto, if/goto or end (see Fig. 17.22 ). 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. 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. The syntax of Simple does not allow string manipulation (reading a string, writing a string, comparing strings, and so on \)) .$ 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 17.29 asks the reader to modify the compiler to perform syntax error checking.