Balanced Parentheses Problem Using Stack in DSA Javascript

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 a plate on top for each opening bracket, and when you see a closing bracket, you remove the top plate to see if it matches.

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

Initial stack is empty: []
We push opening brackets and pop when matching closing bracket appears.

Dry Run Walkthrough

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

Goal: Check if the parentheses in the expression are balanced and correctly nested.

Step 1: Read '(' and push it onto the stack

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

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

Step 2: Read '{' and push it onto the stack

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

Why: Keep track of nested opening brackets

Step 3: Read '[' and push it onto the stack

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

Why: Add another opening bracket to stack

Step 4: Read ']' and check top of stack: '[' matches, so pop it

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

Why: Closing bracket matches last opening, so remove it

Step 5: Read '}' and check top of stack: '{' matches, so pop it

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

Why: Match and remove the last opening bracket

Step 6: Read ')' and check top of stack: '(' matches, so pop it

Stack: []
Expression pointer at end

Why: All brackets matched and stack is empty

Result:

Stack: []
Expression fully processed
Answer: Balanced

Annotated Code

DSA Javascript

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) return null;
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) return null;
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

function isBalanced(expression) {
  const stack = new Stack();
  const pairs = {
    ')': '(',
    ']': '[',
    '}': '{'
  };

  for (const char of expression) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char); // push opening bracket
    } else if (char === ')' || char === ']' || char === '}') {
      if (stack.isEmpty()) return false; // no opening bracket to match
      const top = stack.pop(); // pop last opening bracket
      if (top !== pairs[char]) return false; // mismatch found
    }
  }

  return stack.isEmpty(); // true if all matched
}

// Driver code
const expr = "({[]})";
if (isBalanced(expr)) {
  console.log("Balanced");
} else {
  console.log("Not Balanced");
}

stack.push(char); // push opening bracket

Add opening bracket to stack to track it

if (stack.isEmpty()) return false; // no opening bracket to match

If closing bracket found but stack empty, expression is unbalanced

const top = stack.pop(); // pop last opening bracket

Remove last opening bracket to check match

if (top !== pairs[char]) return false; // mismatch found

If popped bracket does not match closing bracket, unbalanced

return stack.isEmpty(); // true if all matched

If stack empty at end, all brackets matched

Output

Balanced

Complexity Analysis

Time: O(n) because we scan the expression once, pushing and popping at most once per character

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

vs Alternative: Compared to counting brackets without stack, this method correctly handles nested and mixed types with linear time and space

Edge Cases

Empty string

Returns true because no brackets means balanced

DSA Javascript

return stack.isEmpty(); // true if all matched

String with only opening brackets

Returns false because stack is not empty at end

DSA Javascript

return stack.isEmpty(); // true if all matched

String with closing bracket but no opening

Returns false immediately when trying to pop from empty stack

DSA Javascript

if (stack.isEmpty()) return false; // no opening bracket to match

When to Use This Pattern

When you see a problem asking if brackets or symbols are properly opened and closed in order, use the stack pattern to track openings and verify closings.

Common Mistakes

Mistake: Not checking if stack is empty before popping, causing errors on unmatched closing brackets
Fix: Always check stack.isEmpty() before popping to avoid errors

Mistake: Only counting brackets without checking order or type, leading to false positives
Fix: Use stack to ensure correct nesting and matching types

Summary

Checks if every opening bracket has a matching closing bracket in the correct order.

Use when you need to verify balanced and properly nested parentheses or brackets.

The key insight is to push opening brackets and pop them when matching closing brackets appear, ensuring order and type correctness.

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