Infix to Postfix Conversion Using Stack in DSA Typescript - Execution Trace

Concept Flow - Infix to Postfix Conversion Using Stack

Read next token from infix

↓

Is token operand?

Yes→Add operand to postfix

No↓

Is token '('?

Yes→Push '(' to stack

No↓

Is token ')' ?

Yes→Pop stack to postfix until '('

No↓

Is token operator?

Yes→Pop stack operators with higher/equal precedence to postfix

↓

Push current operator to stack

↓

Repeat until infix tokens end

↓

Pop remaining stack to postfix

↓

Done

The flow reads each token from the infix expression, decides if it is operand, operator, or parenthesis, and uses a stack to reorder operators by precedence to build the postfix expression.

Execution Sample

DSA Typescript

infix = 'A+B*C'
stack = []
postfix = ''
for token in infix:
  if operand: postfix += token
  else if operator: pop higher prec from stack
  push token
pop all stack to postfix

Converts infix 'A+B*C' to postfix by scanning tokens, using stack for operators, and appending operands directly.

Execution Table

Step	Operation	Token	Stack State	Postfix Expression	Pointer Changes	Visual State
1	Read token	A	[]		token=A	Postfix: '' | Stack: []
2	Token is operand	A	[]	A	postfix += 'A'	Postfix: 'A' | Stack: []
3	Read token	+	[]	A	token=+	Postfix: 'A' | Stack: []
4	Token is operator	+	[]	A	push '+'	Postfix: 'A' | Stack: ['+']
5	Read token	B	['+']	A	token=B	Postfix: 'A' | Stack: ['+']
6	Token is operand	B	['+']	AB	postfix += 'B'	Postfix: 'AB' | Stack: ['+']
7	Read token	*	['+']	AB	token='*'	Postfix: 'AB' | Stack: ['+']
8	Token is operator	*	['+']	AB	compare precedence '*' > '+'	Postfix: 'AB' | Stack: ['+']
9	Push '*' to stack	*	['+', '*']	AB	push '*'	Postfix: 'AB' | Stack: ['+', '*']
10	Read token	C	['+', '*']	AB	token='C'	Postfix: 'AB' | Stack: ['+', '*']
11	Token is operand	C	['+', '*']	ABC	postfix += 'C'	Postfix: 'ABC' | Stack: ['+', '*']
12	End of infix		['+', '*']	ABC	pop '*' to postfix	Postfix: 'ABC*' | Stack: ['+']
13	Pop '+' to postfix		+	ABC*	pop '+'	Postfix: 'ABC*+' | Stack: []
14	Stack empty		[]	ABC*+	done	Postfix: 'ABC*+' | Stack: []

💡 All tokens processed and stack emptied, postfix expression complete.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 9	After Step 11	After Step 13	Final
postfix	''	'A'	'AB'	'AB'	'ABC'	'ABC*+'	'ABC*+'
stack	[]	[]	['+']	['+', '*']	['+', '*']	[]	[]
token	N/A	'A'	'B'	'*'	'C'	N/A	N/A

Key Moments - 3 Insights

Why do we push '*' on stack without popping '+' even though '+' is already there?

Because '*' has higher precedence than '+', so we keep '*' on top to ensure it is applied first. See step 8 and 9 in execution_table.

Why do operands go directly to postfix without stack?

Operands do not affect operator precedence, so they are added immediately to postfix. See steps 2, 6, and 11.

Why do we pop all remaining operators from stack at the end?

To ensure all operators are added to postfix after processing all tokens. See steps 12 and 13.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the stack state?

A ['+', '*']

B []

C ['+']

D ['*']

💡 Hint

Check the 'Stack State' column at step 9 in execution_table.

At which step does the postfix expression become 'ABC'?

A Step 2

B Step 6

C Step 11

D Step 14

💡 Hint

Look at the 'Postfix Expression' column in execution_table for when 'ABC' appears.

If the input was 'A+B*C', what would happen if we popped '+' before '*' at step 9?

A Postfix would be correct

B Postfix would be incorrect because '*' has higher precedence

C Stack would be empty too early

D Operands would be lost

💡 Hint

Refer to the precedence comparison and stack push logic in steps 8 and 9.

Concept Snapshot

Infix to Postfix Conversion Using Stack:
- Read tokens left to right
- Operands go directly to postfix
- '(' pushed to stack
- ')' pops until '('
- Operators pop higher/equal precedence operators before push
- At end, pop all stack to postfix

Full Transcript

This visualization shows how to convert an infix expression like 'A+B*C' to postfix using a stack. We read each token: if it's an operand, add it to postfix immediately. If it's an operator, we compare its precedence with the top of the stack and pop operators with higher or equal precedence to postfix before pushing the new operator. Parentheses are handled specially by pushing '(' and popping until '(' when ')' is found. After processing all tokens, we pop any remaining operators from the stack to postfix. The execution table tracks each step, showing the stack and postfix states. This method ensures operators are ordered correctly in postfix according to precedence and associativity.

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