Infix to Postfix Conversion Using Stack in DSA Java - Build from Scratch

Infix to Postfix Conversion Using Stack

📖 Scenario: You are building a simple calculator program that converts mathematical expressions written in the usual way (called infix notation) into a form that computers find easier to calculate (called postfix notation).For example, the expression (A + B) * C in infix becomes AB+C* in postfix.

🎯 Goal: Build a Java program that uses a stack to convert an infix expression string into its postfix form.This will help you understand how stacks work and how expressions are processed step-by-step.

📋 What You'll Learn

Create a string variable called infix with the exact value "A+B*C"

Create an integer variable called precedence to help compare operator priority

Write a method called getPrecedence that returns the precedence of operators +, -, *, and /

Use a Stack<Character> to hold operators during conversion

Write a loop to process each character in infix and build the postfix string

Print the final postfix expression string exactly

💡 Why This Matters

🌍 Real World

Converting infix expressions to postfix is a key step in calculators and compilers to evaluate mathematical expressions correctly.

💼 Career

Understanding stacks and expression parsing is important for software developers working on interpreters, compilers, and calculators.

1

Create the Infix Expression String

Create a string variable called infix and set it to the exact value "A+B*C".

DSA Java

// Create the infix expression string
// Your code here

Hint

Use String infix = "A+B*C"; to create the infix expression.

2

Add Operator Precedence Method

Add a static method called getPrecedence that takes a char operator and returns an int representing its precedence: '+' and '-' have precedence 1, '*' and '/' have precedence 2, and any other character returns -1.

DSA Java

public class InfixToPostfix {
    public static void main(String[] args) {
        String infix = "A+B*C";
    }

    // Add getPrecedence method below
    // Your code here
}

Hint

Use if-else to return precedence values for operators.

3

Convert Infix to Postfix Using Stack

Inside the main method, create a Stack<Character> called stack and a string variable called postfix initialized to an empty string. Then write a for loop to process each character ch in infix. If ch is a letter (operand), add it to postfix. If ch is an operator, pop from stack to postfix while the top of stack has an operator with precedence greater or equal to ch. Then push ch onto stack. After the loop, pop all remaining operators from stack to postfix.

DSA Java

import java.util.Stack;

public class InfixToPostfix {
    public static void main(String[] args) {
        String infix = "A+B*C";
        // Create stack and postfix string
        // Your code here
    }

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

Hint

Use a stack to hold operators and build the postfix string step-by-step.

4

Print the Postfix Expression

Add a System.out.println statement at the end of the main method to print the postfix string exactly.

DSA Java

import java.util.Stack;

public class InfixToPostfix {
    public static void main(String[] args) {
        String infix = "A+B*C";
        Stack stack = new Stack();
        String postfix = "";

        for (int i = 0; i = getPrecedence(ch)) {
                    postfix += stack.pop();
                }
                stack.push(ch);
            }
        }

        while (!stack.isEmpty()) {
            postfix += stack.pop();
        }

        // Print the postfix expression
        // Your code here
    }

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

Hint

Use System.out.println(postfix); to print the final 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