Balanced Parentheses Problem Using Stack in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced Parentheses Check for Simple Input

What is the output of this Rust code that checks if parentheses are balanced in the string "()[]{}"?

DSA Rust

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

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

A true

B false

C Compilation error

D Runtime panic

💡 Hint

Think about whether all opening brackets have matching closing brackets in the correct order.

The input string "()[]{}" has all types of brackets properly opened and closed in order. The stack pushes opening brackets and pops them when matching closing brackets appear. Since the stack is empty at the end, the function returns true.

❓ Predict Output

intermediate

Output for Unbalanced Parentheses Input

What is the output of this Rust code when checking the string "([)]" for balanced parentheses?

DSA Rust

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

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

A false

B Runtime panic

C Compilation error

D true

💡 Hint

Check if the closing brackets match the most recent opening bracket.

The input "([)]" is not balanced because the closing bracket ')' does not match the last opening bracket '['. The function returns false when this mismatch is detected.

🔧 Debug

advanced

Identify the Error in Parentheses Checking Code

What error will this Rust code produce when checking the string "(()" for balanced parentheses?

DSA Rust

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

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

A true

B Compilation error

C Runtime panic due to popping from empty stack

D false

💡 Hint

Consider what happens if there are leftover opening brackets after processing the string.

The input "(()" has one extra opening bracket without a matching closing bracket. The stack will not be empty at the end, so the function returns false. No panic occurs because pop is only called when a closing bracket is found.

🧠 Conceptual

advanced

Why Use a Stack for Balanced Parentheses?

Why is a stack the best data structure to check for balanced parentheses in a string?

A Because a stack automatically counts the number of brackets without storing them.

B Because a stack allows checking the most recent opening bracket first, matching the last-in, first-out order needed.

C Because a stack can reverse the string to check parentheses from the end.

D Because a stack stores all characters and sorts them alphabetically.

💡 Hint

Think about how parentheses must close in the reverse order they open.

A stack follows last-in, first-out order, which matches how parentheses must be closed in reverse order of opening. This makes it ideal for checking balanced parentheses.

🚀 Application

expert

Result of Checking Complex Nested Parentheses

What is the output of this Rust code checking the string "{[()()]()}" for balanced parentheses?

DSA Rust

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

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

A Runtime panic

B false

C true

D Compilation error

💡 Hint

Check carefully the nesting and matching of all brackets in the string.

The string "{[()()]()}" is properly nested with all opening brackets matched by the correct closing brackets in order. The stack ends empty, so the function returns true.

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