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

Time Complexity: Evaluate Postfix Expression Using Stack

O(n)

Understanding Time Complexity

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

Specifically, how does the number of steps grow when we process more symbols in the expression?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function evaluatePostfix(expression: string): number {
  const stack: number[] = [];
  for (const char of expression) {
    if (!isNaN(Number(char))) {
      stack.push(Number(char));
    } else {
      const b = stack.pop()!;
      const a = stack.pop()!;
      if (char === '+') stack.push(a + b);
      else if (char === '-') stack.push(a - b);
      else if (char === '*') stack.push(a * b);
      else if (char === '/') stack.push(a / b);
    }
  }
  return stack.pop()!;
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the expression once.
• How many times: Exactly once for each character in the input string.

How Execution Grows With Input

As the expression length grows, the number of steps grows directly with it.

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

Pattern observation: The time grows linearly with the number of characters in the expression.

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 we pop and push inside the loop, the time is more than linear, maybe quadratic."

[OK] Correct: Each character is processed once, and each push/pop is constant time, so total time stays proportional to input length.

Interview Connect

Understanding this linear time complexity helps you explain why stack-based evaluation is efficient and expected in coding 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. Linked List

B. Queue

C. Array

D. Stack

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 allows pushing operands and popping them when an operator is encountered, making it ideal for postfix evaluation.

3. Final Answer:

   Stack -> Option D

4. Quick Check:

   Postfix evaluation uses Stack [OK]

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

Common Mistakes:

• Confusing stack with queue
• Thinking array alone can manage operations
• Using linked list without stack behavior

2. Which of the following is the correct way to push a number onto a stack in TypeScript?

easy

A. stack.push(number);

B. stack.add(number);

C. stack.insert(number);

D. stack.enqueue(number);

Solution

1. Step 1: Recall stack methods in TypeScript

   Stacks in TypeScript are usually arrays, and pushing an element uses the push() method.

2. Step 2: Identify correct method

   push() adds an element to the end of the array, simulating stack push operation.

3. Final Answer:

   stack.push(number); -> Option A

4. Quick Check:

   Use push() to add to stack [OK]

Hint: Use push() to add elements to stack in TypeScript [OK]

Common Mistakes:

• Using add() or insert() which are not array methods
• Confusing enqueue() with queue operation
• Trying to use non-existent stack methods

3. What is the output of evaluating the postfix expression "6 2 3 + - 3 8 2 / + *" using a stack?

medium

A. 7

B. 36

C. 24

D. 30

Solution

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

   Expression: 6 2 3 + - 3 8 2 / + *
   Push 6 -> [6]
   Push 2 -> [6, 2]
   Push 3 -> [6, 2, 3]
   + : pop 3 (right), pop 2 (left) -> 2 + 3 = 5 -> [6, 5]
   - : pop 5 (r), pop 6 (l) -> 6 - 5 = 1 -> [1]
   Push 3 -> [1, 3]
   Push 8 -> [1, 3, 8]
   Push 2 -> [1, 3, 8, 2]
   / : pop 2 (r), 8 (l) -> 8 / 2 = 4 -> [1, 3, 4]
   + : pop 4 (r), 3 (l) -> 3 + 4 = 7 -> [1, 7]
   * : pop 7 (r), 1 (l) -> 1 * 7 = 7 -> [7]

2. Step 2: Confirm final stack value

   Final result: 7

3. Final Answer:

   7 -> Option A

4. Quick Check:

   Postfix evaluation result = 7 [OK]

Hint: Evaluate stepwise, push numbers, pop two for operators [OK]

Common Mistakes:

• Mixing operand order in subtraction/division
• Not popping two operands for each operator
• Assuming division is integer without checking

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

function evalPostfix(expr: string): number {
  const stack: number[] = [];
  for (const ch of expr.split(' ')) {
    if (!isNaN(Number(ch))) {
      stack.push(Number(ch));
    } else {
      const a = stack.pop();
      const b = stack.pop();
      switch (ch) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(b - a); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(b / a); break;
      }
    }
  }
  return stack.pop()!;
}

medium

A. Operands are popped in wrong order for addition and multiplication

B. Missing check for empty stack before popping

C. Operands are popped in wrong order for subtraction and division

D. Using Number() instead of parseInt() causes errors

Solution

1. Step 1: Check for potential runtime errors

   The code pops from the stack without verifying if there are enough elements. For operators, it needs at least 2 elements; at the end, at least 1.

2. Step 2: Identify the issue

   Missing check for empty stack (or insufficient elements) before popping can cause runtime crashes.

3. Final Answer:

   Missing check for empty stack before popping -> Option B

4. Quick Check:

   Always validate stack size before pop [OK]

Hint: Check stack.length before every pop() to avoid errors [OK]

Common Mistakes:

• Swapping operand order for subtraction/division
• Not checking stack empty before pop
• Confusing Number() and parseInt() usage

5. Given the postfix expression "5 1 2 + 4 * + 3 -", what is the final result after evaluation using a stack?

hard

A. 17

B. 13

C. 14

D. 10

Solution

1. Step 1: Evaluate inner expressions stepwise

   Push 5, 1, 2
   '+' pops 2 and 1, sums 3; stack: [5,3]
   Push 4
   '*' pops 4 and 3, multiplies 12; stack: [5,12]
   '+' pops 12 and 5, sums 17; stack: [17]
   Push 3
   '-' pops 3 and 17, computes 17-3=14; stack: [14]

2. Step 2: Confirm final stack value

   Only one value remains: 14, which is the final result.

3. Final Answer:

   14 -> Option C

4. Quick Check:

   Postfix evaluation result = 14 [OK]

Hint: Evaluate operators stepwise, watch operand order carefully [OK]

Common Mistakes:

• Adding instead of subtracting last step
• Mixing operand order in subtraction
• Skipping multiplication step