Infix to Postfix Conversion Using Stack in DSA Go

Mental Model

We use a stack to reorder operators so that expressions can be evaluated without parentheses and with correct priority.

Analogy: Imagine sorting tasks by priority on a desk: you put urgent tasks on top and do them first, then less urgent ones. The stack helps keep track of which operator comes next.

Infix: A + B * C
Stack: empty
Postfix: empty

Stack grows as operators wait to be placed in postfix order.

Dry Run Walkthrough

Input: infix expression: A + B * C

Goal: Convert the infix expression to postfix notation respecting operator precedence

Step 1: Read 'A', output it directly

Stack: []
Postfix: A

Why: Operands go directly to output

Step 2: Read '+', push it on stack

Stack: [+]
Postfix: A

Why: Operators are pushed to stack to wait for correct order

Step 3: Read 'B', output it directly

Stack: [+]
Postfix: A B

Why: Operands go directly to output

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

Stack: [+ *]
Postfix: A B

Why: Higher precedence operators wait on top of lower ones

Step 5: Read 'C', output it directly

Stack: [+ *]
Postfix: A B C

Why: Operands go directly to output

Step 6: End of expression reached, pop '*' from stack to output

Stack: [+]
Postfix: A B C *

Why: Pop remaining operators in correct order

Step 7: Pop '+' from stack to output

Stack: []
Postfix: A B C * +

Why: Finish by emptying stack

Result:

Stack: []
Postfix: A B C * +

Annotated Code

DSA Go

package main

import (
	"fmt"
	"unicode"
)

type Stack []rune

func (s *Stack) Push(r rune) {
	*s = append(*s, r)
}

func (s *Stack) Pop() rune {
	if len(*s) == 0 {
		return 0
	}
	index := len(*s) - 1
	el := (*s)[index]
	*s = (*s)[:index]
	return el
}

func (s *Stack) Peek() rune {
	if len(*s) == 0 {
		return 0
	}
	return (*s)[len(*s)-1]
}

func precedence(op rune) int {
	switch op {
	case '+', '-':
		return 1
	case '*', '/':
		return 2
	}
	return 0
}

func infixToPostfix(infix string) string {
	var stack Stack
	postfix := ""

	for _, ch := range infix {
		if unicode.IsLetter(ch) || unicode.IsDigit(ch) {
			postfix += string(ch) + " " // output operands directly
		} else if ch == '(' {
			stack.Push(ch) // push '(' to stack
		} else if ch == ')' {
			// pop until '(' is found
			for len(stack) > 0 && stack.Peek() != '(' {
				postfix += string(stack.Pop()) + " "
			}
			stack.Pop() // remove '('
		} else {
			// operator encountered
			for len(stack) > 0 && precedence(stack.Peek()) >= precedence(ch) {
				postfix += string(stack.Pop()) + " "
			}
			stack.Push(ch)
		}
	}

	// pop all remaining operators
	for len(stack) > 0 {
		postfix += string(stack.Pop()) + " "
	}

	if len(postfix) > 0 {
		postfix = postfix[:len(postfix)-1] // remove trailing space
	}
	return postfix
}

func main() {
	infix := "A+B*C"
	postfix := infixToPostfix(infix)
	fmt.Println(postfix)
}

