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
 
Search WWH ::




Custom Search