Infix to Postfix Conversion Using Stack in DSA Javascript

Mental Model

We use a stack to reorder operators so that expressions can be evaluated without parentheses, following operator precedence.

Analogy: Imagine sorting tasks by priority: you put higher priority tasks on top of a stack and complete them first, ensuring the right order.

Infix expression: A + B * C
Stack: empty
Postfix output: empty

Dry Run Walkthrough

Input: infix: A + B * C

Goal: Convert the infix expression to postfix notation respecting operator precedence

Step 1: Read 'A', an operand, add to output

Output: A
Stack: empty

Why: Operands go directly to output

Step 2: Read '+', push to stack

Output: A
Stack: +

Why: Operators go to stack to wait for precedence check

Step 3: Read 'B', an operand, add to output

Output: A B
Stack: +

Why: Operands go directly to output

Step 4: Read '*', higher precedence than '+', push to stack

Output: A B
Stack: + -> *

Why: Higher precedence operators go on top of lower ones

Step 5: Read 'C', an operand, add to output

Output: A B C
Stack: + -> *

Why: Operands go directly to output

Step 6: No more input, pop '*' from stack to output

Output: A B C *
Stack: +

Why: Pop remaining operators in correct order

Step 7: Pop '+' from stack to output

Output: A B C * +
Stack: empty

Why: Finish by emptying stack

Result:

Output: A B C * +
Stack: empty

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 precedence(op) {
  if (op === '+' || op === '-') return 1
  if (op === '*' || op === '/') return 2
  return 0
}

function isOperator(c) {
  return ['+', '-', '*', '/'].includes(c)
}

function infixToPostfix(expression) {
  const stack = new Stack()
  let output = ''

  for (const char of expression.replace(/\s+/g, '')) {
    if (/[A-Za-z0-9]/.test(char)) {
      output += char + ' '
    } else if (isOperator(char)) {
      while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(char)) {
        output += stack.pop() + ' '
      }
      stack.push(char)
    }
  }

  while (!stack.isEmpty()) {
    output += stack.pop() + ' '
  }

  return output.trim()
}

// Driver code
const infixExpr = 'A + B * C'
const postfixExpr = infixToPostfix(infixExpr)
console.log(postfixExpr)

if (/[A-Za-z0-9]/.test(char)) { output += char + ' ' }

Add operands directly to output

while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(char)) { output += stack.pop() + ' ' }

Pop operators with higher or equal precedence before pushing new operator

stack.push(char)

Push current operator to stack

while (!stack.isEmpty()) { output += stack.pop() + ' ' }

Pop all remaining operators to output after input processed

Output

A B C * +

Complexity Analysis

Time: O(n) because we scan the expression once and each operator is pushed and popped at most once

Space: O(n) for the stack and output storage proportional to input size

vs Alternative: Compared to recursive parsing, stack-based conversion is simpler and more efficient for linear scans

Edge Cases

Empty expression

Returns empty output without error

DSA Javascript

for (const char of expression.replace(/\s+/g, '')) {

Expression with only operands

Outputs operands separated by spaces directly

DSA Javascript

if (/[A-Za-z0-9]/.test(char)) { output += char + ' ' }

Expression with multiple operators of same precedence

Operators are popped in correct order respecting left-to-right associativity

DSA Javascript

while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(char)) { output += stack.pop() + ' ' }

When to Use This Pattern

When you need to convert expressions from human-readable form to a form easy for computers to evaluate, use the stack-based infix to postfix conversion pattern.

Common Mistakes

Mistake: Not popping operators with equal precedence before pushing new operator
Fix: Use >= in precedence comparison to pop operators of equal or higher precedence

Mistake: Adding operators directly to output instead of using stack
Fix: Always push operators to stack and pop based on precedence

Summary

Converts infix expressions to postfix using a stack to reorder operators by precedence.

Use when you want to evaluate or process expressions without parentheses and operator precedence confusion.

The key insight is that a stack helps reorder operators so operands appear in correct evaluation order.

Practice

1. What is the main purpose of using a stack in Infix to Postfix Conversion?

