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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Postfix Conversion for Simple Expression

What is the output of the following TypeScript code that converts an infix expression to postfix notation?

DSA Typescript

function precedence(op: string): number {
  if (op === '+' || op === '-') return 1;
  if (op === '*' || op === '/') return 2;
  return 0;
}

function infixToPostfix(expression: string): string {
  const stack: string[] = [];
  let result = '';
  for (const char of expression) {
    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 a+bc*

C ab+c*

D abc+*

💡 Hint

Remember that multiplication has higher precedence than addition.

The expression 'a+b*c' converts to postfix as 'abc*+'. The multiplication 'b*c' is done first, then added to 'a'.

❓ Predict Output

intermediate

Postfix Conversion Output with Parentheses

What is the output of this TypeScript function when converting the infix expression '(a+b)*c' to postfix?

DSA Typescript

function precedence(op: string): number {
  if (op === '+' || op === '-') return 1;
  if (op === '*' || op === '/') return 2;
  return 0;
}

function infixToPostfix(expression: string): string {
  const stack: string[] = [];
  let result = '';
  for (const char of expression) {
    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 ab*+c

B abc*+

C a+b*c

D ab+c*

💡 Hint

Parentheses change the order of operations.

The expression '(a+b)*c' converts to postfix as 'ab+c*'. The addition inside parentheses is done first, then multiplied by 'c'.

🧠 Conceptual

advanced

Understanding Stack Usage in Infix to Postfix Conversion

Why do we use a stack data structure when converting an infix expression to postfix notation?

A To temporarily hold operators and manage their precedence and associativity

B To reverse the order of the expression characters

C To store operands until the expression is fully parsed

D To count the number of operators in the expression

💡 Hint

Think about how operators are handled in the conversion process.

The stack holds operators temporarily so we can output them in the correct order based on precedence and associativity rules.

🔧 Debug

advanced

Identify the Error in Postfix Conversion Code

What error will the following TypeScript code produce when converting 'a+b*c' to postfix?

DSA Typescript

function precedence(op: string): number {
  if (op === '+' || op === '-') return 1;
  if (op === '*' || op === '/') return 2;
  return 0;
}

function infixToPostfix(expression: string): string {
  const stack: string[] = [];
  let result = '';
  for (const char of expression) {
    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 Throws runtime error due to empty stack pop

B Outputs 'ab+c*' which is incorrect

C Outputs 'abc*' missing the addition operator

D Outputs 'abc*+' correctly

💡 Hint

Check the condition in the while loop that pops from the stack for operator precedence.

The condition uses '>' instead of '>=' causing operators with equal precedence to not pop correctly, missing the addition operator in output.

🚀 Application

expert

Postfix Expression Length After Conversion

Given the infix expression 'a+(b*c-(d/e^f)*g)*h', how many characters will the postfix expression have after conversion using a correct infix to postfix algorithm?

A 19

B 15

C 17

D 13

💡 Hint

Count operands and operators carefully; each operand and operator appears once in postfix.

The infix expression has 8 operands (a,b,c,d,e,f,g,h) and 7 operators (+,*,-,/,^,*,+). Total length = 15.

Practice

1. What is the main purpose of using a stack in converting an infix expression to postfix?

easy

A. To reverse the order of operands

B. To store operands permanently

C. To temporarily hold operators and manage their precedence

D. To count the number of operators in the expression

Solution

1. Step 1: Understand the role of stack in infix to postfix

   The stack is used to hold operators temporarily while processing the expression to ensure correct precedence and associativity.

2. Step 2: Identify what is stored in the stack

   Operands are directly added to the output, while operators are pushed to the stack to manage order based on precedence.

3. Final Answer:

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

4. Quick Check:

   Stack holds operators for precedence [OK]

Hint: Stack holds operators, not operands, for precedence [OK]

Common Mistakes:

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

2. Which of the following is the correct way to check if the stack is empty in TypeScript when implementing infix to postfix conversion?

easy

A. if (stack.length === 0) {}

B. if (stack.isEmpty()) {}

C. if (stack == null) {}

D. if (stack.size() === 0) {}

Solution

1. Step 1: Understand stack implementation in TypeScript

   Stacks are often implemented as arrays in TypeScript, so checking if empty means checking if length is zero.

2. Step 2: Identify correct syntax for empty check

   Using stack.length === 0 is the standard way to check if an array-based stack is empty.

3. Final Answer:

   if (stack.length === 0) {} -> Option A

4. Quick Check:

   Array length zero means empty stack [OK]

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

Common Mistakes:

• Using non-existent isEmpty() method
• Checking stack == null instead of length
• Using size() which is not standard for arrays

3. What is the postfix expression for the infix expression A + B * C?

medium

A. A+BC*

B. ABC*+

C. AB+C*

D. *ABC+

Solution

1. Step 1: Identify operator precedence in infix

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

2. Step 2: Convert to postfix respecting precedence

   Postfix places operands first, then operator: B C * then A +, resulting in ABC*+.

3. Final Answer:

   ABC*+ -> Option B

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
• Confusing order of operands

4. Given the following TypeScript snippet for infix to postfix conversion, what is the error?

function isOperator(c: string): boolean {
  return c === '+' || c === '-' || c === '*' || c === '/';
}

function precedence(c: string): number {
  if (c === '+' || c === '-') return 1;
  if (c === '*' || c === '/') return 2;
  return 0;
}

function infixToPostfix(expression: string): string {
  const stack: string[] = [];
  let result = '';
  for (const char of expression) {
    if (char.match(/[a-zA-Z0-9]/)) {
      result += char;
    } else if (isOperator(char)) {
      while (stack.length && precedence(stack[stack.length - 1]) >= precedence(char)) {
        result += stack.pop();
      }
      stack.push(char);
    }
  }
  while (stack.length) {
    result += stack.pop();
  }
  return result;
}

medium

A. The code does not handle parentheses in the expression

B. The precedence function returns wrong values

C. The stack is not used to store operators

D. Operands are not added to the result

Solution

1. Step 1: Analyze code handling of parentheses

   The code does not check for '(' or ')' characters, so it cannot handle expressions with parentheses correctly.

2. Step 2: Confirm other parts are correct

   Precedence and operator checks are correct; operands are added properly; stack stores operators as expected.

3. Final Answer:

   The code does not handle parentheses in the expression -> Option A

4. Quick Check:

   Missing parentheses handling causes error [OK]

Hint: Check if parentheses are handled explicitly [OK]

Common Mistakes:

• Assuming parentheses handled automatically
• Confusing precedence values
• Ignoring stack usage for operators

5. Convert the infix expression (A + B) * (C - D) / E to postfix notation using stack-based conversion.

hard

A. AB+CD-E*/

B. A+B*CD-E/

C. AB+CD-*E

D. AB+CD-*E/

Solution

1. Step 1: Handle parentheses and operator precedence

   Parentheses force evaluation order: (A + B) and (C - D) first, then multiply, then divide by E.

2. Step 2: Convert each part to postfix and combine

   (A + B) -> AB+; (C - D) -> CD-; multiply results: AB+CD-*; then divide by E: AB+CD-*E/.

3. Final Answer:

   AB+CD-*E/ -> Option D

4. Quick Check:

   Parentheses respected, operators after operands [OK]

Hint: Convert inside parentheses first, then apply operators [OK]

Common Mistakes:

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