Java Reference
In-Depth Information
while
(!operatorStack.isEmpty()
and
precedence of
nextCharacter <=
precedence of
operatorStack.peek())
{
Append
operatorStack.peek()
to
postfix
operatorStack.pop()
}
operatorStack.push(nextCharacter)
break
case
'( ' :
operatorStack.push(nextCharacter)
break
case
')' :
//
stack is not empty if infix expression is valid
topOperator = operatorStack.pop()
while
(topOperator != '(')
{
Append
topOperator
to
postfix
topOperator = operatorStack.pop()
}
break
default
:
break
}
}
while
(!operatorStack.isEmpty())
{
topOperator = operatorStack.pop()
Append
topOperator
to
postfix
}
return
postfix
Figure 5-9 traces this algorithm for the infix expression
a
/
b
*
(
c
+
(
d
-
e
)). The resulting post-
fix expression is
a
b
/
c
d
e
-
+
*
.
FIGURE 5-9
The steps in converting the infix expression
a
/
b
*
(
c
+
(
d
-
e
))
to postfix form
Next Character from
Infix Expression
Postfix Form
Operator Stack
(bottom to top)
a
/
b
*
a
a
a b
a b /
a b /
a b /
a b / c
a b / c
a b / c
a b / c d
a b / c d
a b / c d e
a b / c d e -
a b / c d e -
a b / c d e - +
a b / c d e - +
a b / c d e - + *
/
/
*
* (
* (
* ( +
* ( + (
* ( + (
* ( + ( -
* ( + ( -
* ( + (
* ( +
* (
*
(
c
+
(
d
-
e
)
)