Aiming for idiomatic Rust

Recently I was exploring ways to work with pattern matching in Rust - using a small relatable example that many people may have come across during technical interviews or in online code challenges.

The problem is as follows: given a string input, determine if parenthesis, brackets and braces are 'balanced'.

That it to say that any occurrence of ( must eventually be followed by its closing partner ).

For example, () would be balanced, as would (1+2). If the closing paren is missing however, then it's not balanced, such as (1-3.

The rule holds true for the other 2 pairs, so this is balanced ([{123}]) because each pair is closed before another is opened, but (]) is NOT balanced because ] has no opener.

First, a stack-based approach

Given my background in Web programming, I was not immediately thinking about the most efficient implementation in Rust, but rather I was focussing on the pattern-matching syntax and this is what I came up.

fn balanced(input: &str) -> bool {
    let mut stack: Vec<char> = vec![];
    for c in input.chars() {
        match c {
            '(' | '[' | '{' => stack.push(c),
            ')' | ']' | '}' => match (stack.pop(), c) {
                (Some('('), ')') => {}
                (Some('['), ']') => {}
                (Some('{'), '}') => {}
                (_, _) => return false,
            },
            _ => {}
        }
    }
    stack.len() == 0
}
 
#[test]
fn test_balanced() {
    assert_eq!(balanced("[]"), true);
    assert_eq!(balanced("["), false);
    assert_eq!(balanced("(())"), true);
    assert_eq!(balanced("((()"), false);
    assert_eq!(balanced(")(())"), false);
    assert_eq!(balanced("))))"), false);
    assert_eq!(balanced("(()))("), false);
    assert_eq!(balanced("([])"), true);
    assert_eq!(balanced("([[[]]])"), true);
    assert_eq!(balanced("([[[00]])"), false);
    assert_eq!(balanced("([[[{0}]]])"), true);
}

In Big O Notation we'd say this has a time complexity of O(n) since our worst case scenario is that we'd have to access every single char once (looping all the way through the string).

The stack will grow & contract slightly as elements are added/removed.

Dropping the nested match

I shared my first attempt on Twitter, asking for help from fellow Rust developers since the nested match just felt wrong

There were a number of extremely helpful responses (see the tweet/thread), my favourite of which shows how the arms in Rust's match expressions can be followed by an optional guard.

rust
///
/// Without a guard - the first match
/// arm here just has 3 patterns.
///
match c {
    '(' | '[' | '{' => { /* omitted */ },
    _ => {}
}

In that example, we say the first match arm has 3 patterns and we know where they end due to the =>. That is to say that everything to the left of the => is any number of patterns - it's then followed on the right by the expression to be executed if a match is found on this arm.

Adding a guard

Notice in the following example how the if stack.pop() != Some(c) is placed before the => and from what we just learned above we know that means it's not the expression to be executed after a match. It's actually there as part of the matching and even allows mutation of the stack.

rust
///
/// With a guard.
///
match c {
//   Patterns           MatchArmGuard
// ↓↓↓↓↓↓↓↓↓↓↓↓↓  ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
  ')' | ']' | '}' if stack.pop() != Some(c) => return false,
  _ => {}
}

Putting it together

The full algorithm looks like this now, and although the Match Guard here doesn't save that much (the if could be inside the block instead), it's usefulness becomes apparent when you realise that you can have match guards on multiple arms.

pub fn balanced(input: &str) -> bool {
    let mut stack: Vec<char> = vec![];
    for c in input.chars() {
        match c {
            '(' => stack.push(')'),
            '[' => stack.push(']'),
            '{' => stack.push('}'),
            ')' | ']' | '}' if stack.pop() != Some(c) => {
                return false
            },
            _ => {}
        }
    }
    stack.is_empty()
}

Stack-based solution Visualization

In this visualization you can clearly see how we only have a single pointer (representing the loop) - the stack grows/shrinks as comparisons are made.

Recursive solution

Whilst my original call for help on Twitter was not directly asking for more efficient solutions, I still got a fair few people recommending a recursive solution to avoid the overhead of the Vec<char>.

The idea is that for this particular problem you can solve it with similar time complexity O(n) but without having to allocate memory for the Vec and therefore dropping all the behind-the-scenes book-keeping needed for Vec's, like bounds & capacity checking. It was noted too, that a recursive solution is more flexible

pub fn balanced(input: &str) -> bool {
    expect(None, &mut input.chars())
}
fn expect(end: Option<char>, input: &mut Chars) -> bool {
    loop {
        let c = input.next();
        let good = match c {
            Some('(') => expect(Some(')'), input),
            Some('[') => expect(Some(']'), input),
            Some('{') => expect(Some('}'), input),
            Some(')') | Some(']') | Some('}') | None => {
                return end == c
            },
            _ => true,
        };
        if !good { return false; }
    }
}

Here we've introduced a second function expect, which is where the recursion will occur.

We kick it off with the initial call to expect from inside balanced, providing None as the end comparison (the thing we try to match when we've seen an opener) and creating a mutable iterator of chars.

Each call to expect will end up in the loop and 1 char at a time will be accessed from the input. If an opening brace/paren/bracket is found then the function is called again with the remainder of the input.

For the example (1+2) you can visualize the call stack like this

calls to 'expect'
    1: end: None, input: "(1+2)"
    1.1 input.next() = "("
        2: end: Some(")"), input: "1+2)"
        2.1 input.next() = "1"
        2.2 input.next() = "+"
        2.3 input.next() = "2"
        2.4 input.next() = ")"
        2.5 return compare Some(")") == Some(c)

Notice that on the very first call because ( is matched, it means we immediately descend into a recursive call. If the input string did not begin with an opener then we'd keep consuming chars first.

For the input 123() the call stack would look like

calls to 'expect'
    1: end: None, input: "123()"
    1.1 input.next() = "1"
    1.2 input.next() = "2"
    1.3 input.next() = "3"
    1.4 input.next() = "("
        2: end: Some(")"), input: ")"
        2.1 input.next() = ")"
        2.2 return compare Some(")") == Some(c)

Recursive solution, visualization

The recursive calls are modelled here as extra pointers (highlighted with different colours) - but the most important thing to note here is the absence of any additional data structures.

Which is 'better'?

These 2 examples solve the same problem, but the recursive solution (especially in a language like Rust) seems to have more benefits. The only advantage to the stack-based approach that I can think of is the easier learning curve.

Either way, talking about and creating visualizations of both has helped me develop a feeling for how I can make more posts like this, perhaps going over common interview-style questions. Showing their implementations in Rust along with animations.

Please reach out to me on Twitter if you'd like to propose a topic.