Evaluate Postfix Expression Using Stack in DSA C

Mental Model

Use a stack to keep numbers until an operator comes, then combine the last two numbers using that operator and push the result back.

Analogy: Imagine stacking plates with numbers. When you get an operator, you take the top two plates, do the math, and put one new plate back on top.

Stack (top at right): []
Expression: 2 3 + 4 *

Initial stack empty, ready to push numbers.

Dry Run Walkthrough

Input: postfix expression: 2 3 + 4 *

Goal: Calculate the final result of the postfix expression using a stack

Step 1: Read '2', push onto stack

Stack: [2]

Why: Numbers go directly onto the stack to wait for operators

Step 2: Read '3', push onto stack

Stack: [2, 3]

Why: Keep numbers on stack until operator appears

Step 3: Read '+', pop 3 and 2, add them (2+3=5), push 5

Stack: [5]

Why: Operator means combine last two numbers and push result

Step 4: Read '4', push onto stack

Stack: [5, 4]

Why: Push number to stack waiting for next operator

Step 5: Read '*', pop 4 and 5, multiply (5*4=20), push 20

Stack: [20]

Why: Combine last two numbers with operator and push result

Result:

Stack: [20]
Final result: 20

Annotated Code

DSA C

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

#define MAX 100

typedef struct {
    int items[MAX];
    int top;
} Stack;

void init(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX - 1;
}

void push(Stack *s, int val) {
    if (!isFull(s)) {
        s->items[++(s->top)] = val;
    }
}

int pop(Stack *s) {
    if (!isEmpty(s)) {
        return s->items[(s->top)--];
    }
    return -1; // error value
}

int evaluatePostfix(const char *expr) {
    Stack s;
    init(&s);
    int i = 0;
    while (expr[i] != '\0') {
        if (isspace(expr[i])) {
            i++;
            continue;
        }
        if (isdigit(expr[i])) {
            int num = 0;
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            push(&s, num); // push number
        } else {
            int val2 = pop(&s); // pop second operand
            int val1 = pop(&s); // pop first operand
            int res = 0;
            switch (expr[i]) {
                case '+': res = val1 + val2; break;
                case '-': res = val1 - val2; break;
                case '*': res = val1 * val2; break;
                case '/': res = val1 / val2; break;
            }
            push(&s, res); // push result
            i++;
        }
    }
    return pop(&s); // final result
}

int main() {
    const char *expr = "2 3 + 4 *";
    int result = evaluatePostfix(expr);
    printf("%d\n", result);
    return 0;
}

push(&s, num); // push number

push each number onto the stack as we read it

int val2 = pop(&s); // pop second operand

pop the second operand for the operator

int val1 = pop(&s); // pop first operand

pop the first operand for the operator

push(&s, res); // push result

push the result of operation back onto the stack

Output

20

Complexity Analysis

Time: O(n) because we scan the expression once and each character is processed in constant time

Space: O(n) because in worst case all numbers are pushed onto the stack

vs Alternative: Compared to evaluating infix expressions which require operator precedence handling and possibly multiple passes, postfix evaluation is simpler and faster with a single stack pass

Edge Cases

Empty expression

Returns -1 or error because no operands to evaluate

DSA C

return pop(&s); // final result

Single number expression like '5'

Returns the number itself as result

DSA C

push(&s, num); // push number

Division by zero in expression

Undefined behavior, code does not handle division by zero explicitly

DSA C

case '/': res = val1 / val2; break;

When to Use This Pattern

When you see an expression in postfix notation and need to calculate its value, use the stack evaluation pattern because it handles operators and operands in one pass without precedence rules.

Common Mistakes

Mistake: Popping operands in wrong order causing incorrect results
Fix: Always pop second operand first, then first operand to maintain correct operation order

Mistake: Not handling multi-digit numbers correctly
Fix: Accumulate digits into a number before pushing to stack instead of pushing single digits

Summary

Evaluates a postfix expression by using a stack to store operands and applying operators as they appear.

Use when you have postfix expressions and want a simple, one-pass evaluation without worrying about operator precedence.

The key insight is to push numbers on the stack and when an operator comes, pop two numbers, apply the operator, and push the result back.