Infix to Postfix Conversion Using Stack in DSA Typescript

Mental Model

We change a math expression from normal form (infix) to a form easy for computers to calculate (postfix) by using a stack to hold operators until they can be placed in the right order.

Analogy: Imagine a chef preparing ingredients in order: they keep spices (operators) on a shelf (stack) until it's time to add them to the dish (output), ensuring the flavors (order) come out just right.

Input: A + B * C
Stack: []
Output: []

Dry Run Walkthrough

Input: infix expression: A + B * C

Goal: Convert the infix expression to postfix notation: A B C * +

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

Stack: []
Output: [A]

Why: Operands go directly to output because they appear in the same order in postfix

Step 2: Read '+', push it onto the stack

Stack: [+]
Output: [A]

Why: Operators wait on stack until we know if higher precedence operators come next

Step 3: Read 'B', add it to output

Stack: [+]
Output: [A B]

Why: Operands always go to output immediately

Step 4: Read '*', push it onto stack because '*' has higher precedence than '+'

Stack: [+ *]
Output: [A B]

Why: Higher precedence operators go on top of lower ones

Step 5: Read 'C', add it to output

Stack: [+ *]
Output: [A B C]

Why: Operands go directly to output

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

Stack: [+]
Output: [A B C *]

Why: Pop operators after processing all operands

Step 7: Pop '+' from stack to output

Stack: []
Output: [A B C * +]

Why: Finish by emptying stack to output

Result:

Final Output: A B C * +
Stack: []

Annotated Code

DSA Typescript

class Stack<T> {
  private items: T[] = [];
  push(element: T) {
    this.items.push(element);
  }
  pop(): T | undefined {
    return this.items.pop();
  }
  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }
  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

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

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

function infixToPostfix(expression: string): string {
  const stack = new Stack<string>();
  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 with space

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

Pop operators from stack with higher or equal precedence before pushing new operator

stack.push(char);

Push current operator onto stack

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

Pop all remaining operators to output after processing input

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) because the stack and output can hold up to all characters in the expression

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

Edge Cases

Empty expression

Returns empty output without error

DSA Typescript

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

Expression with only operands (e.g., 'A B C')

Outputs operands separated by spaces directly

DSA Typescript

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

Expression with operators of same precedence (e.g., 'A - B + C')

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

DSA Typescript

while (!stack.isEmpty() && precedence(stack.peek()!) >= precedence(char)) {

When to Use This Pattern

When you need to convert human-readable math expressions to a form easy for computers to evaluate, use the stack-based infix to postfix conversion pattern because it handles operator precedence and order cleanly.

Common Mistakes

Mistake: Not popping operators with higher or equal precedence before pushing a new operator
Fix: Use a while loop to pop all operators from stack with precedence >= current operator before pushing

Mistake: Adding operators directly to output instead of using stack
Fix: Always push operators onto stack and pop them in correct order to output

Summary

Converts infix expressions to postfix using a stack to manage operator precedence.

Use when you want to prepare expressions for easy evaluation by computers.

The key is to push operators on a stack and pop them only when lower precedence operators appear or at the end.

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