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.

Practice

1. What is the main data structure used to evaluate a postfix expression?

easy

A. Stack

B. Queue

C. Array

D. Linked List

Solution

1. Step 1: Understand postfix evaluation process

   Postfix expressions are evaluated by scanning from left to right and using a data structure to store operands temporarily.

2. Step 2: Identify the suitable data structure

   A stack is used because it allows pushing operands and popping them when an operator is encountered, following Last-In-First-Out order.

3. Final Answer:

   Stack -> Option A

4. Quick Check:

   Postfix evaluation uses stack = Stack [OK]

Hint: Remember: postfix needs LIFO, so use stack [OK]

Common Mistakes:

• Confusing stack with queue
• Using array without stack operations
• Thinking linked list is primary for postfix

2. Which of the following is the correct syntax to push an integer value 'x' onto a stack named 's' in C?

easy

A. stack_push(x);

B. s.push(x);

C. push(x, s);

D. push(s, x);

Solution

1. Step 1: Understand typical stack push function signature

   In C, stack push usually takes the stack and the value to push as arguments, e.g., push(stack, value).

2. Step 2: Match the correct syntax

   push(s, x); matches the common pattern push(s, x); where 's' is the stack and 'x' is the value.

3. Final Answer:

   push(s, x); -> Option D

4. Quick Check:

   push(stack, value) = push(s, x) [OK]

Hint: Remember: push(stack, value) in C [OK]

Common Mistakes:

• Using object.method() syntax in C
• Swapping argument order
• Using undefined function names

3. What is the result of evaluating the postfix expression "6 2 3 + -" using a stack?

medium

A. 3

B. 1

C. 5

D. -1

Solution

1. Step 1: Evaluate postfix step-by-step

   Push 6, push 2, push 3. Encounter '+', pop 3 and 2, add: 2+3=5, push 5. Encounter '-', pop 5 and 6, subtract: 6-5=1.

2. Step 2: Verify final stack value

   After all operations, the stack has one value: 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   6 - (2 + 3) = 1 [OK]

Hint: Process operators by popping two operands [OK]

Common Mistakes:

• Subtracting in wrong order (operand2 - operand1)
• Adding instead of subtracting
• Not pushing intermediate results

4. Identify the error in this C code snippet for postfix evaluation:

char* expr = "5 9 8 + 4 6 * * 7 + *";
int i = 0;
while(expr[i] != '\0') {
  if(isdigit(expr[i])) push(stack, expr[i]);
  else { /* operator handling */ }
  i++;
}

medium

A. Pushing character digit instead of integer value

B. Using while loop instead of for loop

C. Missing stack initialization

D. Incorrect operator handling

Solution

1. Step 1: Check what is pushed onto stack

   The code pushes expr[i], which is a character like '5', not the integer 5.

2. Step 2: Explain why this is wrong

   Characters have ASCII codes; pushing '5' pushes 53, not integer 5, causing wrong calculations.

3. Final Answer:

   Pushing character digit instead of integer value -> Option A

4. Quick Check:

   Push integer, not char digit [OK]

Hint: Convert char to int before push: expr[i] - '0' [OK]

Common Mistakes:

• Pushing char instead of int
• Ignoring spaces in expression
• Not handling operators properly

5. Given the postfix expression "4 5 7 2 + - *", what is the final evaluated result using stack evaluation?

hard

A. -24

B. 16

C. -16

D. 24

Solution

1. Step 1: Evaluate inner expression 7 2 +

   Push 4, 5, 7, 2. '+' operator: pop 2 and 7, add 7+2=9, push 9.

2. Step 2: Evaluate next operator '-'

   Next operator '-', pop 9 and 5, subtract 5-9 = -4, push -4.

3. Step 3: Evaluate final operator '*'

   Pop -4 and 4, multiply 4 * -4 = -16, push -16.

4. Final Answer:

   -16 -> Option C

5. Quick Check:

   4 * (5 - (7 + 2)) = -16 [OK]

Hint: Evaluate inner expressions first, then combine [OK]

Common Mistakes:

• Wrong operator order in subtraction
• Not evaluating nested operations correctly
• Mixing up operand order in multiplication