Infix to Postfix Conversion Using Stack in DSA C++

Mental Model

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

Analogy: Imagine a chef stacking ingredients in order to prepare a dish without mixing them too early; the stack helps keep operators waiting until it's their turn.

Infix: A + B * C
Stack: []
Postfix: []

Dry Run Walkthrough

Input: infix expression: A + B * C

Goal: Convert the infix expression to postfix notation: A B C * +

Step 1: Read 'A', it's an operand, add to postfix

Stack: []
Postfix: [A]

Why: Operands go directly to the output

Step 2: Read '+', stack is empty, push '+'

Stack: [+]
Postfix: [A]

Why: Operators go to stack to wait for correct order

Step 3: Read 'B', it's an operand, add to postfix

Stack: [+]
Postfix: [A B]

Why: Operands go directly to output

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

Stack: [+ *]
Postfix: [A B]

Why: Higher precedence operators wait on top of lower ones

Step 5: Read 'C', it's an operand, add to postfix

Stack: [+ *]
Postfix: [A B C]

Why: Operands go directly to output

Step 6: End of expression, pop '*' from stack to postfix

Stack: [+]
Postfix: [A B C *]

Why: Pop remaining operators in correct order

Step 7: Pop '+' from stack to postfix

Stack: []
Postfix: [A B C * +]

Why: Finish by emptying stack

Result:

Postfix: A B C * +

Annotated Code

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(const string& infix) {
    stack<char> st;
    string postfix;
    for (char ch : infix) {
        if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) {
            postfix += ch; // add operand to postfix
        } else if (ch == '(') {
            st.push(ch); // push '(' to stack
        } else if (ch == ')') {
            while (!st.empty() && st.top() != '(') {
                postfix += st.top();
                st.pop(); // pop until '(' found
            }
            if (!st.empty()) st.pop(); // remove '('
        } else { // operator
            while (!st.empty() && precedence(st.top()) >= precedence(ch)) {
                postfix += st.top();
                st.pop(); // pop higher or equal precedence operators
            }
            st.push(ch); // push current operator
        }
    }
    while (!st.empty()) {
        postfix += st.top();
        st.pop(); // pop remaining operators
    }
    return postfix;
}

int main() {
    string infix = "A+B*C";
    string postfix = infixToPostfix(infix);
    cout << postfix << endl;
    return 0;
}

if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) { postfix += ch; // add operand to postfix }

Add operands directly to postfix output

else if (ch == '(') { st.push(ch); // push '(' to stack }

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

else if (ch == ')') { while (!st.empty() && st.top() != '(') { postfix += st.top(); st.pop(); // pop until '(' found } if (!st.empty()) st.pop(); // remove '(' }

Pop operators until '(' to close sub-expression

else { // operator while (!st.empty() && precedence(st.top()) >= precedence(ch)) { postfix += st.top(); st.pop(); // pop higher or equal precedence operators } st.push(ch); // push current operator }

Pop operators with higher or equal precedence before pushing current

while (!st.empty()) { postfix += st.top(); st.pop(); // pop remaining operators }

Pop all remaining operators after processing input

Output

ABC*+

Complexity Analysis

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

Space: O(n) for the stack and output string in the worst case when all operators are stacked

vs Alternative: Compared to evaluating infix directly with recursion or multiple passes, using a stack for postfix conversion is more efficient and simpler to implement

Edge Cases

Empty expression

Returns empty postfix string without error

DSA C++

for (char ch : infix) { ... } // loop simply does not run

Expression with parentheses

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

DSA C++

else if (ch == ')') { while (!st.empty() && st.top() != '(') { ... } if (!st.empty()) st.pop(); }

Expression with multiple digit numbers or variables

Treats each character as separate operand; does not combine digits

DSA C++

if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) { postfix += 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.

Common Mistakes

Mistake: Not popping all operators from stack at the end, leaving incomplete postfix
Fix: Add a final loop to pop all remaining operators after processing input

Mistake: Ignoring operator precedence and popping too early or too late
Fix: Use a precedence function and pop only operators with higher or equal precedence before pushing new operator

Mistake: Not handling parentheses correctly, causing wrong output
Fix: Push '(' on stack and pop until '(' when ')' is encountered, then remove '('

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 complexity.

The key insight is to use a stack to hold operators until it's their turn to appear in the output based on precedence and parentheses.

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