Evaluate Postfix Expression Using Stack in DSA C - Time & Space Complexity

Time Complexity: Evaluate Postfix Expression Using Stack

O(n)

Understanding Time Complexity

We analyze how the time needed to evaluate a postfix expression changes as the expression gets longer.

We want to know how the number of steps grows with the size of the expression.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int evaluatePostfix(char* expr) {
    Stack s;
    initStack(&s); // Initialize the stack before use
    for (int i = 0; expr[i] != '\0'; i++) {
        if (isdigit(expr[i])) {
            push(&s, expr[i] - '0');
        } else {
            int val2 = pop(&s);
            int val1 = pop(&s);
            push(&s, applyOp(val1, val2, expr[i]));
        }
    }
    return pop(&s);
}
    

This code evaluates a postfix expression by scanning each character once and using a stack to compute the result.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single loop scanning each character in the expression once.
• How many times: Exactly once per character in the input expression.

How Execution Grows With Input

Each character is processed once, so the total steps grow directly with expression length.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows linearly as the expression gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to evaluate grows in direct proportion to the length of the postfix expression.

Common Mistake

[X] Wrong: "Because of the stack operations, the time complexity is more than linear, maybe quadratic."

[OK] Correct: Each character is pushed or popped at most once, so stack operations add only constant work per character, keeping the total time linear.

Interview Connect

Understanding this linear time complexity shows you can analyze how simple data structures like stacks help solve problems efficiently, a key skill in interviews.

Self-Check

"What if the expression included multi-digit numbers separated by spaces? How would the time complexity change?"

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