Infix to Postfix Conversion Algorithm

The idea in one paragraph

The algorithm is Dijkstra's shunting-yard, published in 1961 and named after a railway shunting yard: incoming operators are shunted onto a siding (the stack) and released onto the main line (the output) in the right order. Operands are never ambiguous, so they are written out the instant they are read. Operators are always ambiguous — something stronger might follow — so they are held until the algorithm can prove their position is fixed.

The algorithm, step by step

Create an empty operator stack and an empty output list, then scan the infix expression from left to right, one token at a time.

1. If the token is an operand, append it to the output. Its position in postfix is already final, so it never goes on the stack.
2. If the token is an opening bracket, push it. It is a marker, not an operator — it will be discarded, never output.
3. If the token is a closing bracket, pop to the output until the matching opening bracket is on top. Then pop that opening bracket and discard both. If the stack empties before an opening bracket is found, the expression is unbalanced.
4. If the token is an operator, pop while the top of the stack outranks it. Keep popping to the output while the stack is non-empty, the top is not an opening bracket, and either the top has higher precedence, or the top has equal precedence and the incoming operator is left associative.
5. Push the incoming operator. This happens immediately after the popping in the previous step finishes.
6. When the scan finishes, pop every remaining operator to the output. Top down. If an opening bracket appears here, brackets were unbalanced.
7. The output list is the postfix expression. It contains no brackets, and it can be evaluated left to right with a single value stack.

Operator priority and associativity

Priority — precedence — decides which operator wins when two of them compete for the same operand. Associativity resolves the tie when the priority is equal. These are the standard values used in data structures courses and in this site's converter.

All conversion rules in one table

Pseudocode

Language independent, and a direct transcription of the rules above. Every implementation on this site — including the C program and the JavaScript running the converter — is this same routine.

function infixToPostfix(expression):
    stack  = empty stack
    output = empty list

    for each token in expression:

        if token is an operand:
            output.append(token)

        else if token == '(':
            stack.push(token)

        else if token == ')':
            while stack is not empty and stack.peek() != '(':
                output.append(stack.pop())
            if stack is empty:
                error "unbalanced: missing ("
            stack.pop()                      // discard the '('

        else if token is an operator:
            while stack is not empty
                  and stack.peek() != '('
                  and ( priority(stack.peek()) > priority(token)
                        or ( priority(stack.peek()) == priority(token)
                             and isLeftAssociative(token) ) ):
                output.append(stack.pop())
            stack.push(token)

        else:
            error "invalid character"

    while stack is not empty:
        top = stack.pop()
        if top == '(':
            error "unbalanced: missing )"
        output.append(top)

    return output

Dry run

Tracing K + L - M * N + (O ^ P) * W / U / V * T + Q — the expression that turns up in half the textbooks. Stack top is on the right.

The complete postfix result is:

Rows 18–22 are abbreviated with … for width; open this expression in the converter to see every cell in full.

The equal-precedence trap

This is the single most common bug. When the incoming operator has the same priority as the one on top of the stack, most people push. That is wrong for every left-associative operator.

Addition hides the bug because it is associative in arithmetic — the answer comes out the same. Subtraction and division expose it immediately, which is why exam questions almost always use them.

Right associativity and ^

Exponentiation is the one operator that groups right to left: a ^ b ^ c means a ^ (b ^ c). So when a second ^ arrives and finds a ^ on the stack, it must not pop it.

a ^ b ^ c

  a       output: a
  ^       stack empty, push          stack: ^
  b       output: a b
  ^       equal priority BUT right associative → push
                                     stack: ^ ^
  c       output: a b c
  end     pop both                   output: a b c ^ ^

  correct:  a b c ^ ^      =  a ^ (b ^ c)
  wrong:    a b ^ c ^      =  (a ^ b) ^ c

In the pseudocode above this is handled by the single clause and isLeftAssociative(token) on the equal-priority test. Remove it and exponentiation breaks; hard-code it to true and everything else breaks.

Time and space complexity

Invalid input and edge cases

An algorithm that only works on well-formed input is half an algorithm. These are the cases worth handling explicitly, and how each one is detected.

A single boolean — "the next token must be an operand" — flipped by each token type catches every row except the bracket cases, which the stack itself catches. The converter on this site uses exactly that check, which is why it explains what is wrong instead of silently producing nonsense.

Adapting it for prefix

The same routine produces prefix (Polish notation) with three changes wrapped around it:

1. Reverse the infix expression, swapping every ( for ) and vice versa.
2. Run the algorithm, but flip the associativity test — pop only on strictly higher priority for left-associative operators, and on equal priority for right-associative ones.
3. Reverse the result. That is the prefix expression.

So A + B * C becomes + A * B C. The converter on the homepage shows the prefix form alongside the postfix one for every expression you enter.

Frequently asked questions