Evaluate Postfix Expression Using Stack in DSA Typescript

Mental Model

Use a stack to keep numbers until an operator appears, then combine the last two numbers with that operator.

Analogy: Imagine stacking plates with numbers. When you get a cooking instruction (operator), you take the last two plates, mix them, and put the result back on top.

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

Initial stack empty -> []

Dry Run Walkthrough

Input: Postfix expression: 2 3 + 4 *

Goal: Calculate the final value 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 result

Stack: [5]

Why: Operator means combine last two numbers and push result back

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 result

Stack: [20]

Why: Operator combines last two numbers again

Result:

Stack: [20]
Final result: 20

Annotated Code

DSA Typescript

class Stack {
  private items: number[] = [];

  push(element: number): void {
    this.items.push(element);
  }

  pop(): number | undefined {
    return this.items.pop();
  }

  peek(): number | undefined {
    return this.items[this.items.length - 1];
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

function evaluatePostfix(expression: string): number {
  const stack = new Stack();
  const tokens = expression.split(' ');

  for (const token of tokens) {
    if (!isNaN(Number(token))) {
      stack.push(Number(token)); // push number
    } else {
      const b = stack.pop(); // pop second operand
      const a = stack.pop(); // pop first operand
      if (a === undefined || b === undefined) {
        throw new Error('Invalid expression');
      }
      let result: number;
      switch (token) {
        case '+':
          result = a + b; // add
          break;
        case '-':
          result = a - b; // subtract
          break;
        case '*':
          result = a * b; // multiply
          break;
        case '/':
          result = a / b; // divide
          break;
        default:
          throw new Error('Unknown operator');
      }
      stack.push(result); // push result
    }
  }

  const finalResult = stack.pop();
  if (finalResult === undefined || !stack.isEmpty()) {
    throw new Error('Invalid expression');
  }
  return finalResult!;
}

// Driver code
const expression = '2 3 + 4 *';
const result = evaluatePostfix(expression);
console.log(result);

stack.push(Number(token)); // push number

push number tokens onto stack to wait for operators

const b = stack.pop(); // pop second operand

pop last number for right operand of operator

const a = stack.pop(); // pop first operand

pop second last number for left operand

switch (token) { ... }

apply operator to operands a and b

stack.push(result); // push result

push computed result back onto stack

const finalResult = stack.pop();

pop final result after processing all tokens

if (finalResult === undefined || !stack.isEmpty()) { throw new Error('Invalid expression'); }

check for missing result or leftover items indicating invalid expression

Output

20

Complexity Analysis

Time: O(n) because we process each token once in the expression

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

vs Alternative: Compared to evaluating infix expressions which require operator precedence handling, postfix evaluation is simpler and faster using a stack

Edge Cases

Empty expression

Throws 'Invalid expression' error because no operands exist

DSA Typescript

if (finalResult === undefined || !stack.isEmpty()) { throw new Error('Invalid expression'); }

Expression with single number only

Returns that number as result

DSA Typescript

const finalResult = stack.pop();

Expression with invalid operator

Throws 'Unknown operator' error

DSA Typescript

default: throw new Error('Unknown operator');

When to Use This Pattern

When you see an expression with operators after operands and no parentheses, use the stack evaluation pattern for postfix expressions because it handles order naturally.

Common Mistakes

Mistake: Popping operands in wrong order (e.g., first popped is left operand)
Fix: Pop second operand first, then first operand to preserve correct order

Mistake: Not checking for invalid expressions with too few operands
Fix: Add checks after popping operands to throw error if undefined

Summary

Evaluates a postfix expression by using a stack to store operands and applying operators to the last two operands.

Use when you need to compute the value of postfix expressions efficiently without worrying about operator precedence.

The key insight is to push numbers on a stack and apply operators by popping the last two numbers, then pushing the result back.

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