Infix to Postfix Conversion Using Stack in DSA Rust - Time & Space Complexity

Time Complexity: Infix to Postfix Conversion Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to convert an infix expression to postfix grows as the expression gets longer.

How does the number of steps change when the input expression size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn infix_to_postfix(expression: &str) -> String {
    let mut stack = Vec::new();
    let mut result = String::new();
    for ch in expression.chars() {
        if ch.is_alphanumeric() {
            result.push(ch);
        } else if ch == '(' {
            stack.push(ch);
        } else if ch == ')' {
            while let Some(top) = stack.pop() {
                if top == '(' { break; }
                result.push(top);
            }
        } else {
            while let Some(&top) = stack.last() {
                if precedence(top) >= precedence(ch) {
                    result.push(stack.pop().unwrap());
                } else {
                    break;
                }
            }
            stack.push(ch);
        }
    }
    while let Some(op) = stack.pop() {
        result.push(op);
    }
    result
}

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

This code converts an infix expression (like "a+b*c") to postfix form (like "abc*+") using a stack to manage operators.

Identify Repeating Operations

• Primary operation: Looping through each character of the input expression once.
• How many times: Exactly once for each character (n times for input size n).
• Inside the loop, there are while loops that pop from the stack, but each operator is pushed and popped at most once.

How Execution Grows With Input

As the expression length grows, the number of steps grows roughly in a straight line with the number of characters.

Input Size (n)	Approx. Operations
10	About 10 main loop steps plus some stack operations
100	About 100 main loop steps plus stack operations, still proportional to 100
1000	About 1000 main loop steps plus stack operations, proportional to 1000

Pattern observation: The total work grows linearly with input size because each character is processed once and each operator pushed and popped once.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows directly in proportion to the length of the input expression.

Common Mistake

[X] Wrong: "Because of nested while loops, the time complexity is quadratic O(n²)."

[OK] Correct: Each operator is pushed and popped only once, so the inner loops do not multiply the total steps beyond linear growth.

Interview Connect

Understanding this linear time complexity shows you can efficiently handle expression parsing, a common task in many programming problems.

Self-Check

"What if the input expression included multi-character operands instead of single characters? How would the time complexity change?"

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