Evaluate Postfix Expression Using Stack in DSA Typescript - Execution Trace

Concept Flow - Evaluate Postfix Expression Using Stack

Read next token

↓

Is token a number?

Yes→Push number onto stack

No↓

Pop two numbers from stack

↓

Apply operator to popped numbers

↓

Push result back onto stack

↓

More tokens?

Yes→Read next token

No↓

Final result is top of stack

Process each token: push numbers, pop two numbers for operators, apply operator, push result, repeat until done.

Execution Sample

DSA Typescript

function applyOp(a: number, b: number, op: string): number {
  switch (op) {
    case '+': return a + b;
    case '-': return a - b;
    case '*': return a * b;
    case '/': return a / b;
    default: throw new Error('Unsupported operator');
  }
}

const postfix = ['2', '3', '1', '*', '+', '9', '-'];
const stack: number[] = [];
for (const token of postfix) {
  if (!isNaN(+token)) stack.push(+token);
  else {
    const b = stack.pop()!;
    const a = stack.pop()!;
    stack.push(applyOp(a, b, token));
  }
}
console.log(stack.pop());

Evaluates postfix expression 2 3 1 * + 9 - step-by-step using a stack.

Execution Table

Step	Token	Operation	Stack Before	Stack After	Visual State
1	2	Push number 2	[]	[2]	2 -> null
2	3	Push number 3	[2]	[2, 3]	2 -> 3 -> null
3	1	Push number 1	[2, 3]	[2, 3, 1]	2 -> 3 -> 1 -> null
4	*	Pop 1 and 3, multiply 3*1=3, push 3	[2, 3, 1]	[2, 3]	2 -> 3 -> null
4	*	After push result 3	[2, 3]	[2, 3]	2 -> 3 -> null
5	+	Pop 3 and 2, add 2+3=5, push 5	[2, 3]	[5]	5 -> null
6	9	Push number 9	[5]	[5, 9]	5 -> 9 -> null
7	-	Pop 9 and 5, subtract 5-9=-4, push -4	[5, 9]	[-4]	-4 -> null
End	N/A	No more tokens, final result is top of stack	[-4]	[-4]	-4 -> null

💡 All tokens processed; final result is -4 on top of stack.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
stack	[]	[2]	[2, 3]	[2, 3, 1]	[2, 3]	[5]	[5, 9]	[-4]	[-4]

Key Moments - 3 Insights

Why do we pop two numbers from the stack when we see an operator?

Because postfix operators apply to the two most recent numbers; popping two numbers gets these operands as shown in steps 4, 5, and 7 in the execution_table.

Why is the order of popping important for subtraction and division?

The first popped number is the right operand and the second is the left operand; for example, in step 7, popping 9 then 5 means we compute 5 - 9, not 9 - 5.

What happens if the stack is empty when trying to pop?

It means the postfix expression is invalid; in this example, the stack always has enough numbers before operators, as seen in the variable_tracker and execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the stack after applying the '*' operator?

A [2, 3]

B [2, 3, 3]

C [2]

D [3]

💡 Hint

Check the 'Stack After' column at step 4 in execution_table.

At which step does the stack first contain only one element?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Stack After' column to find when stack length is 1.

If the token '9' was replaced by '4', what would be the final result on the stack?

A 1

B -1

C 5

D -5

💡 Hint

Refer to the calculation in step 7: result = 5 - token; replacing 9 with 4 changes 5 - 9 to 5 - 4.

Concept Snapshot

Evaluate postfix expression using a stack:
- Read tokens left to right
- Push numbers onto stack
- On operator, pop two numbers
- Apply operator (left operand is second popped)
- Push result back
- Final stack top is result

Full Transcript

To evaluate a postfix expression, we read each token from left to right. If the token is a number, we push it onto the stack. If the token is an operator, we pop the top two numbers from the stack, apply the operator with the second popped number as left operand and first popped as right operand, then push the result back onto the stack. We repeat this until all tokens are processed. The final result is the single number left on the stack. This process is shown step-by-step in the execution_table and variable_tracker, demonstrating how the stack changes after each token.

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