Infix to Postfix Conversion Using Stack in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Postfix Conversion for Simple Expression

What is the output of this Rust code that converts the infix expression a+b*c to postfix notation?

DSA Rust

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

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

    for ch in expr.chars() {
        if ch.is_alphanumeric() {
            result.push(ch);
        } else {
            while !stack.is_empty() && precedence(*stack.last().unwrap()) >= precedence(ch) {
                result.push(stack.pop().unwrap());
            }
            stack.push(ch);
        }
    }

    while !stack.is_empty() {
        result.push(stack.pop().unwrap());
    }

    result
}

fn main() {
    let expr = "a+b*c";
    let postfix = infix_to_postfix(expr);
    println!("{}", postfix);
}

A "abc+*"

B "ab+c*"

C "abc*+"

D "a+bc*"

💡 Hint

Remember that multiplication (*) has higher precedence than addition (+).

The multiplication operator '*' has higher precedence than '+', so 'b*c' is evaluated first, then added to 'a'. The postfix expression is 'abc*+'.

❓ Predict Output

intermediate

Postfix Conversion Output with Parentheses

What is the output of this Rust code converting the infix expression (a+b)*c to postfix notation?

DSA Rust

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

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

    for ch in expr.chars() {
        if ch.is_alphanumeric() {
            result.push(ch);
        } else if ch == '(' {
            stack.push(ch);
        } else if ch == ')' {
            while *stack.last().unwrap() != '(' {
                result.push(stack.pop().unwrap());
            }
            stack.pop();
        } else {
            while !stack.is_empty() && precedence(*stack.last().unwrap()) >= precedence(ch) {
                result.push(stack.pop().unwrap());
            }
            stack.push(ch);
        }
    }

    while !stack.is_empty() {
        result.push(stack.pop().unwrap());
    }

    result
}

fn main() {
    let expr = "(a+b)*c";
    let postfix = infix_to_postfix(expr);
    println!("{}", postfix);
}

A "abc*+"

B "abc+*"

C "a+bc*"

D "ab+c*"

💡 Hint

Parentheses change the order of operations by forcing evaluation inside them first.

Parentheses cause 'a+b' to be evaluated first, so 'ab+' is formed, then multiplied by 'c', resulting in 'ab+c*'.

🔧 Debug

advanced

Identify the Error in Postfix Conversion Code

This Rust function aims to convert infix to postfix but produces incorrect output for a+b*c. What is the error?

DSA Rust

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

    for ch in expr.chars() {
        if ch.is_alphanumeric() {
            result.push(ch);
        } else {
            while !stack.is_empty() && precedence(ch) <= precedence(*stack.last().unwrap()) {
                result.push(stack.pop().unwrap());
            }
            stack.push(ch);
        }
    }

    while !stack.is_empty() {
        result.push(stack.pop().unwrap());
    }

    result
}

A The precedence comparison is reversed; it should be precedence(*stack.last().unwrap()) >= precedence(ch)

B The code does not handle parentheses, causing errors with expressions containing them

C The code pushes operators before popping higher precedence ones, causing wrong order

D The code incorrectly pushes operands to the stack instead of the result string

💡 Hint

Check the condition that decides when to pop from the stack.

The condition uses precedence(ch) <= precedence(top), which reverses the intended logic. It should pop while the top of stack has higher or equal precedence than the current operator.

🧠 Conceptual

advanced

Stack Usage in Infix to Postfix Conversion

Why is a stack the ideal data structure for converting infix expressions to postfix notation?

A Because it allows storing operators and retrieving them in reverse order to respect precedence and associativity

B Because it stores operands in sorted order automatically

C Because it can store unlimited characters without overflow

D Because it converts infix to postfix without needing to check operator precedence

💡 Hint

Think about how operators are processed in the order they appear and how precedence affects their placement.

A stack lets us push operators and pop them in reverse order, which helps apply operator precedence and associativity rules correctly during conversion.

❓ Predict Output

expert

Output of Complex Infix to Postfix Conversion

What is the output of this Rust code converting the infix expression a+b*(c^d-e)^(f+g*h)-i to postfix notation?

DSA Rust

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

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

    for ch in expr.chars() {
        if ch.is_alphanumeric() {
            result.push(ch);
        } else if ch == '(' {
            stack.push(ch);
        } else if ch == ')' {
            while *stack.last().unwrap() != '(' {
                result.push(stack.pop().unwrap());
            }
            stack.pop();
        } else {
            while !stack.is_empty() && precedence(*stack.last().unwrap()) >= precedence(ch) {
                if ch == '^' && *stack.last().unwrap() == '^' {
                    break;
                }
                result.push(stack.pop().unwrap());
            }
            stack.push(ch);
        }
    }

    while !stack.is_empty() {
        result.push(stack.pop().unwrap());
    }

    result
}

fn main() {
    let expr = "a+b*(c^d-e)^(f+g*h)-i";
    let postfix = infix_to_postfix(expr);
    println!("{}", postfix);
}

A "abcd^e-fgh*+^*+i-+"

B "abcd^e-fgh*+^*+i-"

C "abcd^efgh*+^-*+i-"

D "abcd^e-fgh*+^*+i"

💡 Hint

Remember that '^' is right-associative and has highest precedence.

The code correctly handles operator precedence and right-associativity of '^'. The postfix expression is 'abcd^e-fgh*+^*+i-'.

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