Data Structures and Algorithms
with Object-Oriented Design Patterns in C#|
One of the most useful characteristics of a postfix expression
is that the value of such an expression can be computed easily
with the aid of a stack of values.
The components of a postfix expression are processed
from left to right as follows:
After all the components of the expression have been processed in this fashion,
the stack will contain a single result
which is the final value of the expression.
Figure illustrates the use of a stack
to evaluate the RPN expression given in Equation .
- If the next component of the expression is an operand,
the value of the component is pushed onto the stack.
- If the next component of the expression is an operator,
then its operands are in the stack.
The required number of operands are popped from the stack;
the specified operation is performed;
and the result is pushed back onto the stack.
Figure: Evaluating the RPN expression in Equation using a stack.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.