Infix to Postfix

Here is a pseudo-code version of an algorithm to convert an infix expression into a postfix expression:

Push (Null)
While getToken
    Case token Of
 
        Operand:  Append(token)
 
        "(":      Push(token)
 
        ")":      While TOS <> "(" Do
                      Append(TOS)
                      Pop
                  Endwhile
                  Pop
 
        Operator: While Precedence(token) <= Precedence(TOS) Do
                      Append(TOS)
                      Pop
                  Endwhile
                  Push(token)
    Endcase
EndWhile
While TOS <> Null Do
    Append(TOS)
    Pop
Endwhile
Pop

As you can see, this algorithm requires the use of a stack of tokens. In effect, this stack keeps track of pending operations that have been deferred because of subsequent operations with a higher precedence.

• TOS refers to the token on the top of the stack.
• Append means that the token is added to the end of the current postfix expression.
• Null, in this case, is the null operator token (the null operator is the null string).