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.
