Stacks are used by compilers to help in the process of evaluating expressions and generating machine-language code.

Question:

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. 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’ll write a Java version of the infix-to-postfix conversion algorithm. In the next exercise, you’ll write a Java version of the postfix expression evaluation algorithm. In a later exercise, you’ll 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 (no parentheses are needed) of the this infix expression is 6 2 + 5 * 8 4 / -

The program should read the expression into StringBuffer infix and use the stack class implemented in this chapter to help create the postfix expression in StringBuffer postfix. The algorithm for creating a postfix expression is shown in Fig. 21.19.

Fig. 21.19

2 3 5 6 7 8 10 [[ 12 13 14 15 16 17 18 Push a left parenthesis

The following arithmetic operations are allowed in an expression: + addition - subtraction * multiplication / division ^ exponentiation % remainder The stack should be maintained with stack nodes, each containing data and a reference to the next stack node. Some 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 that of operator2 (from the stack). The method returns true if operator1 has lower precedence than operator2. Otherwise, false is returned.

d) Method peek (this should be added to the stack class), which returns the top value of the stack without popping the stack.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Java How To Program Late Objects Version

ISBN: 9780136123712

8th Edition

Authors: Paul Deitel, Deitel & Associates

Question Posted: