Java Reference
In-Depth Information
We now pop the operator stack and get the
*
. We get this operator's second and first operands,
respectively, by popping the stack of values twice. After computing the product 3
*
4, we push the
result 12 onto the stack of values, as Figure 5-12b shows. In a similar fashion, we pop the operator
stack once and the value stack twice, compute 2
+
12, and push the result, 14, onto the stack of val-
ues. Since the operator stack is now empty, the value of the expression—14—is at the top of the
stack of values. Figure 5-12c shows these final steps.
5.21
The algorithm.
The algorithm to evaluate an infix expression follows. You should recognize
aspects of its logic from the previous algorithms.
Algorithm
evaluateInfix(infix)
//
Evaluates an infix expression.
operatorStack =
a new empty stack
valueStack =
a new empty stack
while
(infix
has characters left to process
)
{
nextCharacter =
next nonblank character of
infix
switch
(nextCharacter)
{
case
variable
:
valueStack.push(
value of the variable
nextCharacter)
break
case
'^' :
operatorStack.push(nextCharacter)
break
case
'+' :
case
'-' :
case
'*' :
case
'/' :
while
(!operatorStack.isEmpty()
and
precedence of
nextCharacter <=
precedence of
operatorStack.peek())
{
//
Execute operator at top of
operatorStack
topOperator = operatorStack.pop()
operandTwo = valueStack.pop()
operandOne = valueStack.pop()
result =
the result of the operation in
topOperator
and its operands
operandOne
and
operandTwo
valueStack.push(result)
}
operatorStack.push(nextCharacter)
break
case
'(' :
operatorStack.push(nextCharacter)
break
case
')' :
//
stack is not empty if infix expression is valid
topOperator = operatorStack.pop()
while
(topOperator != '(')
{
operandTwo = valueStack.pop()
operandOne = valueStack.pop()
result =
the result of the operation in
topOperator
and its operands
operandOne
and
operandTwo
valueStack.push(result)
topOperator = operatorStack.pop()
}
break