Note: This is from a 50+ year old class handout.

Introduction

This algorithm evaluates an algebraic expression in two steps. The expression is first converted to a reverse Polish notation expression and then the reverse Polish expression is evaluated.

Step one converts an algebraic expression (infix notation) to a reverse Polish expression (postfix notation). The expression is first broken up into tokens which are passed to the conversion algorithm which reassembles them into a reverse Polish expression. The tokens are of two types, operands (values) and operators (+,-,/,etc.). The reverse Polish expression is built in a FIFO queue (called the "Intermediate Queue") which is used by step two. The conversion algorithm uses a stack called the "Operator Stack".

Step two evaluates the reverse Polish expression and generates an answer. The process requires a stack to hold operands called the "Operand Stack". Each token is read, one at a time, from the "Intermediate Queue". If the token is an operand it is pushed onto the the "Operand Stack". If the token is an operator the operation is performed on the Operands on the top of the stack and the results pushed onto the stack. The final answer will be on the stack.

Step 1: Convert An Algebraic Expression to Reverse Polish Notation

1. Scan the algebraic expression from left to right breaking it up into tokens. Pass the token to the following steps.
2. If the token is an operand (value), add it to the "Intermediate Queue".
3. If the Token is an "Operator" (+,-,/,etc.), do one of the following:
   1. Look at the operator on the top of the "Operator Stack" (TOS). If the TOS has an equal or greater precedence than the token, pop the TOS and add it to the "Intermediate Queue". Go to step (a).
   2. If the TOS has a precedence less that the token, push the token onto the "Operator Stack".
   3. When the token is a left parenthesis push it onto the "Operator Stack".
   4. If the token is a right parenthesis discard it. Then pop operators one at a time from the "Operator Stack" and add them to the "Intermediate Queue". Continue this until a left parenthesis is found, which is discarded.
4. When the scan is complete, add any operators left on the "Operator Stack" to the "Intermediate Queue".

Step 2: Evaluate an Expression In Reverse Polish Notation

1. Scan the expression from left to right breaking it into tokens which are passed to the following steps.
2. Push any tokens that are operands onto a stack called the "Operand Stack".
3. If the token is an operator it is executed using the operands on top of the stack. The results is then pushed onto the stack.
4. When the complete expression has been scanned the results of the expression is on the TOS.