Infix to Postfix Converter

How it works

1. Scan the tokens from left to right, with an empty output list and an empty operator stack.
2. Operand (a number or a variable): append it to the output.
3. (: push it onto the stack.
4. ): pop operators to the output until a ( is on top, then pop and discard the (.
5. Operator o: while the top of the stack is an operator that binds tighter than o — higher precedence, or equal precedence with o left-associative — pop it to the output. Then push o.
6. End of input: pop every remaining operator to the output.

Precedence and associativity rules

Precedence decides which operator is applied first; associativity breaks ties between operators of the same precedence. The visualizer, like most textbooks, uses:

• ^ (power) — highest precedence (3) and right-associative: 2^3^2 means 2^(3^2) = 512, so its postfix is 2 3 2 ^ ^.
• *, /, % — precedence 2, left-associative: a/b*c means (a/b)*c, giving a b / c *.
• +, - — lowest precedence (1), left-associative: a-b-c means (a-b)-c, giving a b - c -.
• Parentheses override everything. A ( on the stack acts as a wall: operators never pop past it, and only the matching ) removes it.

The whole pop rule fits in one sentence: pop while the top's precedence is greater than the incoming operator's, or equal and the incoming operator is left-associative. For ^ the equal case does not pop, and that is precisely what makes it right-associative. The precedence card next to the visualizer highlights the two operators being compared at every step.

Worked example: a+b*(c^d-e)/f

Each line shows the token, then the operator stack (bottom → top) and the output after handling it:

• a → stack: empty | output: a
• + → stack: + | output: a
• b → stack: + | output: a b
• * → * (2) binds tighter than + (1), so it is pushed. Stack: + * | output: a b
• ( → stack: + * ( | output: a b
• c → stack: + * ( | output: a b c
• ^ → the top is (, a wall, so push. Stack: + * ( ^ | output: a b c
• d → stack: + * ( ^ | output: a b c d
• - → ^ (3) beats - (1): pop it; then ( stops the loop. Stack: + * ( - | output: a b c d ^
• e → stack: + * ( - | output: a b c d ^ e
• ) → pop -, discard (. Stack: + * | output: a b c d ^ e -
• / → * has equal precedence and / is left-associative: pop *; + is lower, so stop and push /. Stack: + / | output: a b c d ^ e - *
• f → stack: + / | output: a b c d ^ e - * f
• end → pop /, then +.

Result: a b c d ^ e - * f / +. Read back, it is a + ((b * (c^d - e)) / f): the operators appear in the order they are applied, so postfix needs neither parentheses nor precedence rules. Press play above to watch each step.

Why the algorithm works

Postfix keeps the operands in their original order and writes each operator right after both of its operands are complete. So operands go straight to the output, while an operator — whose right operand hasn't been read yet — waits on the stack.

When a new operator arrives, every waiting operator that binds tighter now has a complete right operand, so it is written first. Inside one level of parentheses the stack therefore holds operators in increasing order of precedence from bottom to top (a run of ^ is the only tie). Each token is pushed and popped at most once, so the nested loop does O(n) work in total.

Common mistakes

• Popping on equal precedence for ^: that produces 2 3 ^ 2 ^, which is 64, instead of 2 3 2 ^ ^ = 512.
• Not popping on equal precedence for left-associative operators: a-b+c would become a b c + -, which means a - (b + c).
• Forgetting to pop the remaining operators when the input ends.
• Letting an operator pop past (, or writing parentheses into the output.
• Treating a unary minus as binary: -3+4 has no left operand for -. Rewrite it as (0-3)+4 or give unary minus its own higher-precedence token.
• Splitting 12+3 into single characters: tokenize first so multi-digit numbers and names stay whole.

Infix, prefix and postfix compared

• Infix (a + b) * c — operators sit between operands; needs precedence rules and parentheses. Natural for humans.
• Prefix (Polish notation) * + a b c — each operator comes before its operands; no parentheses needed.
• Postfix (Reverse Polish notation) a b + c * — each operator comes after its operands; a machine evaluates it with one stack in a single left-to-right pass.

To get prefix from infix, reverse the expression, swap ( and ), convert to postfix with the tie rule mirrored (on equal precedence, pop only when the incoming operator is the right-associative ^), then reverse the result. Compilers usually build an expression tree instead: postfix is its post-order traversal and prefix its pre-order traversal.

Interview variations

• Evaluate the result: feed the postfix to a stack evaluator — see postfix evaluation.
• Basic Calculator (LeetCode 224 and 227): evaluate infix directly with two stacks, one for numbers and one for operators, applying an operator whenever this algorithm would output it.
• Postfix to infix: push operands as strings; for each operator pop b and a and push "(a op b)".
• Build an expression tree from postfix with a stack of subtrees.

Time and space complexity

Infix to Postfix in Python

import re


def tokenize(expr):
    """'a+b*(c^d-e)/f' -> ['a', '+', 'b', '*', '(', 'c', '^', 'd', '-', 'e', ')', '/', 'f']"""
    return re.findall(r"\d+(?:\.\d+)?|[A-Za-z_]\w*|[-+*/%^()]", expr)


PREC = {"^": 3, "*": 2, "/": 2, "%": 2, "+": 1, "-": 1}
RIGHT_ASSOC = {"^"}


def to_postfix(tokens):
    """Shunting-yard. tokens like ["(", "3", "+", "4", ")", "*", "2"]; assumes a valid expression."""
    output, stack = [], []
    for t in tokens:
        if t not in PREC and t not in ("(", ")"):  # t is an operand
            output.append(t)
        elif t == "(":
            stack.append(t)
        elif t == ")":
            while stack[-1] != "(":
                output.append(stack.pop())
            stack.pop()                             # discard "("
        else:                                       # t is an operator
            while stack and stack[-1] in PREC and (
                PREC[stack[-1]] > PREC[t]
                or (PREC[stack[-1]] == PREC[t] and t not in RIGHT_ASSOC)
            ):
                output.append(stack.pop())
            stack.append(t)
    while stack:
        output.append(stack.pop())
    return output


# to_postfix(tokenize("a+b*(c^d-e)/f"))
#   -> ['a', 'b', 'c', 'd', '^', 'e', '-', '*', 'f', '/', '+']

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Postfix Expression EvaluatorEvaluate postfix (Reverse Polish) expressions with a stack, step by step: push numbers, pop two operands per operator in the right order, catch invalid input.
• Balanced Parentheses CheckerCheck if parentheses are balanced and watch the stack algorithm step by step: push each opener, match each closer, catch crossed or unclosed brackets in O(n).
• Stack VisualizerInteractive stack visualizer: watch push, pop and peek move the top pointer of an array stack, see overflow and underflow happen, and learn why each is O(1).
• Stack & Queue VisualizerStack and queue visualizer: animate push, pop, enqueue and dequeue, compare LIFO with FIFO, and step through circular queues, deques and stack applications.