rs-02-balanced

# Balanced brackets

Implement the library file **`src/lib.rs`** exposing:

```rust
pub fn is_balanced(input: &str) -> bool
```

Return `true` if and only if the brackets `()`, `[]`, and `{}` in `input` are
correctly balanced and nested. Every opening bracket must be closed by a matching
closing bracket in the right order. Any closing bracket must match the most
recently opened, still-unclosed bracket.

- Non-bracket characters are ignored.
- The empty string is balanced (returns `true`).

Examples:

- `is_balanced("")` → `true`
- `is_balanced("()[]{}")` → `true`
- `is_balanced("([{}])")` → `true`
- `is_balanced("(a + [b * c]) - {d}")` → `true`
- `is_balanced("(]")` → `false`
- `is_balanced("([)]")` → `false`
- `is_balanced("(")` → `false`
- `is_balanced(")(")` → `false`

Tests live in `tests/` and call it as `challenge::is_balanced`.

use challenge::is_balanced;

#[test]
fn empty_is_balanced() {
    assert!(is_balanced(""));
}

#[test]
fn simple_pairs() {
    assert!(is_balanced("()[]{}"));
    assert!(is_balanced("([{}])"));
}

#[test]
fn ignores_non_brackets() {
    assert!(is_balanced("(a + [b * c]) - {d}"));
    assert!(is_balanced("no brackets at all"));
}

#[test]
fn mismatched_type() {
    assert!(!is_balanced("(]"));
    assert!(!is_balanced("{)"));
}

#[test]
fn wrong_nesting_order() {
    assert!(!is_balanced("([)]"));
}

#[test]
fn unclosed_or_unopened() {
    assert!(!is_balanced("("));
    assert!(!is_balanced(")("));
    assert!(!is_balanced("(()"));
}

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

To solve this problem, we need to determine if a given string has balanced brackets. The brackets in question are `()`, `[]`, and `{}`. The string is considered balanced if every opening bracket has a corresponding closing bracket in the correct order, and any closing bracket matches the most recent unclosed opening bracket. Non-bracket characters are ignored, and an empty string is considered balanced.

### Approach
The approach to solve this problem involves using a stack data structure to keep track of the expected closing brackets. Here's a step-by-step breakdown of the approach:

