Infix to Postfix Conversion

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.

Why postfix instead of prefix?

There's a third notation, prefix (operator before its operands, + A B), that's equally valid and equally parenthesis-free. The difference is scan direction: postfix reads left-to-right, prefix reads right-to-left. Postfix is the one taught and converted to most often because a left-to-right scan matches both how text is naturally read and how infix itself is scanned during conversion, making infix-to-postfix a more direct, single-pass translation than infix-to-prefix. See Expression Evaluation for the full three-way comparison.

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.

Worked example

Convert A + B * C:

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

Notice why * gets applied before + in the output, even though + was pushed first: * stays on top of the stack until something pops it, and since nothing after it has lower-or-equal precedence to trigger a pop early, it only comes off at the end, right after C, landing before + in the output. That ordering is exactly what makes ABC*+ evaluate multiplication before addition.

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.