Infix to Postfix Conversion Using Stack in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of converting an infix expression to postfix?

To make it easier for computers to evaluate expressions without needing to consider operator precedence or parentheses.

beginner

Which data structure is primarily used in infix to postfix conversion?

A stack is used to temporarily hold operators and manage their precedence during conversion.

beginner

What does operator precedence mean in the context of infix expressions?

It means some operators are evaluated before others, for example, multiplication (*) before addition (+).

intermediate

In the algorithm, what happens when an operator with lower precedence is encountered compared to the operator on the stack top?

Operators from the stack are popped and added to the postfix expression until the stack is empty or an operator with lower precedence is found.

intermediate

How are parentheses handled during infix to postfix conversion?

Left parentheses '(' are pushed onto the stack, and when a right parenthesis ')' is found, operators are popped from the stack to the postfix expression until the matching '(' is removed.

Which of the following is the correct postfix form of the infix expression: A + B * C?

A A B C * +

B A + B * C

C A B + C *

D A * B + C

Multiplication has higher precedence, so B * C is done first, then added to A, resulting in 'A B C * +'.

What data structure do we use to store operators during infix to postfix conversion?

A Queue

B Linked List

C Array

D Stack

A stack is used to hold operators temporarily and manage their precedence.

When do we pop operators from the stack during conversion?

A When the incoming operator has higher precedence

B When the incoming operator has lower or equal precedence

C Only at the end of the expression

D Never

Operators are popped when the incoming operator has lower or equal precedence to maintain correct order.

How are parentheses treated in the infix to postfix conversion?

A They are ignored

B They are added to the postfix expression

C Left parentheses are pushed to stack; right parentheses cause popping until left parenthesis is found

D They are converted to operators

Parentheses control grouping: '(' is pushed, ')' triggers popping until '(' is removed.

What is the postfix expression for (A + B) * C?

A A B + C *

B A B C + *

C A + B C *

D A B * C +

Parentheses force addition first, so 'A B +' then multiplied by C, resulting in 'A B + C *'.

Explain step-by-step how to convert the infix expression 'A + B * C' to postfix using a stack.

Think about operator precedence and when to push or pop operators.

Describe how parentheses affect the infix to postfix conversion process.

Parentheses control the order of operations explicitly.

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