Infix to Postfix Conversion Using Stack in DSA Rust - Build from Scratch

Infix to Postfix Conversion Using Stack

📖 Scenario: You are building a simple calculator that converts math expressions written in the usual way (called infix) into a form that computers find easier to calculate (called postfix).For example, the expression (A + B) * C in infix becomes A B + C * in postfix.

🎯 Goal: Build a Rust program that converts a given infix expression string into its postfix form using a stack.

📋 What You'll Learn

Create a stack to hold operators

Use a precedence function to compare operator priority

Process each character of the infix expression

Output the postfix expression as a string

💡 Why This Matters

🌍 Real World

Converting infix to postfix is a key step in calculators and compilers to evaluate expressions efficiently.

💼 Career

Understanding stacks and expression parsing is important for software engineers working on interpreters, compilers, and calculators.

1

Create the infix expression string

Create a variable called infix_expr and set it to the string "A+B*C".

DSA Rust

# Create a variable called infix_expr and set it to "A+B*C"
# Your code here

Hint

Use let infix_expr = "A+B*C"; to create the string.

2

Define operator precedence function

Define a function called precedence that takes a char parameter called op and returns an i32. It should return 2 for '*' and '/', 1 for '+' and '-', and 0 for any other character.

DSA Rust

let infix_expr = "A+B*C";
// Define the precedence function below
# Your code here

Hint

Use a match statement to return precedence values for operators.

3

Convert infix to postfix using a stack

Create a mutable vector called stack to hold char. Create a mutable string called postfix. Loop over each character ch in infix_expr.chars(). If ch is a letter (check with ch.is_alphabetic()), append it to postfix. If ch is an operator, pop from stack to postfix while the top of stack has higher or equal precedence. Then push ch to stack. After the loop, pop all remaining operators from stack to postfix.

DSA Rust

let infix_expr = "A+B*C";

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

// Create stack and postfix variables
// Loop over infix_expr.chars() and apply conversion logic
# Your code here

Hint

Use a vector as a stack and a string to build the postfix expression step by step.

4

Print the postfix expression

Write a println! statement to print the postfix string.

DSA Rust

let infix_expr = "A+B*C";

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

let mut stack: Vec = Vec::new();
let mut postfix = String::new();

for ch in infix_expr.chars() {
    if ch.is_alphabetic() {
        postfix.push(ch);
    } else {
        while let Some(&top) = stack.last() {
            if precedence(top) >= precedence(ch) {
                postfix.push(stack.pop().unwrap());
            } else {
                break;
            }
        }
        stack.push(ch);
    }
}

while let Some(op) = stack.pop() {
    postfix.push(op);
}

// Print the postfix expression
# Your code here

Hint

Use println!("{}", postfix); to show the result.

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