Infix to Postfix Conversion Using Stack in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Infix to Postfix Conversion for Simple Expression

What is the output of the following Java code that converts the infix expression a+b*c to postfix notation using a stack?

DSA Java

import java.util.Stack;

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

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

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);

            if (Character.isLetterOrDigit(c)) {
                result.append(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                stack.pop();
            } else {
                while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }

        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(convert("a+b*c"));
    }
}

A "abc*+"

B "ab+c*"

C "a+bc*"

D "abc+*"

💡 Hint

Remember that multiplication has higher precedence than addition.

In infix to postfix conversion, operators with higher precedence are placed after their operands. Here, '*' has higher precedence than '+', so 'b*c' is converted to 'bc*' and then added to 'a' with '+', resulting in 'abc*+'.

❓ Predict Output

intermediate

Postfix Conversion Output with Parentheses

What is the output of the Java code converting the infix expression (a+b)*c to postfix notation using a stack?

DSA Java

import java.util.Stack;

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

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

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);

            if (Character.isLetterOrDigit(c)) {
                result.append(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                stack.pop();
            } else {
                while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }

        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(convert("(a+b)*c"));
    }
}

A "abc*+"

B "abc+*"

C "a+bc*"

D "ab+c*"

💡 Hint

Parentheses change the order of operations.

Parentheses force the addition 'a+b' to be evaluated first, so it becomes 'ab+'. Then multiplication by 'c' is applied, resulting in 'ab+c*'.

🔧 Debug

advanced

Identify the Error in Infix to Postfix Conversion Code

The following Java code is intended to convert infix expressions to postfix using a stack. However, it produces incorrect output for the expression a+b*c. What is the main logical error causing this?

DSA Java

import java.util.Stack;

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

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

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);

            if (Character.isLetterOrDigit(c)) {
                result.append(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                stack.pop();
            } else {
                while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }

        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(convert("a+b*c"));
    }
}

A The condition in the while loop should use <= instead of < to handle equal precedence operators correctly.

B The code does not handle parentheses correctly.

C The precedence function returns wrong values for operators.

D Operands are not appended to the result string.

💡 Hint

Check how operators with the same precedence are handled in the while loop.

Using < instead of <= in the while loop causes operators with equal precedence to be pushed without popping, breaking the correct order in postfix. Changing to <= fixes this.

❓ Predict Output

advanced

Output of Complex Infix Expression Conversion

What is the output of the Java code converting the infix expression a+b*(c^d-e)^(f+g*h)-i to postfix notation using a stack? Assume '^' has highest precedence and is right-associative.

DSA Java

import java.util.Stack;

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

    public static boolean isRightAssociative(char ch) {
        return ch == '^';
    }

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

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);

            if (Character.isLetterOrDigit(c)) {
                result.append(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                stack.pop();
            } else {
                while (!stack.isEmpty() && ((precedence(c) < precedence(stack.peek())) ||
                        (precedence(c) == precedence(stack.peek()) && !isRightAssociative(c))) &&
                        stack.peek() != '(') {
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }

        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(convert("a+b*(c^d-e)^(f+g*h)-i"));
    }
}

A "abcd^e-fg*h+^*+i-"

B "abcd^e-fgh*+^*+i-"

C "abcd^efg*h+^*-+i-"

D "-i+*^+h*gf-e^dcba"

💡 Hint

Remember that '^' is right-associative and has the highest precedence.

The expression is converted respecting operator precedence and associativity. The correct postfix is "abcd^e-fgh*+^*+i-".

🧠 Conceptual

expert

Stack Behavior in Infix to Postfix Conversion

During the conversion of the infix expression a+b*c to postfix using a stack, what is the state of the stack immediately after processing the character +?

A Stack contains '*'

B Stack is empty

C Stack contains only '+'

D Stack contains '+' and '*'

💡 Hint

Consider operator precedence and when operators are pushed or popped.

When '+' is processed first, the stack is empty so '+' is pushed. '*' comes later and has higher precedence, so it is pushed on top of '+'. Immediately after processing '+', only '+' is on the stack.

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