Infix to Postfix Conversion Using Stack in DSA Typescript - Build from Scratch

Infix to Postfix Conversion Using Stack

📖 Scenario: You are building a simple calculator that converts normal math expressions (infix) into a form easier for computers to calculate (postfix). This helps computers solve math problems step-by-step without confusion.

🎯 Goal: Build a program that takes a math expression written in normal form (like (A+B)*C) and changes it into postfix form (like AB+C*) using a stack.

📋 What You'll Learn

Create a string variable called infix with the exact value '(A+B)*C'

Create a stack using an array called stack to help with the conversion

Write a function called precedence that returns the priority of operators: '+' and '-' have priority 1, '*' and '/' have priority 2

Write the main logic to convert infix to postfix using the stack and the precedence function

Print the final postfix expression

💡 Why This Matters

🌍 Real World

Converting infix to postfix is used in calculators and compilers to simplify math expression evaluation.

💼 Career

Understanding stacks and expression parsing is important for software developers working on interpreters, compilers, and calculators.

1

Create the infix expression string

Create a string variable called infix and set it to the exact value '(A+B)*C'

DSA Typescript

# Create a string variable called infix with value '(A+B)*C'
// Your code here

Hint

Use const infix: string = '(A+B)*C'; to create the expression.

2

Create the stack array and precedence function

Create an empty array called stack to use as a stack. Then write a function called precedence that takes a string op and returns 2 if op is '*' or '/', returns 1 if op is '+' or '-', and returns 0 otherwise.

DSA Typescript

const infix: string = '(A+B)*C';
// Create an empty array called stack
// Write the precedence function
// Your code here

Hint

Use const stack: string[] = []; and a function with if statements to return priorities.

3

Write the core logic to convert infix to postfix

Create a string variable called postfix and set it to an empty string. Then use a for loop with variable char to go through each character in infix. Inside the loop, do the following:
- If char is a letter (A-Z), add it to postfix.
- If char is '(', push it to stack.
- If char is ')', pop from stack and add to postfix until '(' is found, then remove '('.
- If char is an operator (+, -, *, /), pop from stack and add to postfix while the top of stack has an operator with precedence greater or equal to char. Then push char to stack.
After the loop, pop all remaining operators from stack and add to postfix.

DSA Typescript

const infix: string = '(A+B)*C';
const stack: string[] = [];

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

// Create postfix string and write the conversion logic using a for loop
// Your code here

Hint

Use a loop to check each character and stack operations to build postfix.

4

Print the postfix expression

Write a console.log statement to print the postfix string.

DSA Typescript

const infix: string = '(A+B)*C';
const stack: string[] = [];

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

let postfix: string = '';

for (const char of infix) {
    if (char >= 'A' && char  0 && stack[stack.length - 1] !== '(') {
            postfix += stack.pop();
        }
        stack.pop(); // remove '('
    } else { // operator
        while (stack.length > 0 && precedence(stack[stack.length - 1]) >= precedence(char)) {
            postfix += stack.pop();
        }
        stack.push(char);
    }
}

while (stack.length > 0) {
    postfix += stack.pop();
}

// Print the postfix expression
// Your code here

Hint

Use console.log(postfix); to show the result.

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