Infix to Postfix Conversion Using Stack in DSA Rust

Mental Model

We change a math expression from normal reading order to a form where operators come after their numbers, using a stack to keep track of operators.

Analogy: Imagine you are cooking and have a stack of recipe cards. You put cards with cooking steps on the stack and take them off in the right order to finish the dish correctly.

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

Dry Run Walkthrough

Input: infix expression: A + B * C

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

Step 1: Read 'A', output it directly

Postfix: A
Stack: [empty]

Why: Operands go directly to output

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

Postfix: A
Stack: +

Why: Operators are stored on stack to wait for correct order

Step 3: Read 'B', output it directly

Postfix: A B
Stack: +

Why: Operands go directly to output

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

Postfix: A B
Stack: + *

Why: Higher precedence operators go on top of lower ones

Step 5: Read 'C', output it directly

Postfix: A B C
Stack: + *

Why: Operands go directly to output

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

Postfix: A B C *
Stack: +

Why: Pop remaining operators in correct order

Step 7: Pop '+' from stack to output

Postfix: A B C * +
Stack: [empty]

Why: Finish by emptying the stack

Result:

Postfix: A B C * +

Annotated Code

DSA Rust

use std::collections::VecDeque;

fn precedence(op: char) -> i32 {
    match op {
        '+' | '-' => 1,
        '*' | '/' => 2,
        _ => 0,
    }
}

fn infix_to_postfix(expression: &str) -> String {
    let mut stack: Vec<char> = Vec::new();
    let mut output = String::new();

    for ch in expression.chars() {
        if ch.is_alphanumeric() {
            output.push(ch);
            output.push(' ');
        } else if ch == '(' {
            stack.push(ch);
        } else if ch == ')' {
            while let Some(top) = stack.pop() {
                if top == '(' {
                    break;
                } else {
                    output.push(top);
                    output.push(' ');
                }
            }
        } else if ch == '+' || ch == '-' || ch == '*' || ch == '/' {
            while let Some(&top) = stack.last() {
                if precedence(top) >= precedence(ch) {
                    output.push(stack.pop().unwrap());
                    output.push(' ');
                } else {
                    break;
                }
            }
            stack.push(ch);
        }
    }

    while let Some(top) = stack.pop() {
        output.push(top);
        output.push(' ');
    }

    output.trim_end().to_string()
}

fn main() {
    let expression = "A+B*C";
    let postfix = infix_to_postfix(expression);
    println!("{}", postfix);
}

if ch.is_alphanumeric() { output.push(ch); output.push(' '); }

Output operands immediately

while let Some(&top) = stack.last() { if precedence(top) >= precedence(ch) { output.push(stack.pop().unwrap()); output.push(' '); } else { break; } } stack.push(ch);

Pop operators with higher or equal precedence before pushing current operator

while let Some(top) = stack.pop() { output.push(top); output.push(' '); }

Pop all remaining operators 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) for the stack and output string to hold operators and operands

vs Alternative: Compared to evaluating directly or using recursion, this stack method is simpler and more efficient for conversion

Edge Cases

Empty expression

Returns empty output without error

DSA Rust

for ch in expression.chars() { ... } handles empty input gracefully

Expression with parentheses

Parentheses are handled by pushing '(' and popping until '(' on ')'

DSA Rust

if ch == '(' { stack.push(ch); } else if ch == ')' { while let Some(top) = stack.pop() { if top == '(' { break; } else { output.push(top); } } }

Expression with multiple operators of same precedence

Operators with same precedence are popped before pushing new operator

DSA Rust

while let Some(&top) = stack.last() { if precedence(top) >= precedence(ch) { output.push(stack.pop().unwrap()); } else { break; } }

When to Use This Pattern

When you need to convert expressions from normal math order to a form easier for computers to evaluate, use the stack-based infix to postfix conversion pattern.

Common Mistakes

Mistake: Not handling operator precedence correctly, causing wrong output order
Fix: Use a precedence function and pop from stack while top operator has higher or equal precedence

Mistake: Forgetting to pop all remaining operators after processing input
Fix: Add a final loop to pop and output all remaining operators from the stack

Mistake: Not handling parentheses properly, leading to incorrect grouping
Fix: Push '(' on stack and pop until '(' when ')' is encountered

