Infix to Postfix Conversion Using Stack in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this infix to postfix conversion?

Given the infix expression A + B * C, what is the postfix expression produced by the standard stack-based algorithm?

DSA Javascript

function infixToPostfix(expression) {
  const precedence = {'+':1, '-':1, '*':2, '/':2};
  const stack = [];
  let result = '';
  for (let char of expression.replace(/\s+/g, '')) {
    if (/[A-Z]/.test(char)) {
      result += char;
    } else if (char === '(') {
      stack.push(char);
    } else if (char === ')') {
      while (stack.length && stack[stack.length - 1] !== '(') {
        result += stack.pop();
      }
      stack.pop();
    } else {
      while (stack.length && precedence[stack[stack.length - 1]] >= precedence[char]) {
        result += stack.pop();
      }
      stack.push(char);
    }
  }
  while (stack.length) {
    result += stack.pop();
  }
  return result;
}

console.log(infixToPostfix('A + B * C'));

A ABC*+

B AB+C*

C A*BC+

D AB*C+

💡 Hint

Remember that multiplication has higher precedence than addition.

In infix to postfix conversion, operators with higher precedence are placed after their operands first. Here, B * C is evaluated before adding A, so the postfix is ABC*+.

❓ Predict Output

intermediate

Output of infix to postfix for expression with parentheses

What is the postfix expression for (A + B) * C using the stack-based infix to postfix algorithm?

DSA Javascript

function infixToPostfix(expression) {
  const precedence = {'+':1, '-':1, '*':2, '/':2};
  const stack = [];
  let result = '';
  for (let char of expression.replace(/\s+/g, '')) {
    if (/[A-Z]/.test(char)) {
      result += char;
    } else if (char === '(') {
      stack.push(char);
    } else if (char === ')') {
      while (stack.length && stack[stack.length - 1] !== '(') {
        result += stack.pop();
      }
      stack.pop();
    } else {
      while (stack.length && precedence[stack[stack.length - 1]] >= precedence[char]) {
        result += stack.pop();
      }
      stack.push(char);
    }
  }
  while (stack.length) {
    result += stack.pop();
  }
  return result;
}

console.log(infixToPostfix('(A + B) * C'));

A ABC*+

B AB+C*

C A+BC*

D AB*+C

💡 Hint

Parentheses change the order of operations.

Parentheses force the addition to happen before multiplication. So A and B are added first, then multiplied by C, resulting in AB+C*.

🧠 Conceptual

advanced

Which operator has the highest precedence in this infix to postfix algorithm?

In the given infix to postfix conversion code, which operator will be popped from the stack first when the current operator is '*' and the top of the stack is '+'?

DSA Javascript

const precedence = {'+':1, '-':1, '*':2, '/':2};

A Neither, '*' will be pushed without popping '+'

B '+' because it has lower precedence than '*'

C '*' because it has higher precedence than '+'

D Both will be popped simultaneously

💡 Hint

Check the condition that decides when to pop from the stack.

The algorithm pops from the stack only if the top operator has precedence greater or equal to the current operator. Since '+' has lower precedence than '*', '*' is pushed without popping '+'.

🔧 Debug

advanced

What error occurs with this infix to postfix code snippet?

Consider this code snippet for infix to postfix conversion:

while (stack.length && precedence[stack[stack.length - 1]] > precedence[char]) {
  result += stack.pop();
}

What problem will this cause when converting A + B * C?

DSA Javascript

function infixToPostfix(expression) {
  const precedence = {'+':1, '-':1, '*':2, '/':2};
  const stack = [];
  let result = '';
  for (let char of expression.replace(/\s+/g, '')) {
    if (/[A-Z]/.test(char)) {
      result += char;
    } else if (char === '(') {
      stack.push(char);
    } else if (char === ')') {
      while (stack.length && stack[stack.length - 1] !== '(') {
        result += stack.pop();
      }
      stack.pop();
    } else {
      while (stack.length && precedence[stack[stack.length - 1]] > precedence[char]) {
        result += stack.pop();
      }
      stack.push(char);
    }
  }
  while (stack.length) {
    result += stack.pop();
  }
  return result;
}

console.log(infixToPostfix('A + B * C'));

A SyntaxError due to missing else clause

B No error, correct postfix is produced

C Infinite loop because stack is never popped

D The multiplication operator '*' is popped too early, resulting in incorrect postfix

💡 Hint

Check the condition for popping operators with equal precedence.

Using '>' instead of '>=' causes operators with equal precedence not to be popped, which can cause wrong order in postfix. For example, '+' is not popped before '*', leading to wrong postfix.

🚀 Application

expert

Final postfix expression after multiple operations

Given the infix expression A + (B - C) * (D + E) / F, what is the correct postfix expression produced by the stack-based infix to postfix algorithm?

DSA Javascript

function infixToPostfix(expression) {
  const precedence = {'+':1, '-':1, '*':2, '/':2};
  const stack = [];
  let result = '';
  for (let char of expression.replace(/\s+/g, '')) {
    if (/[A-Z]/.test(char)) {
      result += char;
    } else if (char === '(') {
      stack.push(char);
    } else if (char === ')') {
      while (stack.length && stack[stack.length - 1] !== '(') {
        result += stack.pop();
      }
      stack.pop();
    } else {
      while (stack.length && stack[stack.length - 1] !== '(' && precedence[stack[stack.length - 1]] >= precedence[char]) {
        result += stack.pop();
      }
      stack.push(char);
    }
  }
  while (stack.length) {
    result += stack.pop();
  }
  return result;
}

console.log(infixToPostfix('A + (B - C) * (D + E) / F'));

A + / F * +ED -CBA

B BC- DE+ * F / +

C ABC- DE+ * F / +

D ABC- DE+ * F /

💡 Hint

Break down the expression by parentheses and operator precedence step by step.

The postfix expression is 'ABC- DE+ * F / +'. The subexpressions inside parentheses are converted first, then multiplication and division, then addition.

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