Evaluate Postfix Expression Using Stack in DSA Javascript

Mental Model

We use a stack to keep numbers until we find an operator, then combine the last two numbers using that operator.

Analogy: Imagine a chef stacking ingredients on a plate. When the chef gets a cooking instruction (operator), they take the last two ingredients, cook them together, and put the result back on the plate.

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

Initial stack empty, reading tokens left to right.

Dry Run Walkthrough

Input: Postfix expression: 2 3 + 4 *

Goal: Calculate the final result of the postfix expression using a stack.

Step 1: Read '2', push it onto the stack

Stack: [2]

Why: Numbers are pushed to stack to wait for operators

Step 2: Read '3', push it onto the stack

Stack: [2, 3]

Why: Keep numbers until operator appears

Step 3: Read '+', pop 3 and 2, add them (2+3=5), push result back

Stack: [5]

Why: Operator means combine last two numbers and push result

Step 4: Read '4', push it onto the stack

Stack: [5, 4]

Why: Push number to stack

Step 5: Read '*', pop 4 and 5, multiply them (5*4=20), push result back

Stack: [20]

Why: Operator combines last two numbers

Result:

Stack: [20]
Final result: 20

Annotated Code

DSA Javascript

class Stack {
  constructor() {
    this.items = [];
  }
  push(element) {
    this.items.push(element);
  }
  pop() {
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
}

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

  for (const token of tokens) {
    if (!isNaN(token)) {
      stack.push(Number(token)); // push number to stack
    } else {
      const b = stack.pop(); // pop second operand
      const a = stack.pop(); // pop first operand
      let result;
      if (token === '+') {
        result = a + b; // add
      } else if (token === '-') {
        result = a - b; // subtract
      } else if (token === '*') {
        result = a * b; // multiply
      } else if (token === '/') {
        result = a / b; // divide
      }
      stack.push(result); // push result back
    }
  }
  return stack.pop(); // final result
}

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

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

push numbers onto stack to wait for operators

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

pop last number for operation

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

pop second last number for operation

result = a + b; // add

perform addition for '+' operator

result = a - b; // subtract

perform subtraction for '-' operator

result = a * b; // multiply

perform multiplication for '*' operator

result = a / b; // divide

perform division for '/' operator

stack.push(result); // push result back

push operation result back to stack

return stack.pop(); // final result

pop final result after processing all tokens

Output

20

Complexity Analysis

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

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

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

Edge Cases

Empty expression

Returns undefined or error because no tokens to process

DSA Javascript

return stack.pop(); // final result

Single number only

Returns that number as result

DSA Javascript

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

Division by zero

Returns Infinity or error depending on JavaScript behavior

DSA Javascript

result = a / b; // divide

When to Use This Pattern

When you see an expression without parentheses and operators after operands, use the stack evaluation pattern for postfix expressions because it simplifies calculation by avoiding precedence rules.

Common Mistakes

Mistake: Popping operands in wrong order (e.g., reversing a and b)
Fix: Always pop second operand first, then first operand to maintain correct order

Mistake: Trying to evaluate operators as numbers
Fix: Check if token is a number before pushing; otherwise treat as operator

Summary

It calculates the value of a postfix expression using a stack.

Use it when you have postfix expressions to evaluate without worrying about operator precedence.

The key is to push numbers and apply operators to the last two numbers on the stack.

Practice

1. What is the main data structure used to evaluate a postfix expression?

easy

A. Linked List

B. Queue

C. Stack

D. Array

Solution

1. Step 1: Understand postfix evaluation process

   Postfix expressions are evaluated using a stack to hold operands until an operator is encountered.

2. Step 2: Identify the correct data structure

   The stack allows pushing operands and popping them for operations, which fits postfix evaluation perfectly.

3. Final Answer:

   Stack -> Option C

4. Quick Check:

   Postfix evaluation uses stack = Stack [OK]

Hint: Postfix uses stack to hold operands until operators appear [OK]

Common Mistakes:

• Choosing queue instead of stack
• Using array without stack operations
• Confusing with infix evaluation

2. Which of the following is the correct way to push an element onto a stack in JavaScript?

