Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Evaluating Postfix Expressions

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:

  1. If the next component of the expression is an operand, the value of the component is pushed onto the stack.
  2. 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.
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 gif illustrates the use of a stack to evaluate the RPN expression given in Equation gif.

   figure5644
Figure: Evaluating the RPN expression in Equation gif using a stack.

next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.