Balanced Parentheses Problem Using Stack in DSA Rust

Mental Model

We use a stack to keep track of opening brackets and check if each closing bracket matches the last opened one.

Analogy: Imagine stacking plates: you put plates on top when you see an opening bracket, and you remove the top plate when you see a matching closing bracket. If you try to remove a plate that doesn't match or the stack is empty, the order is wrong.

Stack (top at right): []
Expression: ( [ { } ] )

Initial:
Stack: []
Expression pointer: ↑ at '('

Dry Run Walkthrough

Input: expression: "({[]})"

Goal: Check if all parentheses are balanced and correctly nested

Step 1: Push '(' onto stack

Stack: ['(']
Expression pointer: ↑ at '{'

Why: We store opening brackets to match later with closing ones

Step 2: Push '{' onto stack

Stack: ['(', '{']
Expression pointer: ↑ at '['

Why: Keep track of nested opening brackets

Step 3: Push '[' onto stack

Stack: ['(', '{', '[']
Expression pointer: ↑ at ']'

Why: Add another opening bracket to stack

Step 4: Pop '[' from stack because current char is ']' and matches '['

Stack: ['(', '{']
Expression pointer: ↑ at '}'

Why: Closing bracket matches last opening bracket, so remove it

Step 5: Pop '{' from stack because current char is '}' and matches '{'

Stack: ['(']
Expression pointer: ↑ at ')'

Why: Match closing bracket with last opening bracket

Step 6: Pop '(' from stack because current char is ')' and matches '('

Stack: []
Expression pointer: end

Why: All brackets matched and stack is empty

Result:

Stack: []
Expression fully processed
Result: Balanced parentheses

Annotated Code

DSA Rust

use std::collections::VecDeque;

fn is_balanced(expression: &str) -> bool {
    let mut stack: VecDeque<char> = VecDeque::new();
    for ch in expression.chars() {
        if ch == '(' || ch == '{' || ch == '[' {
            stack.push_back(ch); // push opening bracket
        } else if ch == ')' || ch == '}' || ch == ']' {
            if let Some(top) = stack.pop_back() {
                if !matches!((top, ch), ('(', ')') | ('{', '}') | ('[', ']')) {
                    return false; // mismatch found
                }
            } else {
                return false; // closing bracket with empty stack
            }
        }
    }
    stack.is_empty() // true if all matched
}

fn main() {
    let expression = "({[]})";
    if is_balanced(expression) {
        println!("Balanced parentheses");
    } else {
        println!("Not balanced parentheses");
    }
}

stack.push_back(ch); // push opening bracket

Add opening bracket to stack to track it