easy

A. To temporarily hold operators and manage their precedence

B. To store the final postfix expression

C. To reverse the infix expression

D. To count the number of operands

Solution

1. Step 1: Understand the role of stack in conversion

   The stack is used to hold operators temporarily while scanning the infix expression to respect operator precedence and associativity.

2. Step 2: Differentiate stack usage from other tasks

   The postfix expression is built separately, and the stack is not used to store operands or reverse the expression.

3. Final Answer:

   To temporarily hold operators and manage their precedence -> Option A

4. Quick Check:

   Stack holds operators [OK]

Hint: Stack holds operators to manage precedence during conversion [OK]

Common Mistakes:

• Thinking stack stores operands
• Confusing stack role with reversing expression
• Assuming stack counts operands

2. Which of the following is the correct way to check if the stack is empty in JavaScript during infix to postfix conversion?

easy

A. if (stack === undefined)

B. if (stack == null)

C. if (stack.length === 0)

D. if (stack.isEmpty())

Solution

1. Step 1: Recall JavaScript array properties

   Stacks are usually implemented using arrays; checking if stack.length === 0 confirms if it is empty.

2. Step 2: Evaluate other options

   stack == null or stack === undefined check if the variable exists, not if it's empty. stack.isEmpty() is not a built-in method in JavaScript arrays.

3. Final Answer:

   if (stack.length === 0) -> Option C

4. Quick Check:

   Array length zero means empty stack [OK]

Hint: Use stack.length === 0 to check empty stack in JavaScript [OK]

Common Mistakes:

• Using undefined or null checks instead of length
• Calling non-existent isEmpty() method
• Confusing variable existence with emptiness

3. What is the postfix expression output for the infix expression A + B * C using stack-based conversion?

medium

A. ABC*+

B. AB+C*

C. A+BC*

D. *ABC+

Solution

1. Step 1: Apply operator precedence rules

   Multiplication (*) has higher precedence than addition (+), so B * C is evaluated first.

2. Step 2: Convert to postfix step-by-step

   Postfix for B * C is BC*. Then add A and + operator: ABC*+.

3. Final Answer:

   ABC*+ -> Option A

4. Quick Check:

   Multiplication before addition = ABC*+ [OK]

Hint: Multiply before add; postfix puts operator after operands [OK]

Common Mistakes:

• Ignoring operator precedence
• Placing operators before operands
• Mixing operand order

4. Identify the error in this JavaScript snippet for infix to postfix conversion:

if (stack.length = 0) { output += token; }

medium

A. Output variable is not declared

B. Missing semicolon after if condition

C. Stack length property is incorrect

D. Assignment operator used instead of comparison

Solution

1. Step 1: Check the if condition syntax

   The condition uses single equals = which assigns 0 to stack.length instead of comparing it.

2. Step 2: Understand correct comparison operator

   Use === or == to compare values, not =.

3. Final Answer:

   Assignment operator used instead of comparison -> Option D

4. Quick Check:

   Use === for comparison, not = [OK]

Hint: Use === for comparison, not = assignment [OK]

Common Mistakes:

• Using = instead of === in conditions
• Ignoring syntax errors in if statements
• Assuming missing semicolon causes error here

5. Given the infix expression (A + B) * (C - D) / E, what is the correct postfix expression after conversion using stack?

hard

A. AB+CD-E*/

B. AB+CD-*E/

C. AB+CD-E/*

D. AB+CD*E/-

Solution

1. Step 1: Convert each parenthesis group separately

   (A + B) becomes AB+, and (C - D) becomes CD-.

2. Step 2: Apply multiplication and division in order

   Multiply results: AB+ CD- *, then divide by E: AB+CD-*E/.

3. Final Answer:

   AB+CD-*E/ -> Option B

4. Quick Check:

   Parentheses handled first, then * and / left to right [OK]

Hint: Handle parentheses first, then * and / left to right [OK]

Common Mistakes:

• Ignoring parentheses order
• Mixing operator precedence
• Placing division before multiplication incorrectly