if unicode.IsLetter(ch) || unicode.IsDigit(ch) {

output operands directly to postfix

else if ch == '(' {

push '(' to stack to handle precedence inside parentheses

else if ch == ')' {

pop from stack until '(' is found to close parentheses

for len(stack) > 0 && precedence(stack.Peek()) >= precedence(ch) {

pop operators with higher or equal precedence before pushing new operator

stack.Push(ch)

push current operator to stack

for len(stack) > 0 {

pop all remaining operators after processing input

Output

A B C * +

Complexity Analysis

Time: O(n) because we scan the input expression once and each operator is pushed and popped at most once

Space: O(n) because the stack can hold all operators in worst case and output string grows with input size

vs Alternative: Compared to evaluating infix directly with repeated scanning or recursion, using a stack for postfix conversion is more efficient and simpler to implement

Edge Cases

empty expression

returns empty postfix string without error

DSA Go

for _, ch := range infix {

expression with parentheses

correctly handles nested parentheses by pushing '(' and popping until ')' is found

DSA Go

else if ch == ')' {

expression with multiple operators of same precedence

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

DSA Go

for len(stack) > 0 && precedence(stack.Peek()) >= precedence(ch) {

When to Use This Pattern

When you see an expression with operators and parentheses and need to evaluate or reorder it, use the stack-based infix to postfix conversion pattern to simplify evaluation.

Common Mistakes

Mistake: Not popping all operators from stack at the end, leaving some operators unprocessed
Fix: Add a final loop to pop all remaining operators after processing the input

Mistake: Ignoring operator precedence and pushing all operators directly without popping
Fix: Compare precedence and pop operators with higher or equal precedence before pushing new operator

Mistake: Not handling parentheses correctly, especially not popping until '(' on encountering ')'
Fix: On reading ')', pop from stack until '(' is found and remove '(' from stack

Summary

Converts an infix expression to postfix notation using a stack to reorder operators.

Use when you need to evaluate or simplify expressions with operators and parentheses.

The key insight is using a stack to hold operators and pop them in order of precedence and associativity.

Practice

1. What is the main purpose of using a stack in Infix to Postfix Conversion?

easy

A. To temporarily hold operators and manage their precedence

B. To store the final postfix expression

C. To reverse the infix expression

D. To count the number of operands

Solution

1. Step 1: Understand the role of stack in conversion

   The stack is used to hold operators temporarily while processing the infix expression to respect operator precedence and associativity.

2. Step 2: Identify what is stored in stack

   Operands are directly added to the output, while operators are pushed to the stack to decide their order in postfix.

3. Final Answer:

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

4. Quick Check:

   Stack holds operators for precedence [OK]

Hint: Stack holds operators, output holds operands [OK]

Common Mistakes:

• Thinking stack stores operands
• Confusing stack role with output
• Ignoring operator precedence

2. Which of the following Go code snippets correctly initializes an empty stack for infix to postfix conversion?

easy

A. var stack []rune = []rune{}

B. stack := make([]int, 0)

C. stack := []string{0}

D. var stack []int = nil

Solution

1. Step 1: Identify correct stack type for operators

   Operators are characters, so stack should be a slice of runes (characters) initialized empty.

2. Step 2: Check initialization correctness

   var stack []rune = []rune{} initializes an empty rune slice correctly. stack := make([]int, 0) uses int slice, not suitable. stack := []string{0} has syntax error (cannot use int 0 as string). var stack []int = nil is nil slice, which can cause runtime errors.

3. Final Answer:

   var stack []rune = []rune{} -> Option A

4. Quick Check:

   Empty rune slice for operator stack [OK]

Hint: Use rune slice for operator stack [OK]

Common Mistakes:

• Using int slice for operators
• Initializing with wrong type
• Using nil slice without initialization

3. What is the postfix expression output by the following Go code snippet for input "a+b*c"?

infix := "a+b*c"
// Assume correct infix to postfix conversion function called here
postfix := InfixToPostfix(infix)
fmt.Println(postfix)

medium

A. "a+bc*"

B. "ab+c*"

C. "abc*+"

D. "*abc+"

Solution

1. Step 1: Analyze operator precedence in expression

   Multiplication (*) has higher precedence than addition (+), so 'b*c' is evaluated before adding 'a'.

2. Step 2: Convert infix to postfix step-by-step

   Postfix is formed as 'a' 'b' 'c' '*' '+', which is "abc*+".

3. Final Answer:

   "abc*+" -> Option C

4. Quick Check:

   Multiplication before addition = "abc*+" [OK]

Hint: Multiply before add means * goes before + in postfix [OK]

Common Mistakes:

• Ignoring operator precedence
• Placing + before * in postfix
• Confusing operand order

4. Given this Go function snippet for infix to postfix conversion, what is the bug?

func precedence(op rune) int {
    if op == '+' || op == '-' {
        return 1
    } else if op == '*' || op == '/' {
        return 2
    }
    return 0
}

// InfixToPostfix function uses precedence(op) to compare operators
// but outputs incorrect postfix for input "a+b^c"

medium

A. Precedence function returns 0 for non-operators causing errors

B. Precedence function returns int instead of float

C. Precedence values for '+' and '-' are swapped

D. Precedence function does not handle '^' operator

Solution

1. Step 1: Check if all operators are handled

   The function handles '+', '-', '*', '/' but misses '^' (exponent) operator which is common in infix expressions.

2. Step 2: Understand impact on output

   If input contains '^', missing precedence causes wrong order in postfix output.

3. Final Answer:

   Precedence function does not handle '^' operator -> Option D

4. Quick Check:

   Missing '^' causes wrong postfix [OK]

Hint: Include all operators in precedence function [OK]

Common Mistakes:

• Ignoring missing operators
• Assuming 0 precedence is error
• Confusing precedence values

5. How would you modify the infix to postfix algorithm to correctly handle parentheses in the expression (a+b)*c?

hard

A. Ignore parentheses and treat them as operands

B. Push '(' onto stack and pop operators until '(' when ')' is found

C. Remove all parentheses before conversion

D. Treat '(' as higher precedence operator and never pop it

Solution

1. Step 1: Understand role of parentheses in infix

   Parentheses change normal precedence by grouping expressions to evaluate first.

2. Step 2: Modify stack operations for parentheses

   Push '(' onto stack when encountered. When ')' is found, pop operators until '(' is popped, discarding both parentheses.

3. Final Answer:

   Push '(' onto stack and pop operators until '(' when ')' is found -> Option B

4. Quick Check:

   Parentheses control stack push/pop [OK]

Hint: Push '(' and pop until '(' on ')' [OK]

Common Mistakes:

• Ignoring parentheses in algorithm
• Treating parentheses as operands
• Not popping until '(' on ')'