Balanced Parentheses Problem Using Stack in DSA Rust - Execution Trace

Concept Flow - Balanced Parentheses Problem Using Stack

Start

↓

Read next char

↓

Is char '(' or '{' or '['?

Yes→Push to stack

↓

Is char ')' or '}' or '

↓

Stack empty?

Yes→Unbalanced

↓

Pop from stack

↓

Does popped match char?

↓

Unbalanced

↓

More chars?

Yes→Read next char

No↓

Stack empty?

Yes→Balanced

No↓

Unbalanced

The flow reads each character, pushes opening brackets onto the stack, pops and checks matching for closing brackets, and finally checks if stack is empty to decide balance.

Execution Sample

DSA Rust

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

Checks if parentheses in string s are balanced using a stack.

Execution Table

Step	Operation	Current Char	Stack Before	Stack After	Action	Visual State
1	Read char	(		(	Push '('	( ) -> null
2	Read char	[	(	(, [	Push '['	( -> [ ] -> null
3	Read char	]	(, [	(	Pop '[' and match with ']'	( -> null
4	Read char	)	(		Pop '(' and match with ')'	null
5	End of string	N/A			Stack empty, balanced	null

💡 End of string reached and stack is empty, so parentheses are balanced.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
stack		(	(, [	(
current_char	N/A	(	[	]	)	N/A

Key Moments - 3 Insights

Why do we push only opening brackets onto the stack?

Because opening brackets mark places where we expect matching closing brackets later. This is shown in execution_table rows 1 and 2 where '(' and '[' are pushed.

What happens if we find a closing bracket but the stack is empty?

It means there is no matching opening bracket, so the string is unbalanced. This would be caught in the step where we try to pop but stack is empty (not shown in this example but explained in concept_flow).

Why do we check if the popped bracket matches the current closing bracket?

To ensure correct pairing. For example, '(' matches ')', '[' matches ']', etc. If they don't match, the string is unbalanced. This is shown in execution_table rows 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the stack after reading the second character?

A ['(']

B ['(', '[']

C []

D ['[']

💡 Hint

Check the 'Stack After' column at Step 2 in execution_table.

At which step does the stack become empty again after pushing elements?

A Step 4

B Step 2

C Step 3

D Step 1

💡 Hint

Look at 'Stack After' column in execution_table rows 3 and 4.

If the input string was "([)]", what would happen at Step 3?

A Push ')' onto stack

B Pop '(' and match with ']', which succeeds

C Pop '[' and match with ')', which fails

D Stack becomes empty

💡 Hint

Refer to concept_flow and key_moments about matching pairs and stack operations.

Concept Snapshot

Balanced Parentheses Using Stack:
- Push opening brackets onto stack
- For closing brackets, pop and check match
- If mismatch or empty stack on pop, unbalanced
- At end, stack empty means balanced
- Works for (), {}, [] pairs

Full Transcript

This concept uses a stack to check if parentheses in a string are balanced. We read each character: if it's an opening bracket like '(' or '[', we push it onto the stack. If it's a closing bracket like ')' or ']', we pop from the stack and check if it matches the correct opening bracket. If it doesn't match or the stack is empty when popping, the string is unbalanced. After processing all characters, if the stack is empty, the parentheses are balanced. The execution table shows step-by-step how the stack changes with each character read, and key moments clarify common confusions about pushing, popping, and matching brackets.

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