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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Postfix Conversion for Simple Expression

What is the output postfix expression after converting the infix expression a+b*c using the standard infix to postfix algorithm with stack?

DSA C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

string infixToPostfix(string infix) {
    stack<char> s;
    string postfix = "";
    for (char c : infix) {
        if (isalnum(c)) {
            postfix += c;
        } else {
            while (!s.empty() && precedence(s.top()) >= precedence(c)) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }
    return postfix;
}

int main() {
    string infix = "a+b*c";
    cout << infixToPostfix(infix) << endl;
    return 0;
}

A abc*+

B ab+c*

C a+bc*

D abc+*

💡 Hint

Remember that multiplication (*) has higher precedence than addition (+).

In infix expression 'a+b*c', multiplication has higher precedence, so 'b*c' is evaluated first, then added to 'a'. The postfix is 'abc*+'.

❓ Predict Output

intermediate

Postfix Conversion Output with Parentheses

What is the postfix expression output after converting the infix expression (a+b)*c using the infix to postfix stack algorithm?

DSA C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

string infixToPostfix(string infix) {
    stack<char> s;
    string postfix = "";
    for (char c : infix) {
        if (isalnum(c)) {
            postfix += c;
        } else if (c == '(') {
            s.push(c);
        } else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            s.pop();
        } else {
            while (!s.empty() && precedence(s.top()) >= precedence(c)) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }
    return postfix;
}

int main() {
    string infix = "(a+b)*c";
    cout << infixToPostfix(infix) << endl;
    return 0;
}

A abc*+

B a+bc*

C ab+*c

D ab+c*

💡 Hint

Parentheses change the order of operations, forcing addition before multiplication.

Parentheses cause 'a+b' to be evaluated first, then multiplied by 'c'. The postfix is 'ab+c*'.

🔧 Debug

advanced

Identify the Error in Postfix Conversion Code

Given the following code snippet for infix to postfix conversion, what error will it cause when run with input a+b*c?

DSA C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

string infixToPostfix(string infix) {
    stack<char> s;
    string postfix = "";
    for (char c : infix) {
        if (isalnum(c)) {
            postfix += c;
        } else {
            while (!s.empty() && precedence(s.top()) > precedence(c)) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }
    return postfix;
}

int main() {
    string infix = "a+b*c";
    cout << infixToPostfix(infix) << endl;
    return 0;
}

A Output is 'abc*+' as expected

B Output is 'ab+c*+' causing wrong postfix expression

C Output is 'ab+c*' which is incorrect

D Output is 'abc*+' but with extra operators at the end

💡 Hint

Check the condition in the while loop comparing operator precedence.

The code uses '>' instead of '>=' in the while loop, so operators with equal precedence are not popped, causing wrong order.

🧠 Conceptual

advanced

Stack Behavior in Infix to Postfix Conversion

During the conversion of the infix expression a+b*c-d/e to postfix, what is the content of the stack just before processing the last operand e?

A ['+', '*', '-']

B ['-', '/']

C ['+', '*', '-','/']

D ['*', '-', '/']

💡 Hint

Remember operator precedence and when operators are popped from the stack.

After processing 'a+b*c-d/', the stack contains '-' and '/' because '+' and '*' have been popped due to precedence rules.

🚀 Application

expert

Final Postfix Expression for Complex Infix

What is the postfix expression after converting the infix expression (a+b)*(c-d)/e+f using the infix to postfix algorithm with stack?

A ab+cd-*e/f+

B ab+cd-*ef/+

C +f/e*-dc+ba

D ab+cd* -e/f+

💡 Hint

Break down the expression by parentheses and operator precedence step-by-step.

The postfix is 'ab+cd-*e/f+'. First '(a+b)' and '(c-d)' are converted, then multiplied, divided by 'e', and finally added to 'f'.

Practice

1. What is the main purpose of using a stack in Infix to Postfix Conversion?

easy

A. To count the number of operators

B. To temporarily hold operators and manage their precedence

C. To reverse the order of the expression

D. To store operands permanently

Solution

1. Step 1: Understand the role of stack in conversion

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

2. Step 2: Identify what is stored in the stack

   Operands are directly added to the output, while operators are pushed to the stack to manage order and precedence.

3. Final Answer:

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

4. Quick Check:

   Stack holds operators = D [OK]

Hint: Stack holds operators to manage precedence [OK]

Common Mistakes:

• Thinking stack stores operands
• Believing stack reverses the entire expression
• Confusing stack role with counting operators

2. Which of the following is the correct syntax to push an operator onto a stack named st in C++?

easy

A. st.push(operator);

B. push(st, operator);

C. st.add(operator);

D. push.operator(st);

Solution

1. Step 1: Recall C++ stack push syntax

   In C++, the standard stack uses the member function push() to add elements.

2. Step 2: Match correct syntax

   The correct syntax is st.push(operator); where st is the stack object.

3. Final Answer:

   st.push(operator); -> Option A

4. Quick Check:

   Stack push method = st.push() [OK]

Hint: Use st.push(element) to add to stack [OK]

Common Mistakes:

• Using non-member functions like push(st, element)
• Using incorrect method names like add()
• Incorrect dot notation like push.operator()

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

medium

A. A+BC*

B. AB+C*

C. ABC*+

D. *ABC+

Solution

1. Step 1: Apply operator precedence rules

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

2. Step 2: Convert to postfix

   Postfix places operands first, then operator: B C * then A +, resulting in ABC*+.

3. Final Answer:

   ABC*+ -> Option C

4. Quick Check:

   Postfix of A + B * C = ABC*+ [OK]

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

Common Mistakes:

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

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

std::stack<char> st;
std::string infix = "A+B*C";
std::string postfix = "";
for (char ch : infix) {
  if (isalnum(ch))
    postfix += ch;
  else {
    while (!st.empty() && st.top() >= ch) {
      postfix += st.top();
      st.pop();
    }
    st.push(ch);
  }
}
while (!st.empty()) {
  postfix += st.top();
  st.pop();
}

medium

A. Operator precedence comparison is incorrect

B. Operands are not added to postfix

C. Stack is not used for operators

D. Postfix string is not initialized

Solution

1. Step 1: Analyze operator precedence check

   The code compares operators using >= directly on characters, which does not correctly reflect operator precedence.

2. Step 2: Identify correct precedence handling

   Operator precedence should be checked using a function that assigns precedence values, not character comparison.

3. Final Answer:

   Operator precedence comparison is incorrect -> Option A

4. Quick Check:

   Operator precedence needs function, not char compare [OK]

Hint: Use precedence function, not char comparison [OK]

Common Mistakes:

• Comparing operators as characters
• Ignoring precedence rules
• Not popping stack correctly

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: Handle parentheses and operator precedence

   Parentheses force A+B and C-D to be evaluated first, then multiply results, then divide by E.

2. Step 2: Convert step-by-step to postfix

   A B + (for A+B), C D - (for C-D), then multiply: AB+CD-*, finally divide by E: AB+CD-*E/.

3. Final Answer:

   AB+CD-*E/ -> Option D

4. Quick Check:

   Postfix of (A+B)*(C-D)/E = AB+CD-*E/ [OK]

Hint: Process parentheses first, then operators by precedence [OK]

Common Mistakes:

• Ignoring parentheses order
• Mixing operator order
• Placing division before multiplication