Infix to Postfix

Humans commonly write expressions like A + B * C, with the operator sitting between its operands. That's called infix notation. It's natural to read, but a computer evaluating it has to work out precedence and parentheses on the fly. Postfix notation sidesteps that by writing every operator right after its operands, so evaluation becomes a simple left-to-right scan with no precedence rules needed at evaluation time. Converting from one to the other is where a stack comes in.

Infix and postfix notation

A + B       → A B +
A * B       → A B *
A + B * C   → A B C * +

Postfix doesn't need parentheses to preserve evaluation order, the position of each operator relative to its operands already encodes exactly which operations happen first. That's precisely what makes it easy for a computer to evaluate directly, covered next.

Operator precedence

Converting infix to postfix correctly requires knowing which operators bind tighter than others:

Highest
  ^
  * /
  + -
Lowest

Parentheses override precedence explicitly, forcing whatever they enclose to be evaluated as a unit. When two operators have equal precedence, associativity (left-to-right, for + - * /) decides which one is applied first.

The conversion algorithm

A stack holds operators and open parentheses temporarily, while the output string builds up the final postfix expression, one token at a time.

InfixToPostfix(infix)
 
1. Create empty stack S and empty output string P
 
2. For each token in infix (left to right):
 
   a) If token is operand:
      Add token to P
 
   b) If token is '(':
      Push token to S
 
   c) If token is ')':
      Pop from S to P until '(' is found
      Discard the '('
 
   d) If token is operator (+, -, *, /):
      While S is not empty
            AND top(S) is not '('
            AND precedence(top(S)) >= precedence(token):
         Pop from S, append to P
      Push token to S
 
3. After scanning all tokens:
   While S is not empty:
       Pop from S, append to P
 
4. Return P

An operand always goes straight to the output, it never touches the stack, since operands don't need to wait for anything, only operators do.

Simple worked example

Convert A + B * C:

Result: A + B * C becomes ABC*+.

KTU PYQ: full worked conversion

This question has two parts: converting to postfix (this page) and evaluating the result (the Postfix Evaluation page, which continues from the postfix expression produced here).

Postfix expression: A B C * D / + E F G / - -

Practice

Quick recall

• Infix places the operator between operands; postfix places it right after them, removing the need for parentheses or precedence rules at evaluation time.
• The conversion algorithm uses a stack to hold operators and ( temporarily, and an output string that only ever grows, operands go straight in, operators wait their turn.
• On reading an operator, pop and output every stack operator with equal or higher precedence first, then push the new one, this is what enforces correct precedence in the output.
• ) pops everything back to the matching ( and discards it; anything still on the stack at the end gets popped to the output, in order.