1. **Initialize a Stack**: Use a stack to keep track of the closing brackets that should follow the encountered opening brackets.
2. **Iterate Through Each Character**: Loop through each character in the input string.
3. **Process Opening Brackets**: When an opening bracket (`(`, `[`, `{`) is encountered, push the corresponding closing bracket (`)`, `]`, `}`) onto the stack.
4. **Process Closing Brackets**: When a closing bracket is encountered, check if the stack is empty (which would mean there's no corresponding opening bracket) or if the top of the stack does not match the current closing bracket. If either condition is true, the string is unbalanced.
5. **Ignore Non-Bracket Characters**: Any character that is not a bracket is simply ignored.
6. **Check Stack at End**: After processing all characters, if the stack is empty, all brackets were properly matched and nested, so the string is balanced. If the stack is not empty, some brackets were not closed, so the string is unbalanced.

### Solution Code
```rust
pub fn is_balanced(input: &str) -> bool {
    let mut stack = Vec::new();
    for c in input.chars() {
        match c {
            '(' => stack.push(')'),
            '[' => stack.push(']'),
            '{' => stack.push('}'),
            ')' | ']' | '}' => {
                if stack.is_empty() || stack.pop() != Some(c) {
                    return false;
                }
            },
            _ => {}
        }
    }
    stack.is_empty()
}
```

### Explanation
- **Stack Initialization**: An empty stack is created to keep track of the expected closing brackets.
- **Character Processing**: Each character in the input string is processed. Opening brackets push their corresponding closing brackets onto the stack. Closing brackets check against the top of the stack to ensure they match the most recent unclosed opening bracket.
- **Matching Check**: If a closing bracket does not match the expected closing bracket (top of the stack), the function immediately returns `false`.
- **Final Check**: After processing all characters, if the stack is empty, all brackets were matched correctly, and the function returns `true`. If the stack is not empty, some brackets were not closed, and the function returns `false`.

This approach efficiently ensures that all brackets are balanced and nested correctly using a stack, which is optimal for this type of problem.

Okay, I need to solve this problem where I have to determine if a string has balanced brackets. The function is called is_balanced and it takes a string slice as input, returning a boolean. So, the task is to check if all the brackets—(), [], {}—are correctly balanced and nested. 

First, I should think about how to approach this. I remember that for bracket balancing, a stack data structure is typically used. The idea is that every time I encounter an opening bracket, I push it onto the stack. When I encounter a closing bracket, I check if it matches the top of the stack. If it does, I pop the stack; if not, the string is unbalanced.

But wait, the input can have other characters that we need to ignore. So, I should process only the bracket characters and skip everything else. That makes sense.

Let me outline the steps:

1. Iterate through each character in the input string.
2. For each character, check if it's a bracket. If not, skip it.
3. If it's an opening bracket (i.e., '(', '[', '{'), push the corresponding closing bracket onto the stack. Or maybe push the opening bracket and then when a closing comes, compare. Hmm, perhaps it's better to push the expected closing bracket so when a closing bracket is found, we can just compare it to the top of the stack.
4. If it's a closing bracket, check if the stack is empty. If it is, return false because there's nothing to match with. Otherwise, pop the top element and see if it matches the current closing bracket.
5. After processing all characters, if the stack is empty, return true; else, return false.

Wait, no. Let me think again. When I see an opening bracket, I push the corresponding closing bracket onto the stack. For example, when I see '(', I push ')'. Then, when I encounter a closing bracket, I check if it's equal to the top of the stack. If yes, pop the stack. If not, it's unbalanced.

Yes, that makes sense. So for each opening bracket, I push the corresponding closing bracket. For each closing bracket, I check if it's the same as the top of the stack. If not, return false.

So, let's think about the data structures. I'll need a stack to keep track of the expected closing brackets. In Rust, I can use the Vec as a stack, using push and pop methods.

Now, let's think about the code structure.

The function is_balanced takes a &str. So, I'll loop through each character in input.chars().

For each char c in input:

- If c is one of '(', '[', '{', then I push the corresponding closing bracket to the stack. For example, if c is '(', push ')'.
- Else if c is one of ')', ']', '}', then I check if the stack is empty. If it is, return false. Otherwise, pop the top element and see if it matches c. If not, return false.
- Else, do nothing (ignore non-bracket characters).

After processing all characters, check if the stack is empty. If yes, return true; else, false.

Wait, but how do I map the opening brackets to their closing counterparts? Maybe create a helper function or a hash map. Alternatively, I can use a match statement.

Let me think about the code.

Initialize an empty stack: let mut stack = Vec::new();

For each c in input.chars():

match c {
    '(' => stack.push(')'),
    '[' => stack.push(']'),
    '{' => stack.push('}'),
    ')' | ']' | '}' => {
        if stack.is_empty() || stack.pop() != Some(c) {
            return false;
        }
    },
    _ => {}
}

After processing all characters, return stack.is_empty();

Yes, that seems correct.

Let me test this logic against the examples.

Example 1: is_balanced("") → true. The stack is empty, so returns true.

Example 2: "()[]{}" → each opening bracket is pushed, and each closing bracket matches and pops. Stack is empty at the end. True.

Example 3: "([{}])" → same as above. True.

Example 4: "(a + [b * c]) - {d}" → the brackets are balanced. The non-bracket characters are ignored. So, the function should return true.

Example 5: "(]" → the first character is '(', push ')'. Then ']' is encountered. Stack is not empty, pop gives ')', which is not equal to ']', so return false. Correct.

Example 6: "([)]" → Let's see:

- '(', push ')'
- '[', push ']'
- ')', now check stack: top is ']', which is not equal to ')', so return false. Correct.

Another test case: "(" → stack has ')', after processing, stack is not empty, returns false.

Test case: ")(" → first character is ')', stack is empty, return false.

What about nested brackets with other characters? Like "a(b)c[d]e{f}g" → should return true.

What about a string with only non-brackets? Like "abcde", returns true because stack is empty.

What about a string with unbalanced brackets in the middle, like "([])" → should be balanced. Wait, no: "([])" is balanced. Wait, no, the string is "([)]" which is unbalanced, but in the example, it's "([)]" which is handled correctly.

Wait, no. Let me think about the example "([)]". The processing would be:

- '(', push ')'
- '[', push ']'
- ')', now stack top is ']', which doesn't match ')', so return false. Correct.

So the logic seems solid.

Now, implement this in Rust.

The code would look like:

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

Wait, but in Rust, the match arms can be written more concisely. For example, for the closing brackets, we can have a single arm.

Testing this code against the examples should work.

Another thing to consider: what about uppercase brackets? But the problem statement says the brackets are (), [], {}, so I think the input will only have these, but the code is case-sensitive. So, the function correctly handles only these.

What about other bracket types, like <>? The problem says to ignore non-bracket characters, so they are skipped.

So, the code should handle all cases correctly.

I think this should solve the problem.