Summary

Converts a math expression from infix to postfix notation using a stack to manage operators.

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

The key is to push operators on a stack and pop them in order of precedence to build the postfix output.

Practice

1. What is the main purpose of using a stack in converting an infix expression to postfix?

easy

A. To temporarily hold operators and manage their precedence

B. To store operands permanently

C. To reverse the order of operands

D. To count the number of operators

Solution

1. Step 1: Understand the role of stack in operator handling

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

2. Step 2: Clarify why operands are not stored in stack

   Operands are directly added to the postfix output; only operators need temporary storage to ensure correct order.

3. Final Answer:

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

4. Quick Check:

   Stack holds operators = A [OK]

Hint: Stack holds operators, not operands, to manage precedence [OK]

Common Mistakes:

• Thinking stack stores operands
• Confusing stack role with reversing operands
• Assuming stack counts operators

2. Which of the following Rust code snippets correctly initializes an empty stack for characters used in infix to postfix conversion?

easy

A. let stack: Vec<char> = new Vec();

B. let mut stack: Vec<char> = Vec::new();

C. let stack = Vec<char>();

D. let mut stack = Vec::empty();

Solution

1. Step 1: Identify correct Rust syntax for empty vector

   In Rust, an empty vector is created with Vec::new(), and mutability requires 'mut'.

2. Step 2: Check each option for syntax correctness

   let mut stack: Vec<char> = Vec::new(); uses correct syntax: mutable vector of chars with Vec::new(). Others have syntax errors or invalid methods.

3. Final Answer:

   let mut stack: Vec<char> = Vec::new(); -> Option B

4. Quick Check:

   Vec::new() + mut = C [OK]

Hint: Use 'let mut stack: Vec<char> = Vec::new();' to create empty stack [OK]

Common Mistakes:

• Omitting 'mut' for mutable stack
• Using invalid Vec constructors
• Confusing Vec::new() with Vec::empty()

3. Given the infix expression a + b * c, what is the correct postfix expression after conversion using a stack?

medium

A. a b + c *

B. a * b + c

C. a b c * +

D. a + b c *

Solution

1. Step 1: Apply operator precedence rules

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

2. Step 2: Convert to postfix respecting precedence

   Postfix becomes 'a b c * +' where 'b c *' is first, then 'a' and '+' applied last.

3. Final Answer:

   a b c * + -> Option C

4. Quick Check:

   Multiplication before addition = a b c * + [OK]

Hint: Multiply before add: postfix is a b c * + [OK]

Common Mistakes:

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

4. Consider this Rust snippet for infix to postfix conversion stack push operation: stack.push(token); If the stack is not declared mutable, what error will occur?

medium

A. No error, code runs fine

B. Stack overflow error

C. Syntax error: missing semicolon

D. Cannot borrow immutable variable `stack` as mutable

Solution

1. Step 1: Understand Rust mutability rules

   In Rust, to modify a variable like pushing to a vector, it must be declared mutable with 'mut'.

2. Step 2: Identify error from pushing to immutable stack

   Trying to push to an immutable vector causes a compile-time error: cannot borrow immutable variable as mutable.

3. Final Answer:

   Cannot borrow immutable variable `stack` as mutable -> Option D

4. Quick Check:

   Push needs mutable stack = D [OK]

Hint: Declare stack mutable to push: 'let mut stack' [OK]

Common Mistakes:

• Ignoring mut keyword
• Assuming runtime error instead of compile error
• Confusing syntax errors with mutability errors

5. Given the infix expression (a + b) * (c - d) / e, what is the correct postfix expression after conversion using a stack?

hard

A. a b + c d - * e /

B. a b c d - + * e /

C. a b + c d - e / *

D. a b + * c d - 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 stepwise to postfix

   Postfix of (a + b) is 'a b +', (c - d) is 'c d -', then multiply '*', then divide by 'e' with '/'.

3. Final Answer:

   a b + c d - * e / -> Option A

4. Quick Check:

   Parentheses respected: a b + c d - * e / [OK]

Hint: Convert inside parentheses first, then apply operators [OK]

Common Mistakes:

• Ignoring parentheses order
• Misplacing operators in postfix
• Mixing operand order