Evaluate Postfix Expression Using Stack in DSA Javascript - Execution Trace

Concept Flow - Evaluate Postfix Expression Using Stack

Start

↓

Read next token

↓

Is token operand?

Yes→Push operand on stack

↓

Stack updated

↓

Is token operator?

↓

Is more tokens?

No→Result = stack top

↓

Pop two operands

↓

Apply operator

↓

Push result on stack

↓

Is more tokens?

Yes→Read next token

We read tokens one by one. If operand, push on stack. If operator, pop two operands, apply operator, push result. Repeat until tokens end. Result is top of stack.

Execution Sample

DSA Javascript

function evaluatePostfix(expr) {
  const stack = [];
  for (const token of expr) {
    if (!isNaN(token)) stack.push(Number(token));
    else {
      const b = stack.pop();
      const a = stack.pop();
      stack.push(eval(`${a}${token}${b}`));
    }
  }
  return stack.pop();
}

Evaluates postfix expression by pushing operands and applying operators using a stack.

Execution Table

Step	Operation	Token	Stack Before	Action	Stack After	Visual State
1	Read token	2	[]	Push operand 2	[2]	2 -> null
2	Read token	3	[2]	Push operand 3	[2, 3]	2 -> 3 -> null
3	Read token	+	[2, 3]	Pop 3 and 2, compute 2+3=5, push 5	[5]	5 -> null
4	Read token	4	[5]	Push operand 4	[5, 4]	5 -> 4 -> null
5	Read token	*	[5, 4]	Pop 4 and 5, compute 5*4=20, push 20	[20]	20 -> null
6	Read token	5	[20]	Push operand 5	[20, 5]	20 -> 5 -> null
7	Read token	6	[20, 5]	Push operand 6	[20, 5, 6]	20 -> 5 -> 6 -> null
8	Read token	+	[20, 5, 6]	Pop 6 and 5, compute 5+6=11, push 11	[20, 11]	20 -> 11 -> null
9	Read token	-	[20, 11]	Pop 11 and 20, compute 20-11=9, push 9	[9]	9 -> null
10	End		[9]	No more tokens, pop result	[]	null

💡 All tokens processed; final result is 9 at top of stack.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	Final
stack	[]	[2]	[2,3]	[5]	[5,4]	[20]	[20,5]	[20,5,6]	[20,11]	[9]	[]
token		2	3	+	4	*	5	6	+	-

Key Moments - 3 Insights

Why do we pop two operands when we see an operator?

Because postfix operators apply to the two most recent operands on the stack, as shown in steps 3, 5, 8, and 9 in the execution_table.

Why is the first popped operand the second operand in the operation?

Because the stack is LIFO, the last pushed operand is popped first, so in step 3 for '+', we pop 3 then 2, applying 2 + 3.

What happens if the expression has only operands and no operators?

Operands are pushed on stack but no operations happen; final result is the last operand pushed, as the stack never reduces, shown by absence of operator steps.

Visual Quiz - 3 Questions

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

A [20]

B [5, 4]

C [5]

D [20, 4]

💡 Hint

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

At which step does the condition 'No more tokens' become true?

A Step 8

B Step 9

C Step 10

D Step 7

💡 Hint

Look for the 'End' operation and 'No more tokens' action in the execution_table.

If the token '+' at step 3 was replaced by '-', what would be the stack after step 3?

A [5]

B [-1]

C [2]

D [3]

💡 Hint

Consider the operation 2 - 3 and check the 'Stack After' value after applying the operator.

Concept Snapshot

Evaluate Postfix Expression Using Stack:
- Read tokens left to right
- Push operands on stack
- On operator, pop two operands
- Apply operator: left operand is second popped
- Push result back on stack
- 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 a stack. If the token is an operator, we pop the two most recent numbers from the stack, apply the operator to them (the first popped is the right operand, the second popped is the left 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, where the stack changes as operands are pushed and operators applied. Key points include understanding why two operands are popped for each operator and the order of operands in the operation.

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