Evaluate Postfix Expression Using Stack in DSA Typescript - Build from Scratch

Evaluate Postfix Expression Using Stack

📖 Scenario: You are building a simple calculator that can evaluate postfix expressions. Postfix expressions are math expressions where the operator comes after the numbers, like 23+ which means 2 + 3.Using a stack helps us solve this step-by-step by pushing numbers and applying operators as we find them.

🎯 Goal: Build a program that reads a postfix expression string and calculates its result using a stack.

📋 What You'll Learn

Create a string variable called expression with the postfix expression '231*+9-'

Create a stack as an array called stack to hold numbers

Use a loop to go through each character in expression

If the character is a number, push it as a number onto stack

If the character is an operator (+, -, *, /), pop two numbers from stack, apply the operator, and push the result back

Print the final result from the stack after processing the whole expression

💡 Why This Matters

🌍 Real World

Postfix expressions are used in calculators and computer programs to simplify math expression evaluation without needing parentheses.

💼 Career

Understanding stacks and expression evaluation is important for software developers working on compilers, calculators, and interpreters.

1

Create the postfix expression string

Create a string variable called expression and set it to the postfix expression '231*+9-'.

DSA Typescript

// Create a string variable called expression with value '231*+9-'
// Your code here

Hint

Use const expression: string = '231*+9-'; to create the postfix expression.

2

Create a stack to hold numbers

Create an empty array called stack to use as a stack for numbers.

DSA Typescript

const expression: string = '231*+9-';
// Create an empty array called stack
// Your code here

Hint

Use const stack: number[] = []; to create an empty stack.

3

Loop through the expression and process characters

Use a for loop with variable char to go through each character in expression. Inside the loop, if char is a digit, push its number value onto stack. If char is an operator (+, -, *, /), pop two numbers from stack, apply the operator, and push the result back onto stack.

DSA Typescript

const expression: string = '231*+9-';
const stack: number[] = [];
// Loop through each character in expression and process it
// Your code here

Hint

Use for (const char of expression) to loop. Use !isNaN(Number(char)) to check if char is a number. Use stack.pop() to get last two numbers and apply the operator.

4

Print the final result from the stack

Print the last remaining number in stack which is the result of the postfix expression evaluation using console.log(stack[0]).

DSA Typescript

const expression: string = '231*+9-';
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()!;
        let result = 0;
        if (char === '+') {
            result = a + b;
        } else if (char === '-') {
            result = a - b;
        } else if (char === '*') {
            result = a * b;
        } else if (char === '/') {
            result = a / b;
        }
        stack.push(result);
    }
}
// Print the final result from stack
// Your code here

Hint

Use console.log(stack[0]) to print the final result.

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