Infix to RPN/postfix
P.J. Drongowski
16 October 2004

Background

  * One of the simplest notations for arithmetic expression is
    Reverse Polish Notation (RPN) also called "postfix" notation
    + Invented by Polish logician Jan Lukasiewicz
    + Does not require parentheses
  * PostScript, which is stack-based, uses a form of RPN for everything,
    including arithmetic
  * Stacks are an easy way to evaluate an RPN expression once an infix
    expression has been converted to RPN

Algorithm for converting infix to postfix (RPN)

  Given:
    * An infix expression consisting of tokens: constants, variables,
      operators and parentheses; constants and variables are operands
    * Precedence between operators; A left parenthesis has a lower
      precedence than any operator
    * A place to hold or output the postfix expression
    * A stack which is used to store operators

  Steps
    1. Initialize the stack to its empty state
    2. While no error has occurred and the end of the infix expression
       has not been reached:
       a. Get the next input token
       b. If the token is:
          Left parenthesis    Push it onto the stack

          Right parenthesis   Pop and output stack elements until a left
                              parenthesis is encountered. Pop the left
                              parenthesis. If the stack becomes empty, the
                              parens are unbalanced and an error is reported

          Operator            If the stack is empty or the token has a higher
                              priority than the top stack element, push token
                              on the stack

                              Otherwise, pop and output the top stack element
                              and repeat comparison of token with the new
                              top of stack

          Operand             Output the operand

    3. When the end of the infix expression is reached, pop and output
       any stack items until the stack is empty

Source: ADTs, Data Structures and Problem Solving with C++,
        Larry Nyhoff, Pearson Prentice Hall

****************************************************************
Example (Nyhoff)

  Expression           Stack       Output          Action
  ------------------   --------    ----------      -----------------
   7 * 8 - ( 2 + 3 )               7               Output 7     
     * 8 - ( 2 + 3 )    *          7               Push *
       8 - ( 2 + 3 )    *          7 8             Output 8
         - ( 2 + 3 )               7 8 *           Pop and output *
         - ( 2 + 3 )    -          7 8 *           Push -
           ( 2 + 3 )    - (        7 8 *           Push (
             2 + 3 )    - (        7 8 * 2         Output 2
               + 3 )    - ( +      7 8 * 2         Push +
                 3 )    - ( +      7 8 * 2 3       Push 3
                   )    - (        7 8 * 2 3 +     Pop and output +
                   )    -          7 8 * 2 3 +     Pop (
             <empty>               7 8 * 2 3 + -   Pop and output -
             <empty>     


****************************************************************
Another statement of the conversion algorithm

Given:
  * A set of operators and operator precedence {+, -, *, /}
    where * and / have higher precedence than + and -
  * A stack to hold operand (e.g., variable, number) and operator symbols
  * A place to put the postfix expression ("the output")

1. Variables and numbers are copied to the output
2. Left parentheses are pushed on the stack
3. When a right parenthesis is encountered, the symbol at the top of the
   stack is popped and is copied to the output until the symbol at the
   top of the stack is a left parenthesis. When a left parenthesis is found,
   both parentheses are discarded.
4. If the current symbol has a higher precedence than the symbol on top
   of the stack, the current symbol is pushed.
5. If the precedence of the current symbol is lower than or equal to the
   precedence of the symbol on the top of the stack, then the stack is
   popped to the output until a symbol of lower or equal precedence
6. When the terminating symbol is reached, the stack is popped to the
   output and the algorithm terminates.
7. If the top of the stack is a left parenthesis and the terminating
   symbol is scanned, or a right parenthesis is scanned when the terminating
   symbol is at the top of the stack, the parentheses of the original
   expression were unbalanced and an unrecoverable error has occurred.

Source: Bob Brown, Southern Polytechnic State University