if let Some(top) = stack.pop_back() {

Remove last opening bracket to match with current closing bracket

if !matches!((top, ch), ('(', ')') | ('{', '}') | ('[', ']')) {

Check if popped opening bracket matches current closing bracket

return false; // closing bracket with empty stack

If stack empty but closing bracket found, parentheses not balanced

stack.is_empty() // true if all matched

If stack empty after processing, all parentheses matched

Output

Balanced parentheses

Complexity Analysis

Time: O(n) because we scan each character once

Space: O(n) in worst case if all characters are opening brackets stored in stack

vs Alternative: Using a stack is more efficient than repeatedly scanning the string for pairs, which can be O(n^2)

Edge Cases

Empty string

Returns true because no parentheses means balanced

DSA Rust

stack.is_empty() // true if all matched

String with only opening brackets like "((("

Returns false because stack not empty at end

DSA Rust

stack.is_empty() // true if all matched

String with closing bracket first like ")("

Returns false because stack empty when closing bracket found

DSA Rust

return false; // closing bracket with empty stack

When to Use This Pattern

When you see a problem asking if brackets or parentheses are properly matched and nested, use a stack to track opening brackets and match them with closing ones.

Common Mistakes

Mistake: Not checking if stack is empty before popping on a closing bracket
Fix: Add a condition to return false if stack is empty when a closing bracket appears

Mistake: Matching brackets by comparing characters directly without checking pairs
Fix: Use a matching condition that pairs each opening bracket with its correct closing bracket

Summary

Checks if parentheses and brackets in a string are balanced using a stack.

Use when you need to verify correct nesting and matching of brackets.

The key is to push opening brackets and pop them only if the closing bracket matches the last opened one.

Practice

1. What is the main purpose of using a stack in the Balanced Parentheses Problem?

easy

A. To keep track of opening parentheses and match them with closing ones

B. To count the total number of parentheses in the string

C. To reverse the order of parentheses in the string

D. To sort the parentheses alphabetically

Solution

1. Step 1: Understand the role of stack in parentheses matching

   A stack stores opening parentheses as they appear to check if each closing parenthesis matches the last opened one.

2. Step 2: Explain why other options are incorrect

   Counting, reversing, or sorting parentheses does not help in checking if they are balanced.

3. Final Answer:

   To keep track of opening parentheses and match them with closing ones -> Option A

4. Quick Check:

   Stack tracks openings for matching = B [OK]

Hint: Stack stores openings to match closings quickly [OK]

Common Mistakes:

• Thinking stack counts parentheses instead of matching
• Confusing stack with queue for this problem
• Assuming stack sorts parentheses

2. Which of the following Rust code snippets correctly pushes an opening parenthesis '(' onto a stack named stack?

easy

A. stack.insert('(');

B. stack.push('(');

C. stack.add('(');

D. stack.append('(');

Solution

1. Step 1: Recall Rust Vec method to add elements

   In Rust, Vec uses push() to add elements at the end.

2. Step 2: Verify other methods are invalid for Vec

   add(), insert() require different parameters or do not exist; append() merges vectors, not single elements.

3. Final Answer:

   stack.push('('); -> Option B

4. Quick Check:

   Vec push method = push() [OK]

Hint: Use push() to add items to Rust Vec stack [OK]

Common Mistakes:

• Using append() to add single element
• Confusing insert() with push()
• Using add() which is not a Vec method

3. What will be the output of the following Rust code snippet that checks if parentheses are balanced?

fn is_balanced(s: &str) -> bool {
    let mut stack = Vec::new();
    for ch in s.chars() {
        if ch == '(' {
            stack.push(ch);
        } else if ch == ')' {
            if stack.pop().is_none() {
                return false;
            }
        }
    }
    stack.is_empty()
}

fn main() {
    println!("{}", is_balanced("(()())"));
}

medium

A. false

B. Runtime panic

C. Compilation error

D. true

Solution

1. Step 1: Trace the input string "(()())" character by character

   Process '(', push ['(']; '(', push ['(','(']; ')', pop ['(']; '(', push ['(','(']; ')', pop ['(']; ')', pop []. All match.

2. Step 2: Check final stack state

   Stack is NOT empty after processing all 6 characters because the input string "(()())" has 6 characters but the last character is ')', so the stack ends empty. Wait, let's count carefully:
   Characters: '(' push ['(']
   '(' push ['(','(']
   ')' pop ['(']
   '(' push ['(','(']
   ')' pop ['(']
   ')' pop []
   Stack is empty after processing all characters, so stack.is_empty() returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Matched pairs and empty stack = true [OK]

Hint: Count openings and closings; unmatched means false [OK]

Common Mistakes:

• Mis-counting the number of parentheses
• Ignoring stack emptiness at end
• Confusing pop() returning None with Some

4. Identify the bug in this Rust function that checks balanced parentheses:

fn check_balance(s: &str) -> bool {
    let mut stack = Vec::new();
    for ch in s.chars() {
        if ch == '(' {
            stack.push(ch);
        } else if ch == ')' {
            stack.pop();
        }
    }
    stack.is_empty()
}

medium

A. It uses a wrong data structure instead of Vec

B. It pushes closing parentheses instead of opening

C. It does not check if pop() returns None before popping

D. It returns true even if stack is not empty

Solution

1. Step 1: Analyze pop() usage on empty stack

   The function calls stack.pop() without checking if stack is empty, so popping from empty stack returns None but is ignored.

2. Step 2: Explain consequence of missing check

   This causes false positives when closing parentheses appear without matching openings, as function never returns false early.

3. Final Answer:

   It does not check if pop() returns None before popping -> Option C

4. Quick Check:

   Missing pop() None check causes errors [OK]

Hint: Always check pop() result before proceeding [OK]

Common Mistakes:

• Ignoring pop() returning None on empty stack
• Pushing wrong characters
• Assuming stack emptiness check is enough

5. Given the Rust function below, what will be the output when checking the string "{[(())]}"? The function supports '()', '[]', and '{}' pairs.

fn is_balanced(s: &str) -> bool {
    let mut stack = Vec::new();
    for ch in s.chars() {
        if ch == '(' || ch == '[' || ch == '{' {
            stack.push(ch);
        } else {
            if let Some(top) = stack.pop() {
                if (ch == ')' && top != '(') ||
                   (ch == ']' && top != '[') ||
                   (ch == '}' && top != '{') {
                    return false;
                }
            } else {
                return false;
            }
        }
    }
    stack.is_empty()
}

fn main() {
    println!("{}", is_balanced("{[(())]}"));
}

hard

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Trace the string "{[(())]}" step-by-step

   Push '{', '[', '(', '('. Then pop for ')', ')', ']', '}'. Each closing matches the last opening correctly.

2. Step 2: Check stack emptiness after processing

   All pairs matched, stack is empty, so function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   All pairs matched and stack empty = true [OK]

Hint: Match each closing with last opening in stack [OK]

Common Mistakes:

• Not handling multiple bracket types
• Ignoring order of matching pairs
• Forgetting to check stack empty at end