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.

Analogy: Imagine a chef stacking ingredients in order to prepare a sandwich without needing to look back at the recipe each time.

Infix expression: A + B * C
Stack: empty
Postfix output: empty

Dry Run Walkthrough

Input: infix: A + B * C

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

Step 1: Read 'A', an operand, add to output

Output: A
Stack: empty

Why: Operands go directly to output

Step 2: Read '+', an operator, push to stack

Output: A
Stack: +

Why: Operators are stored to decide order later

Step 3: Read 'B', an operand, add to output

Output: A B
Stack: +

Why: Operands go directly to output

Step 4: Read '*', an operator, has higher precedence than '+', push to stack

Output: A B
Stack: + -> *

Why: Higher precedence operators go on top

Step 5: Read 'C', an operand, add to output

Output: A B C
Stack: + -> *

Why: Operands go directly to output

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

Output: A B C *
Stack: +

Why: Pop remaining operators in order

Step 7: Pop '+' from stack to output

Output: A B C * +
Stack: empty

Why: Finish by emptying stack

Result:

Output: A B C * +
Stack: empty

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) {
    if (top < MAX - 1) {
        stack[++top] = c;
    }
}

char pop() {
    if (top >= 0) {
        return stack[top--];
    }
    return '\0';
}

char peek() {
    if (top >= 0) {
        return stack[top];
    }
    return '\0';
}

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

void infixToPostfix(char* infix, char* postfix) {
    int i = 0, j = 0;
    char c;
    while ((c = infix[i++]) != '\0') {
        if (isalnum(c)) {
            postfix[j++] = c; // add operand to output
        } else {
            while (top != -1 && precedence(peek()) >= precedence(c)) {
                postfix[j++] = pop(); // pop higher or equal precedence operators
            }
            push(c); // push current operator
        }
    }
    while (top != -1) {
        postfix[j++] = pop(); // pop remaining operators
    }
    postfix[j] = '\0';
}

int main() {
    char infix[] = "A+B*C";
    char postfix[MAX];
    infixToPostfix(infix, postfix);
    printf("%s\n", postfix);
    return 0;
}

if (isalnum(c)) { postfix[j++] = c; // add operand to output }

Add operands directly to output

while (top != -1 && precedence(peek()) >= precedence(c)) { postfix[j++] = pop(); // pop higher or equal precedence operators }

Pop operators with higher or equal precedence before pushing new operator

push(c); // push current operator

Push current operator onto stack

while (top != -1) { postfix[j++] = pop(); // pop remaining operators }

Pop all remaining operators after processing input

Output

ABC*+

Complexity Analysis

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

Space: O(n) for the stack and output arrays to hold operators and result

vs Alternative: Compared to evaluating infix directly with parentheses, this method simplifies evaluation by reordering operators first, avoiding repeated precedence checks during evaluation

Edge Cases

Empty input string

Output is empty, no operators pushed

DSA C

while ((c = infix[i++]) != '\0')

Expression with single operand

Operand goes directly to output, stack remains empty

DSA C

if (isalnum(c)) {
    postfix[j++] = c;

Expression with multiple operators of same precedence

Operators popped in correct order due to precedence check

DSA C

while (top != -1 && precedence(peek()) >= precedence(c))

When to Use This Pattern

When you see expressions with operators and parentheses and need to evaluate or convert them, use the stack-based infix to postfix conversion to simplify processing order.

Common Mistakes

Mistake: Not popping operators with equal precedence before pushing new operator
Fix: Use >= in precedence comparison to pop operators of equal or higher precedence

Mistake: Adding operators directly to output instead of using stack
Fix: Always push operators to stack and pop based on precedence rules

Summary

Converts infix expressions to postfix notation using a stack to reorder operators.

Use when you want to evaluate or simplify expressions without parentheses.

The key insight is to use a stack to hold operators and pop them based on precedence rules.