easy

A. stack.push(element);

B. stack.add(element);

C. stack.insert(element);

D. stack.enqueue(element);

Solution

1. Step 1: Recall JavaScript stack operations

   JavaScript arrays use push() to add elements to the end, simulating stack push.

2. Step 2: Match correct method

   push() is the standard method; add(), insert(), enqueue() are incorrect for stack push.

3. Final Answer:

   stack.push(element); -> Option A

4. Quick Check:

   Push uses push() method = stack.push(element); [OK]

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

Common Mistakes:

• Using add() or insert() which don't exist
• Confusing enqueue() with queue operation
• Using pop() instead of push()

3. What is the output of the following JavaScript code that evaluates the postfix expression "23+5*"?

function evaluatePostfix(expr) {
  const stack = [];
  for (const ch of expr) {
    if (!isNaN(ch)) {
      stack.push(Number(ch));
    } else {
      const b = stack.pop();
      const a = stack.pop();
      if (ch === '+') stack.push(a + b);
      else if (ch === '*') stack.push(a * b);
    }
  }
  return stack.pop();
}
console.log(evaluatePostfix("23+5*"));

medium

A. 25

B. 15

C. 10

D. Error

Solution

1. Step 1: Evaluate postfix expression "23+5*" step-by-step

   Push 2, push 3, then '+' operator: pop 3 and 2, add = 5, push 5. Push 5, then '*' operator: pop 5 and 5, multiply = 25, push 25.

2. Step 2: Final stack value

   Only one value 25 remains, which is returned and printed.

3. Final Answer:

   25 -> Option A

4. Quick Check:

   2+3=5, 5*5=25 = 25 [OK]

Hint: Calculate stepwise: operands pushed, operators pop two and push result [OK]

Common Mistakes:

• Mixing operand order in subtraction/division
• Forgetting to convert char to number
• Confusing operator precedence

4. Identify the error in the following postfix evaluation code snippet:

function evalPostfix(expr) {
  const stack = [];
  for (const ch of expr) {
    if (ch >= '0' && ch <= '9') {
      stack.push(ch);
    } else {
      const b = stack.pop();
      const a = stack.pop();
      if (ch === '+') stack.push(a + b);
      else if (ch === '-') stack.push(a - b);
    }
  }
  return stack.pop();
}

medium

A. Stack pop order is reversed

B. Operands are pushed as strings, not numbers

C. Missing handling for multiplication operator

D. Loop does not iterate over expression

Solution

1. Step 1: Check how operands are pushed

   The code pushes characters directly without converting to numbers, so operands are strings.

2. Step 2: Effect of pushing strings on arithmetic

   Adding strings with '+' concatenates instead of numeric addition, causing wrong results.

3. Final Answer:

   Operands are pushed as strings, not numbers -> Option B

4. Quick Check:

   Push operands as numbers, not strings = Operands are pushed as strings, not numbers [OK]

Hint: Convert chars to numbers before pushing to stack [OK]

Common Mistakes:

• Pushing chars without Number()
• Ignoring operator cases
• Assuming pop order is wrong

5. Given the postfix expression "82/3-4*", what is the correct evaluation result using a stack-based approach?

hard

A. 6

B. 0

C. 8

D. 4

Solution

1. Step 1: Evaluate "82/3-4*" step-by-step

   Push 8, push 2, '/' operator: 8 / 2 = 4, push 4. Push 3, '-' operator: 4 - 3 = 1, push 1. Push 4, '*' operator: 1 * 4 = 4, push 4.

2. Step 2: Final stack value

   Only one value 4 remains, but check carefully: The last '*' uses 1 and 4, result 4.

3. Step 3: Re-check calculation

   Actually, after '-' operation, stack has 1. Then push 4, then '*': 1 * 4 = 4.

4. Final Answer:

   4 -> Option D

5. Quick Check:

   8/2=4, 4-3=1, 1*4=4 = 4 [OK]

Hint: Evaluate stepwise: divide, subtract, then multiply [OK]

Common Mistakes:

• Mixing operand order in division
• Skipping operator precedence
• Incorrect stack pop sequence