How to Convert Infix to Postfix Expression - Data Structures

To convert an infix expression to postfix, use a stack to hold operators and output operands immediately; push operators on the stack considering precedence and pop them when a lower precedence operator or closing parenthesis appears, finally outputting all remaining operators from the stack.

Examples

InputA+B

OutputAB+

InputA+B*C

OutputABC*+

Input(A+B)*C

OutputAB+C*

How to Think About It

Think of reading the infix expression from left to right. When you see an operand (like a letter or number), add it directly to the output. When you see an operator, decide if it should wait on a stack or if you should first output operators already on the stack based on their priority. Parentheses help group operations and control when to pop operators from the stack.

Algorithm

1

Initialize an empty stack for operators and an empty output string.

2

Scan the infix expression from left to right.

3

If the character is an operand, add it to the output.

4

If the character is an opening parenthesis '(', push it onto the stack.

5

If the character is a closing parenthesis ')', pop from the stack to output until '(' is found; remove '(' from stack.

6

If the character is an operator, pop operators from the stack to output while they have higher or equal precedence and are not '(', then push the current operator.

7

After processing all characters, pop and output all remaining operators from the stack.

Code

data_structures

def precedence(op):
    return {'+':1, '-':1, '*':2, '/':2, '^':3}.get(op, 0)

def infix_to_postfix(expr):
    stack = []
    output = ''
    for char in expr:
        if char.isalnum():
            output += char
        elif char == '(': 
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(': 
                output += stack.pop()
            stack.pop()  # Remove '('
        else:
            while stack and stack[-1] != '(' and precedence(stack[-1]) >= precedence(char):
                output += stack.pop()
            stack.append(char)
    while stack:
        output += stack.pop()
    print(output)

# Example usage
infix_to_postfix('(A+B)*C')

Output

AB+C*

Dry Run

Let's trace '(A+B)*C' through the code

1

Read '('

Push '(' onto stack; output is empty.

2

Read 'A'

Operand, add to output: output = 'A'.

3

Read '+'

Push '+' onto stack; stack = ['(', '+'].

4

Read 'B'

Operand, add to output: output = 'AB'.

5

Read ')'

Pop '+' from stack to output: output = 'AB+'; remove '(' from stack.

6

Read '*'

Push '*' onto stack; stack = ['*'].

7

Read 'C'

Operand, add to output: output = 'AB+C'.

8

End of expression

Pop '*' from stack to output: output = 'AB+C*'.

Step	Stack	Output
1	(
2	(	A
3	(, +	A
4	(, +	AB
5		AB+
6	*	AB+
7	*	AB+C
8		AB+C*

Why This Works

Step 1: Operands go directly to output

When the code sees a letter or number, it adds it immediately to the output string because operands appear in the same order in postfix.

Step 2: Operators use a stack to manage precedence

Operators are pushed on a stack but popped to output if the next operator has lower precedence, ensuring correct order in postfix.

Step 3: Parentheses control grouping

Opening parentheses are pushed on the stack, and when a closing parenthesis is found, operators are popped until the matching '(' is removed, preserving grouped operations.

Alternative Approaches

Using two stacks (one for operators, one for output)

data_structures

def infix_to_postfix_two_stacks(expr):
    ops = []
    output = []
    prec = {'+':1, '-':1, '*':2, '/':2, '^':3}
    for c in expr:
        if c.isalnum():
            output.append(c)
        elif c == '(': ops.append(c)
        elif c == ')':
            while ops and ops[-1] != '(': output.append(ops.pop())
            ops.pop()
        else:
            while ops and ops[-1] != '(' and prec.get(ops[-1],0) >= prec.get(c,0):
                output.append(ops.pop())
            ops.append(c)
    while ops: output.append(ops.pop())
    print(''.join(output))

infix_to_postfix_two_stacks('(A+B)*C')

This method separates output into a list for clarity but uses more memory.

Recursive parsing

data_structures

def infix_to_postfix_recursive(expr):
    def precedence(op):
        return {'+':1, '-':1, '*':2, '/':2, '^':3}.get(op, 0)
    def helper(i):
        output = ''
        stack = []
        while i < len(expr):
            c = expr[i]
            if c.isalnum(): output += c
            elif c == '(':
                sub, i = helper(i+1)
                output += sub
            elif c == ')':
                break
            else:
                while stack and stack[-1] != '(' and precedence(stack[-1]) >= precedence(c):
                    output += stack.pop()
                stack.append(c)
            i += 1
        while stack: output += stack.pop()
        return output, i
    result, _ = helper(0)
    print(result)

infix_to_postfix_recursive('(A+B)*C')

Recursive approach handles nested parentheses naturally but is more complex.

Complexity: O(n) time, O(n) space

Time Complexity

The algorithm scans the expression once, pushing and popping operators at most once each, resulting in linear time O(n) where n is expression length.

Space Complexity

Extra space is used for the operator stack and output string, both proportional to input size, so O(n) space.

Which Approach is Fastest?

The single stack method is fastest and simplest; recursive parsing is slower and more complex but handles nested expressions elegantly.

Approach	Time	Space	Best For
Single Stack	O(n)	O(n)	Simple and efficient conversion
Two Stacks	O(n)	O(n)	Clear separation of output and operators
Recursive Parsing	O(n)	O(n)	Handling deeply nested parentheses