Infix to Postfix Conversion Using Stack in DSA Java

Mental Model

We use a stack to reorder operators so that expressions can be evaluated without parentheses, following operator precedence.

Analogy: Imagine sorting tasks by priority: you keep the most important tasks on top of a stack and finish them first, so the order of work is clear and efficient.

Infix expression: A + B * C
Stack: empty
Postfix output: empty

Dry Run Walkthrough

Input: infix expression: A + B * C

Goal: Convert the infix expression to postfix notation respecting operator precedence

Step 1: Read 'A', an operand, add to output

Stack: []
Output: A

Why: Operands go directly to output

Step 2: Read '+', push to stack

Stack: [+]
Output: A

Why: Operators go to stack to wait for precedence check

Step 3: Read 'B', an operand, add to output

Stack: [+]
Output: A B

Why: Operands go directly to output

Step 4: Read '*', higher precedence than '+', push to stack

Stack: [+ *]
Output: A B

Why: Higher precedence operators stay on stack

Step 5: Read 'C', an operand, add to output

Stack: [+ *]
Output: A B C

Why: Operands go directly to output

Step 6: End of expression, pop all operators from stack to output

Stack: []
Output: A B C * +

Why: Empty stack to complete postfix expression

Result:

Postfix expression: A B C * +

Annotated Code

DSA Java

import java.util.Stack;

public class InfixToPostfix {

    public static int precedence(char ch) {
        if (ch == '+' || ch == '-')
            return 1;
        else if (ch == '*' || ch == '/')
            return 2;
        else
            return -1;
    }

    public static String convert(String infix) {
        StringBuilder postfix = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < infix.length(); i++) {
            char ch = infix.charAt(i);

            if (Character.isLetterOrDigit(ch)) {
                postfix.append(ch).append(' '); // add operand to output
            } else if (ch == '(') {
                stack.push(ch); // push '(' to stack
            } else if (ch == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop()).append(' '); // pop until '('
                }
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop(); // remove '(' from stack
                }
            } else { // operator
                while (!stack.isEmpty() && precedence(ch) <= precedence(stack.peek()) && stack.peek() != '(') {
                    postfix.append(stack.pop()).append(' '); // pop higher or equal precedence
                }
                stack.push(ch); // push current operator
            }
        }

        while (!stack.isEmpty()) {
            postfix.append(stack.pop()).append(' '); // pop remaining operators
        }

        return postfix.toString().trim();
    }

    public static void main(String[] args) {
        String infix = "A+B*C";
        String postfix = convert(infix);
        System.out.println(postfix);
    }
}

