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

Infix to Postfix Conversion Using Stack

📖 Scenario: Imagine you are building a simple calculator that reads expressions written in the usual way (like 3 + 4 * 2) and you want to convert these expressions into a form that computers find easier to evaluate (called postfix notation).This project will help you convert an expression written in the normal way (infix) into postfix using a stack.

🎯 Goal: You will write a C++ program that takes an infix expression as input and converts it into postfix notation using a stack.

📋 What You'll Learn

Create a string variable to hold the infix expression.

Create a stack to help with the conversion process.

Write a function to check operator precedence.

Write the core logic to convert infix to postfix using the stack.

Print the final postfix expression.

💡 Why This Matters

🌍 Real World

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

💼 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-D/E".

DSA C++

# Create the infix expression string
# Your code here

Hint

Use string infix = "A+B*C-D/E"; to create the expression.

2

Create a stack for characters

Add a stack of characters called st below the infix declaration to help with the conversion.

DSA C++

#include 
#include 
#include 

using namespace std;

int main() {
    string infix = "A+B*C-D/E";
    // Create a stack of characters called st
    // Your code here
    return 0;
}

Hint

Use stack<char> st; to create the stack.

3

Write a function to get operator precedence

Add a function called precedence that takes a char op and returns an int representing its precedence. Use these rules: '+' and '-' return 1, '*' and '/' return 2, and any other character returns 0.

DSA C++

#include 
#include 
#include 

using namespace std;

// Write a function called precedence that returns the precedence of operators
int precedence(char op) {
    // Your code here
}

int main() {
    string infix = "A+B*C-D/E";
    stack st;
    return 0;
}

Hint

Use if statements to check the operator and return the correct precedence number.

4

Convert infix to postfix and print the result

Write the core logic inside main() to convert the infix expression to postfix using the stack st. Create a string postfix to store the result. Use a for loop with variable ch to iterate over infix. For each character: if it is a letter (operand), add it to postfix. If it is an operator, pop from st to postfix while the top of st has higher or equal precedence. Then push the current operator. After the loop, pop all remaining operators from st to postfix. Finally, print postfix.

DSA C++

#include 
#include 
#include 

using namespace std;

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

int main() {
    string infix = "A+B*C-D/E";
    stack st;
    string postfix = "";
    // Convert infix to postfix using the stack
    // Your code here
    return 0;
}

Hint

Remember to add operands directly to postfix. For operators, pop from the stack while the top has higher or equal precedence, then push the current operator. After the loop, pop all remaining operators.

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