Balanced Parentheses Problem Using Stack in DSA Javascript - 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 - Stop

↓

Pop from stack

↓

Does popped match char?

↓

Unbalanced - Stop

↓

More chars?

Yes→Read next char

No↓

Stack empty?

Yes→Balanced

No↓

Unbalanced

The flow reads each character, pushes opening brackets, pops and matches closing brackets, and checks stack emptiness at the end.

Execution Sample

DSA Javascript

function isBalanced(s) {
  const stack = [];
  for (const char of s) {
    if ('({['.includes(char)) stack.push(char);
    else {
      if (stack.length === 0) return false;
      const top = stack.pop();
      if (!((top === '(' && char === ')') || (top === '{' && char === '}') || (top === '[' && char === ']'))) return false;
    }
  }
  return stack.length === 0;
}

Checks if a string of parentheses is balanced using a stack.

Execution Table

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

💡 All characters processed 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		(	{	}	)

Key Moments - 3 Insights

Why do we push only opening brackets onto the stack?

Because only opening brackets need to be matched later by closing brackets. See execution_table steps 1 and 2 where '(' and '{' are pushed.

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

It means there is no matching opening bracket, so the string is unbalanced. This is checked in step 3 before popping.

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

To ensure correct pairing of brackets. If they don't match, the string is unbalanced, as shown in step 3 where matching is verified.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the stack after popping and matching '}'?

A

B (

C ({

D {

💡 Hint

Check the 'Stack After' column at step 3 in execution_table.

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

A Step 4

B Step 3

C Step 2

D Step 1

💡 Hint

Look at the 'Stack After' column to see when the stack returns to empty.

If the input string started with a closing bracket ')', what would happen at step 1?

A Push ')' onto stack

B Pop from empty stack

C Return false immediately

D Ignore the character

💡 Hint

Refer to the concept_flow where encountering a closing bracket with empty stack leads to unbalanced.

Concept Snapshot

Balanced Parentheses Using Stack:
- Push opening brackets '(' '{' '[' onto stack.
- On closing brackets ')' '}' ']', pop and check match.
- If mismatch or pop on empty stack, unbalanced.
- At end, stack empty means balanced.
- Time: O(n), Space: O(n).

Full Transcript

This visualization shows how to check balanced parentheses using a stack. We read each character. If it's an opening bracket, we push it onto the stack. If it's a closing bracket, we pop from the stack and check if it matches. If the stack is empty when popping or the brackets don't match, the string is unbalanced. After processing all characters, if the stack is empty, the string is balanced. The execution table tracks each step, showing the stack before and after each operation and the current character. The variable tracker shows how the stack and current character change over time. Key moments clarify why we push only opening brackets, what happens if the stack is empty on closing bracket, and why matching is necessary. The quiz tests understanding of stack state and behavior at different steps.

Practice

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

easy

A. To sort the parentheses in order

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

C. To reverse the string of parentheses

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

Solution

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

   A stack helps store opening parentheses as they appear, so we can check if each closing parenthesis matches the last opened one.

2. Step 2: Explain why other options are incorrect

   Counting or reversing parentheses does not help check if they are balanced. Sorting changes order and breaks the original sequence.

3. Final Answer:

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

4. Quick Check:

   Stack tracks openings for matching [OK]

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

Common Mistakes:

• Thinking stack counts parentheses instead of matching
• Assuming reversing string solves balance
• Confusing sorting with balancing

2. Which of the following is the correct way to push an element onto a stack in JavaScript?

easy

A. stack.add(element);

B. stack.push(element);

C. stack.insert(element);

D. stack.append(element);

Solution

1. Step 1: Recall JavaScript array method for adding elements at the end

   JavaScript arrays use push() to add elements to the end, which simulates stack push.

2. Step 2: Identify incorrect methods

   add(), insert(), and append() are not valid JavaScript array methods.

3. Final Answer:

   stack.push(element); -> Option B

4. Quick Check:

   Use push() to add to stack [OK]

Hint: Use push() to add elements to stack in JavaScript [OK]

Common Mistakes:

• Using add() or append() which are not JavaScript array methods
• Confusing push() with pop()
• Trying to use insert() which doesn't exist

3. What will be the output of the following JavaScript code snippet?

function isBalanced(s) {
  const stack = [];
  for (const char of s) {
    if (char === '(') stack.push(char);
    else if (char === ')') {
      if (stack.length === 0) return false;
      stack.pop();
    }
  }
  return stack.length === 0;
}

console.log(isBalanced('(()())'));
console.log(isBalanced('(()'));
console.log(isBalanced(')('));

medium

A. true, true, false

B. false, true, false

C. true, false, false

D. false, false, true

Solution

1. Step 1: Trace the function for each input string

   For '(()())': all parentheses match, stack ends empty, returns true.
   For '(()': one '(' remains unmatched, returns false.
   For ')(': first char is ')', stack empty, returns false.

2. Step 2: Confirm outputs match true, false, false

   Outputs are true, false, false respectively.

3. Final Answer:

   true, false, false -> Option C

4. Quick Check:

   Stack empty at end means balanced [OK]

Hint: Stack empty at end means balanced parentheses [OK]

Common Mistakes:

• Assuming unmatched openings are balanced
• Ignoring early unmatched closing parentheses
• Confusing true/false outputs

4. The following code is intended to check balanced parentheses but has a bug. What is the bug?

function checkBalance(str) {
  const stack = [];
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') {
      stack.push('(');
    } else {
      if (stack.length === 0) return false;
      stack.pop();
    }
  }
  return true;
}

medium

A. It returns true even if stack is not empty after loop

B. It pushes closing parentheses instead of opening

C. It does not check for closing parentheses

D. It uses wrong loop syntax

Solution

1. Step 1: Analyze the return statement after loop

   The function returns true without checking if stack is empty, so leftover '(' are ignored.

2. Step 2: Explain why this causes incorrect results

   If there are unmatched '(' left in stack, string is unbalanced but function returns true incorrectly.

3. Final Answer:

   It returns true even if stack is not empty after loop -> Option A

4. Quick Check:

   Check stack.length === 0 before return true [OK]

Hint: Always check stack empty before returning true [OK]

Common Mistakes:

• Forgetting to check stack length after loop
• Returning true too early
• Ignoring unmatched opening parentheses

5. Given the string s = '{[()]}', which modification is needed in the stack-based balanced parentheses algorithm to correctly check this string?

hard

A. Add support for matching pairs of '()', '{}', and '[]' with stack push/pop logic

B. Ignore all characters except '(' and ')' during stack operations

C. Use two separate stacks for different types of brackets

D. Reverse the string before checking with the existing algorithm

Solution

1. Step 1: Understand the input string contains multiple bracket types

   The string has '()', '{}', and '[]' brackets, so the algorithm must handle all types.

2. Step 2: Explain how to handle multiple bracket types with one stack

   Push opening brackets onto stack, and on closing bracket, check if it matches the last opening bracket type before popping.

3. Final Answer:

   Add support for matching pairs of '()', '{}', and '[]' with stack push/pop logic -> Option A

4. Quick Check:

   One stack handles all bracket types [OK]

Hint: Match each closing bracket with last opening bracket type [OK]

Common Mistakes:

• Ignoring bracket types other than parentheses
• Using multiple stacks unnecessarily
• Reversing string instead of matching pairs