if (Character.isLetterOrDigit(ch)) { postfix.append(ch).append(' ');

Add operands directly to output

else if (ch == '(') { stack.push(ch);

Push '(' to stack to mark sub-expression start

else if (ch == ')') { while (!stack.isEmpty() && stack.peek() != '(') { postfix.append(stack.pop()).append(' ');

Pop operators until '(' found to close sub-expression

while (!stack.isEmpty() && precedence(ch) <= precedence(stack.peek())) { postfix.append(stack.pop()).append(' ');

Pop operators with higher or equal precedence before pushing current

stack.push(ch);

Push current operator to stack

while (!stack.isEmpty()) { postfix.append(stack.pop()).append(' ');

Pop all remaining operators after processing expression

Output

A B C * +

Complexity Analysis

Time: O(n) because we scan the expression once and each operator is pushed and popped at most once

Space: O(n) for the stack and output string to hold operators and operands

vs Alternative: Compared to recursive parsing, stack-based conversion is simpler and uses less overhead

Edge Cases

Empty expression

Returns empty postfix string without error

DSA Java

for (int i = 0; i < infix.length(); i++) {

Expression with parentheses

Correctly handles nested parentheses by pushing '(' and popping until ')' is found

DSA Java

else if (ch == ')') {

Expression with single operand

Returns the operand as postfix without operators

DSA Java

if (Character.isLetterOrDigit(ch)) {

When to Use This Pattern

When you see an expression with operators and parentheses and need to evaluate or reorder it, use the stack-based infix to postfix conversion pattern to simplify evaluation order.

Common Mistakes

Mistake: Not popping all remaining operators from the stack at the end
Fix: Add a final loop to pop all operators after processing the entire expression

Mistake: Ignoring operator precedence when pushing to stack
Fix: Compare precedence and pop higher or equal precedence operators before pushing new operator

Mistake: Not handling parentheses correctly
Fix: Push '(' to stack and pop until '(' when ')' is encountered

Summary

Converts an infix expression to postfix notation using a stack to reorder operators.

Use when you want to evaluate or simplify expressions without parentheses and operator precedence confusion.

The key insight is to use a stack to hold operators and pop them in order of precedence to build the postfix expression.

Practice

1. What is the main purpose of using a stack in converting an infix expression to postfix?

easy

A. To temporarily hold operators and manage their precedence

B. To store operands permanently

C. To reverse the order of operands

D. To count the number of operators

Solution

1. Step 1: Understand the role of stack in infix to postfix

   The stack is used to hold operators temporarily while processing the expression to respect operator precedence and associativity.

2. Step 2: Differentiate stack use from other data structures

   Operands are output immediately, not stored in stack. Stack is not used for counting or reversing operands.

3. Final Answer:

   To temporarily hold operators and manage their precedence -> Option A

4. Quick Check:

   Stack holds operators = A [OK]

Hint: Stack holds operators to manage precedence during conversion [OK]

Common Mistakes:

• Thinking stack stores operands
• Confusing stack with queue
• Believing stack reverses operands

2. Which of the following is the correct way to push an operator onto the stack in Java?

easy

A. stack.push(operator);

B. stack.insert(operator);

C. stack.add(operator);

D. stack.put(operator);

Solution

1. Step 1: Recall Java Stack method for adding elements

   Java's Stack class uses the push() method to add elements to the top of the stack.

2. Step 2: Identify incorrect methods

   Methods add(), insert(), and put() are not standard for Stack push operation in Java.

3. Final Answer:

   stack.push(operator); -> Option A

4. Quick Check:

   Use push() to add to stack [OK]

Hint: Use push() to add elements to Java stack [OK]

Common Mistakes:

• Using add() instead of push()
• Using non-existent methods like insert()
• Confusing stack with other collections

3. What is the postfix expression for the infix expression A + B * C?

medium

A. AB+C*

B. ABC*+

C. A+BC*

D. *ABC+

Solution

1. Step 1: Apply operator precedence in infix to postfix

   Multiplication (*) has higher precedence than addition (+), so B*C is evaluated first.

2. Step 2: Convert expression step-by-step

   Postfix: operands B and C followed by *, then operand A followed by + gives "ABC*+".

3. Final Answer:

   ABC*+ -> Option B

4. Quick Check:

   Multiplication before addition = ABC*+ [OK]

Hint: Multiply before add: operands then operator [OK]

Common Mistakes:

• Ignoring operator precedence
• Placing operators before operands
• Confusing postfix order

4. Given the following code snippet for infix to postfix conversion, what is the error?

if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
    while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(ch)) {
        postfix += stack.pop();
    }
    stack.push(ch);
}

medium

A. The precedence comparison should use > instead of >=

B. The stack should be checked for null before peek()

C. Operands are not handled in this snippet

D. The while loop condition is incorrect for operator associativity

Solution

1. Step 1: Understand operator associativity in infix to postfix

   For left-associative operators like '-', '+', '*', '/', pop operators with precedence >= current operator.

2. Step 2: Identify issue with while condition

   Using >= causes right-associative operators like '^' to be handled incorrectly; condition should consider associativity.

3. Final Answer:

   The while loop condition is incorrect for operator associativity -> Option D

4. Quick Check:

   Associativity affects while condition [OK]

Hint: Check operator associativity when comparing precedence [OK]

Common Mistakes:

• Ignoring operator associativity
• Not handling operands separately
• Assuming peek() can be null without check

5. Convert the infix expression (A + B) * (C - D) / E to postfix using stack. What is the correct postfix expression?

hard

A. AB+CD*E-/

B. AB+CD-E*/

C. AB+CD-*E/

D. AB+CD-*E

Solution

1. Step 1: Convert each parenthesis group to postfix

   "(A + B)" becomes "AB+" and "(C - D)" becomes "CD-".

2. Step 2: Combine with multiplication and division respecting precedence

   Multiply results: "AB+CD-*" then divide by E: "AB+CD-*E/".

3. Final Answer:

   AB+CD-*E/ -> Option C

4. Quick Check:

   Parentheses handled first, then * and / [OK]

Hint: Convert inside parentheses first, then apply operators [OK]

Common Mistakes:

• Ignoring parentheses order
• Mixing operator precedence
• Dropping operators or operands