GeeksforGeeks Medium

Infix to Postfix Conversion

Convert an infix arithmetic expression to its postfix (Reverse Polish) form.

stackstringsparsing

02

Intuition

💡

Operands go straight to the output because their order never changes. Operators must wait, because whether one is emitted now depends on what comes next — that waiting room is the stack. An operator is popped and emitted as soon as it can no longer be outranked, which is what the precedence comparison decides.

03

Approach

1

Operands out, operators onto the stack

Any alphanumeric character is appended to the output immediately, since operands appear in postfix in the same relative order as in infix. Operators are held on a stack until their operands are known to be complete.

2

Pop by precedence before pushing

Before pushing an operator, pop and emit every stack operator with greater or equal precedence. Those operators bind at least as tightly and their operands are already complete, so they must be emitted first. It is easy to reuse the same >= comparison for every operator, since that is what correctly pops equal-precedence left-associative operators like + or *. But ^ is right-associative, and >= there pops the previous ^ too eagerly, making a^b^c associate as (a^b)^c instead of the correct a^(b^c). Right-associative operators need a strict > comparison instead.

3

Brackets as scope markers

Push ( unconditionally; it blocks all popping since nothing outside the bracket may be emitted from inside it. On ), pop and emit until the matching ( appears, then discard both brackets — they never appear in postfix. At the end, drain whatever remains on the stack. O(n) time and O(n) space; each character is pushed and popped at most once.

04

Solution & live demo

python

▶1class Solution:
▶2    def infixToPostfix(self, exp):
▶3        prec = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
▶4        out, st = [], []
▶5        for ch in exp:
▶6            if ch.isalnum():
▶7                out.append(ch)
▶8            elif ch == '(': 
▶9                st.append(ch)
▶10            elif ch == ')':
▶11                while st and st[-1] != '(': 
▶12                    out.append(st.pop())
▶13                st.pop()
▶14            else:
▶15                while st and st[-1] != '(' and prec.get(st[-1], 0) >= prec[ch]:
▶16                    out.append(st.pop())
▶17                st.append(ch)
▶18        while st:
▶19            out.append(st.pop())
▶20        return ''.join(out)

05

Edge cases

Single operand

It is emitted directly and the stack stays empty.

Fully bracketed expression

The brackets are consumed and never appear in the output.

Right-associative ^

Needs a strict > comparison; using >= produces the wrong association for a^b^c.

Operators of equal precedence

Left-associative ones pop on >=, giving the correct left-to-right grouping.

06

Complexity

Time

O(n)

Space

O(n)

Each character is pushed and popped at most once.