Java Reference
In-Depth Information
Question 5
In general, when should you push an exponentiation operator
^
onto the stack?
5.15
Parentheses.
Parentheses override the rules of operator precedence. We always push an open
parenthesis onto the stack. Once it is in the stack, we treat an open parenthesis as an operator with
the lowest precedence. That is, any subsequent operator will get pushed onto the stack. When we
encounter a close parenthesis, we pop operators from the stack and append them to the forming
postfix expression until we pop an open parenthesis. The algorithm continues with no parentheses
added to the postfix expression.
Note:
Infix-to-postfix conversion
To convert an infix expression to postfix form, you take the following actions, according to the
symbols you encounter, as you process the infix expression from left to right:
•
Operand
Append each operand to the end of the output expression.
•
Operator
^
Push
^
onto the stack.
•
Operator
+
,
-
,
*
, or
/
Pop operators from the stack, appending them to the output
expression, until the stack is empty or its top entry has a lower
precedence than the new operator. Then push the new operator
onto the stack.
•
Open parenthesis
Push ( onto the stack.
•
Close parenthesis
Pop operators from the stack and append them to the output
expression until an open parenthesis is popped. Discard both
parentheses.
5.16
The infix-to-postfix algorithm.
The following algorithm encompasses the previous observations
about the conversion process. For simplicity, all operands in our expression are single-letter variables.
Algorithm
convertToPostfix(infix)
//
Converts an infix expression to an equivalent postfix expression.
operatorStack =
a new empty stack
postfix =
a new empty string
while
(infix
has characters left to parse
)
{
nextCharacter =
next nonblank character of
infix
switch
(nextCharacter)
{
case
variable
:
Append
nextCharacter
to
postfix
break
case
'^' :
operatorStack.push(nextCharacter)
break
case
'+' :
case
'-' :
case
'*' :
case
'/' :
