Expression evaluation in Rust - Time & Space Complexity

Time Complexity: Expression evaluation

O(n)

Understanding Time Complexity

When we evaluate expressions in code, we want to know how the time it takes grows as the expression gets bigger.

We ask: How does the number of steps change when the expression has more parts?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn evaluate_expression(expr: &str) -> i32 {
    let mut stack = Vec::new();
    for ch in expr.chars() {
        if ch.is_digit(10) {
            stack.push(ch.to_digit(10).unwrap() as i32);
        } else {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            let res = match ch {
                '+' => a + b,
                '-' => a - b,
                '*' => a * b,
                '/' => a / b,
                _ => 0,
            };
            stack.push(res);
        }
    }
    stack.pop().unwrap()
}
    

This code evaluates a simple expression in postfix form using a stack.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the expression string.
• How many times: Once for every character in the input expression.

How Execution Grows With Input

As the expression gets longer, the code checks each character once, so the work grows steadily.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The number of steps grows directly with the size of the expression.

Final Time Complexity

Time Complexity: O(n)

This means the time to evaluate grows in a straight line with the length of the expression.

Common Mistake

[X] Wrong: "Evaluating an expression always takes a lot more time because of nested operations."

[OK] Correct: Here, each character is handled once in order, so nested or not, the time grows just with expression length.

Interview Connect

Understanding how expression evaluation scales helps you explain how code handles bigger inputs clearly and confidently.

Self-Check

"What if we changed the input to include parentheses and had to handle them? How would the time complexity change?"

Practice

1. What does the following Rust expression do?
let result = 5 + 3 * 2;
Choose the correct description.

easy

A. Calculates 3 times 2, then adds 5

B. Multiplies 5 by 3, then adds 2

C. Calculates 5 plus 3, then multiplies by 2

D. Adds 5, 3, and 2 together

Solution

1. Step 1: Understand operator precedence in Rust

   Multiplication (*) has higher precedence than addition (+), so 3 * 2 is calculated first.

2. Step 2: Calculate the expression step-by-step

   3 * 2 = 6, then 5 + 6 = 11.

3. Final Answer:

   Calculates 3 times 2, then adds 5 -> Option A

4. Quick Check:

   5 + (3 * 2) = 11 [OK]

Hint: Remember multiplication before addition in expressions [OK]

Common Mistakes:

• Adding numbers left to right ignoring precedence
• Multiplying after addition
• Confusing operator precedence

2. Which of the following is the correct way to assign the result of 4 + 7 to a variable named sum in Rust?

easy

A. let sum : 4 + 7;

B. sum = let 4 + 7;

C. let sum = 4 + 7;

D. let sum == 4 + 7;

Solution

1. Step 1: Recall Rust variable assignment syntax

   In Rust, use let variable = expression; to assign a value.

2. Step 2: Check each option for correct syntax

   let sum = 4 + 7; uses correct syntax: let sum = 4 + 7;. Others have syntax errors.

3. Final Answer:

   let sum = 4 + 7; -> Option C

4. Quick Check:

   Correct Rust assignment syntax [OK]

Hint: Use 'let var = expression;' to assign values [OK]

Common Mistakes:

• Using '==' instead of '=' for assignment
• Placing 'let' after variable name
• Using ':' instead of '=' for assignment

3. What is the output of this Rust code?

fn main() {
    let x = 10;
    let y = 3;
    let result = x / y + x % y;
    println!("{}", result);
}

medium

A. 13

B. 3

C. 1

D. 4

Solution

1. Step 1: Calculate integer division and remainder

   10 / 3 = 3 (integer division), 10 % 3 = 1 (remainder).

2. Step 2: Add the results

   3 + 1 = 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   10 / 3 + 10 % 3 = 4 [OK]

Hint: Remember integer division drops decimals, % gives remainder [OK]

Common Mistakes:

• Treating division as float division
• Confusing remainder with division result
• Adding operands incorrectly

4. Identify the error in this Rust code snippet:

fn main() {
    let a = 5;
    let b = 0;
    let c = a / b;
    println!("{}", c);
}

medium

A. Division by zero causes a runtime panic

B. Variable 'c' is not declared properly

C. Missing semicolon after 'let b = 0'

D. println! macro syntax is incorrect

Solution

1. Step 1: Analyze the division operation

   The code divides 'a' by 'b', where 'b' is zero.

2. Step 2: Understand Rust runtime behavior

   Dividing by zero in Rust causes a runtime panic (crash), not a compile error.

3. Final Answer:

   Division by zero causes a runtime panic -> Option A

4. Quick Check:

   Division by zero panics in Rust [OK]

Hint: Check for zero divisor before division to avoid panic [OK]

Common Mistakes:

• Thinking division by zero is a compile error
• Ignoring runtime panics
• Assuming variable declaration errors

5. Given a list of numbers, which Rust expression correctly calculates the sum of all even numbers?

let numbers = [1, 2, 3, 4, 5, 6];
let sum_even = /* fill here */;
println!("{}", sum_even);

Choose the correct expression to replace /* fill here */.

hard

A. numbers.iter().map(|x| x * 2).sum::<i32>()

B. numbers.iter().filter(|&&x| x % 2 == 0).sum::<i32>()

C. numbers.iter().filter(|&x| x % 2 != 0).sum::<i32>()

D. numbers.iter().sum::<i32>()

Solution

1. Step 1: Understand the goal

   We want to sum only even numbers from the list.

2. Step 2: Analyze each option

   numbers.iter().filter(|&&x| x % 2 == 0).sum::<i32>() filters even numbers (x % 2 == 0) and sums them. numbers.iter().map(|x| x * 2).sum::<i32>() doubles all numbers then sums (wrong). numbers.iter().filter(|&x| x % 2 != 0).sum::<i32>() sums odd numbers (wrong). numbers.iter().sum::<i32>() sums all numbers (wrong).

3. Final Answer:

   numbers.iter().filter(|&&x| x % 2 == 0).sum::<i32>() -> Option B

4. Quick Check:

   Filter evens then sum [OK]

Hint: Filter even numbers before summing with iterator methods [OK]

Common Mistakes:

• Summing all numbers without filtering
• Filtering odd numbers instead of even
• Mapping values incorrectly before sum