Lesson 10: Infix to Postfix Conversion Using Stack

Infix to Postfix Conversion Using Stack

Infix Expression:
An expression in which operators are written between operands, e.g.,

A + B * C

Postfix Expression (Reverse Polish Notation):
An expression in which operators come after operands, e.g.,

A B C * +

Why convert infix to postfix?

• Postfix expressions do not require parentheses

• They are easier to evaluate using a stack

• Widely used in compiler design and calculators

Have you practiced the last lesson? Introduction to Stack in C++

🔹 Real-World Use Case

• Evaluators in calculators: Convert 2 + 3 * 4 → 2 3 4 * + to compute efficiently

• Compiler parsing: Translating mathematical expressions into a machine-friendly format

• Expression evaluation in programming

🔹 Algorithm for Infix to Postfix Conversion

1. Initialize an empty stack for operators.

2. Scan the infix expression from left to right:

   • If operand, add to postfix expression.

   • If ‘(’, push to stack.

   • If ‘)’, pop from stack to postfix until ‘(’ is found.

   • If operator, pop operators with higher or equal precedence from stack to postfix, then push current operator.

3. Pop any remaining operators from the stack to postfix.

Operator Precedence (Highest → Lowest):

^ > * / > + –

💻 C++ Implementation

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

// Function to return precedence of operators
int precedence(char op) {
    if(op == '^') return 3;
    if(op == '*' || op == '/') return 2;
    if(op == '+' || op == '-') return 1;
    return 0;
}

bool isOperator(char c) {
    return (c=='+' || c=='-' || c=='*' || c=='/' || c=='^');
}

// Function to convert infix to postfix
string infixToPostfix(string infix) {
    stack<char> s;
    string postfix = "";

    for(char c : infix) {
        if((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) {
            // Operand
            postfix += c;
        }
        else if(c == '(') {
            s.push(c);
        }
        else if(c == ')') {
            while(!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            if(!s.empty()) s.pop(); // Remove '('
        }
        else if(isOperator(c)) {
            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-D)";
    cout << "Infix Expression: " << infix << endl;
    cout << "Postfix Expression: " << infixToPostfix(infix) << endl;
    return 0;
}

🔹 Sample Input & Output

Input:
A + B * (C – D)

Output:
A B C D – * +

✅ Key Points

• Stack stores operators temporarily.

• Operands are added immediately to the output.

• Handles parentheses and precedence automatically.

• Can be extended to evaluate numeric postfix expressions.

💡 Advantages of Postfix Expressions

• No parentheses required

• Evaluation is faster

• Suitable for stack-based computation

Interview Questions & Answers – Infix to Postfix Using Stack

1. What is the difference between infix and postfix expressions

• Infix: Operators are between operands (e.g., A + B)

• Postfix: Operators come after operands (e.g., A B +)

2. Why do we use postfix expressions?
   
   Postfix expressions do not require parentheses and are easier to evaluate using a stack.

3. What is a stack’s role in converting infix to postfix?
   
   A stack temporarily stores operators while operands are added immediately to the postfix expression.

4. How do you handle operator precedence in infix to postfix conversion?
   
   Before pushing a new operator onto the stack, pop all operators from the stack with higher or equal precedence to ensure correct order in postfix.

5. How are parentheses handled?

• ( is pushed onto the stack

• ) causes operators to pop from the stack until ( is encountered

6. What is the time complexity of infix to postfix conversion?
   O(n), where n is the number of characters in the expression.

7. Can the algorithm handle multi-digit operands or variables?
   Yes, by scanning numbers or variable names as a single token instead of a single character.

8. What is the space complexity of infix to postfix conversion?
   O(n) for the stack, where n is the number of operators in the expression.

9. Why is a stack suitable for expression evaluation?
   
   Because stacks follow LIFO, they naturally handle nested expressions and operator precedence efficiently.

10. How would you evaluate a postfix expression after conversion?

11. 10. 
        Use a stack:

    • Push operands to the stack

    • On encountering an operator, pop the required number of operands, perform operation, and push result back.

    11. What could go wrong if you forget to pop operators after processing the entire infix expression?
        
        The resulting postfix expression would be incorrect and may cause runtime errors during evaluation.

    12. Why is this algorithm commonly used in compilers?
        
        Because postfix simplifies machine-level evaluation and removes the need for parentheses in parsing expressions.

Are you interested in developing mobile application development skills? You may visit the link below:

https://onlineskilllab.com/2025/11/18/how-to-build-a-complete-flutter-authentication-system-with-firebase-login-signup-reset-password-dashboard/

If you are learning and enjoying, subscribe to our blog for daily updates.