Validate Balanced Parentheses Using a Stack | Coding Problems: DSA

Q: What is the Balanced Parentheses problem?

Given a string containing only (), [], and {}, determine whether every opener has a matching closer in the correct nesting order. The LIFO discipline of a stack makes it the natural tool: brackets must close in the reverse order they opened. package com.bank.service; import java.util.ArrayDeque; imp

Q: How does the matching map work?

A Map<Character, Character maps each closer to its expected opener. When you see ), look up pairs.get(')') which gives (. Compare that to stack.pop(). If they match, continue. If not, the string is invalid. This avoids a chain of ifelse comparisons and is easy to extend. package com.bank.core; impor

Q: What are the edge cases?

Empty string is valid. Oddlength string is always invalid (quick O(1) check). Single bracket is invalid. Deeply nested and sequential combinations must both pass. package com.bank.core; public class ParenEdgeCases { public static void main(String[] args) { System.out.println("Empty: " + BalancedPare

Q: What are common mistakes?

Forgetting the final isEmpty() check wrongly accepts allopener strings. Not checking for an empty stack before popping throws NoSuchElementException. Not typechecking the match wrongly accepts crossed brackets like "({)}". package com.bank.core; public class ParenMistakes { public static void main(S

Definition

Push every opener, pop and type-match on every closer, and the string is valid only if the stack ends empty.

Balanced Parentheses – validate that every opening bracket has a matching closer of the same type in the correct nesting order.
Stack approach – push each opener; on each closer, pop the top and verify it matches the closer's type using a map.
Two failure paths – empty stack when a closer arrives (unmatched close), non-empty stack at the end (unmatched opens).
Complexity – O(n) time, O(n) space; each character is pushed and popped at most once.
Java practice – use ArrayDeque through Deque rather than the legacy Stack class.

Imagine a clerk at the National Bank of India stacking approval slips on a spike. Every time a nested approval opens, she spikes a slip of that color on top. When an approval closes, she can only remove the slip currently on top, and its color must match the one closing. If a red approval tries to close while a blue slip sits on top, the paperwork is out of order and the batch is rejected. At the end the spike must be empty.

Understanding the Concepts

What is the Balanced Parentheses problem?

Given a string containing only (), [], and {}, determine whether every opener has a matching closer in the correct nesting order. The LIFO discipline of a stack makes it the natural tool: brackets must close in the reverse order they opened.

JAVA

package com.bank.service;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class BalancedParentheses {
    private static final Map<Character, Character> PAIRS =
            Map.of(')', '(', ']', '[', '}', '{');

    public static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (PAIRS.containsValue(c)) {
                stack.push(c);
            } else if (PAIRS.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != PAIRS.get(c)) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValid("({[]})")); // true
        System.out.println(isValid("({[)]"));  // false
        System.out.println(isValid("((("));    // false
    }
}

TEXT

true
false
false

Why does this problem require a stack?

Brackets close in the reverse order they opened: last opened, first closed. This is exactly LIFO. A stack enforces that the most recently pushed element is the one you access next, which maps directly to the nesting rule.

JAVA

package com.bank.core;

import java.util.ArrayDeque;
import java.util.Deque;

public class NestingOrder {
    public static void main(String[] args) {
        // Open: { [ ( -> Stack: ( on top
        // Must close ( first, then [, then {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("{ opened"); stack.push("[ opened"); stack.push("( opened");

        System.out.println("Close order: " + stack.pop()); // ( first
        System.out.println("Close order: " + stack.pop()); // [ second
        System.out.println("Close order: " + stack.pop()); // { last
    }
}

TEXT

Close order: ( opened
Close order: [ opened
Close order: { opened

How does the matching map work?

A Map maps each closer to its expected opener. When you see ), look up pairs.get(')') which gives (. Compare that to stack.pop(). If they match, continue. If not, the string is invalid. This avoids a chain of if-else comparisons and is easy to extend.

JAVA

package com.bank.core;

import java.util.Map;

public class MatchingMap {
    public static void main(String[] args) {
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

        char closer = ')';
        char expected = pairs.get(closer);
        System.out.println("Closer: " + closer + " -> expected opener: " + expected);

        closer = '}';
        expected = pairs.get(closer);
        System.out.println("Closer: " + closer + " -> expected opener: " + expected);
    }
}

TEXT

Closer: ) -> expected opener: (
Closer: } -> expected opener: {

What are the two failure conditions?

First: a closer arrives when the stack is empty, meaning there is no opener to match. Second: after the scan, openers remain on the stack, meaning they were never closed. Both checks are essential for correctness.

JAVA

package com.bank.service;

public class TwoFailures {
    public static void main(String[] args) {
        System.out.println("')(' -> fails at index 0: stack empty on closer");
        System.out.println("'(((' -> scan finishes with 3 openers still on stack");
        System.out.println("'(]' -> fails at index 1: popped '(' does not match ']'");
        System.out.println("'()' -> both checks pass: valid");
    }
}

TEXT

')(' -> fails at index 0: stack empty on closer
'(((' -> scan finishes with 3 openers still on stack
'(]' -> fails at index 1: popped '(' does not match ']'
'()' -> both checks pass: valid

What are the edge cases?

Empty string is valid. Odd-length string is always invalid (quick O(1) check). Single bracket is invalid. Deeply nested and sequential combinations must both pass.

JAVA

package com.bank.core;

public class ParenEdgeCases {
    public static void main(String[] args) {
        System.out.println("Empty: " + BalancedParentheses.isValid(""));          // true
        System.out.println("Odd: " + BalancedParentheses.isValid("(()")); // false
        System.out.println("Deep: " + BalancedParentheses.isValid("(((())))")); // true
        System.out.println("Sequential: " + BalancedParentheses.isValid("()[]{}")); // true
    }
}

TEXT

Empty: true
Odd: false
Deep: true
Sequential: true

What are common mistakes?

Forgetting the final isEmpty() check wrongly accepts all-opener strings. Not checking for an empty stack before popping throws NoSuchElementException. Not type-checking the match wrongly accepts crossed brackets like "({)}".

JAVA

package com.bank.core;

public class ParenMistakes {
    public static void main(String[] args) {
        System.out.println("Bug 1: return true instead of stack.isEmpty()");
        System.out.println("  '(((' passes incorrectly");
        System.out.println("Bug 2: pop without empty check");
        System.out.println("  ')(' throws NoSuchElementException");
        System.out.println("Bug 3: pop without type check");
        System.out.println("  '({)}' passes incorrectly");
    }
}

TEXT

Bug 1: return true instead of stack.isEmpty()
  '(((' passes incorrectly
Bug 2: pop without empty check
  ')(' throws NoSuchElementException
Bug 3: pop without type check
  '({)}' passes incorrectly

How is this applied in banking?

At the National Bank of India, structured transaction messages use nested bracket segments. A validator checks the brackets before the real parser runs. Malformed messages with crossed or dangling brackets are rejected to a dead-letter path, protecting the parser from errors and giving the operations team a clean audit trail.

JAVA

package com.bank.service;

public class TransactionMessageValidator {
    public static void main(String[] args) {
        String good = "{header: [fields: (amount, currency)]}";
        String bad = "{header: [fields: (amount, currency]}";

        System.out.println("Good message: " + BalancedParentheses.isValid(
                good.replaceAll("[^()\\[\\]{}]", "")));
        System.out.println("Bad message: " + BalancedParentheses.isValid(
                bad.replaceAll("[^()\\[\\]{}]", "")));
    }
}

TEXT

Good message: true
Bad message: false

What should a senior engineer know?

This technique is the foundation of real parsing. The identical approach validates HTML/XML tags, nested expressions, and balanced quotes. The map-based matching is trivially extensible to new bracket types. In production, early rejection of malformed input at the bracket level protects downstream parsers from wasting resources on corrupt data.

JAVA

package com.bank.core;

public class SeniorParenNotes {
    public static void main(String[] args) {
        System.out.println("Extends to: HTML/XML tag matching, quote balancing");
        System.out.println("Map-based matching: add new bracket types with one entry");
        System.out.println("Production pattern: validate brackets before full parse");
        System.out.println("Prefer ArrayDeque over legacy Stack class");
    }
}

TEXT

Extends to: HTML/XML tag matching, quote balancing
Map-based matching: add new bracket types with one entry
Production pattern: validate brackets before full parse
Prefer ArrayDeque over legacy Stack class

Visual Overview

DIAGRAM

  Validation of "({[]})"
  ──────────────────────

  Char  Action              Stack
  ────  ──────────────────  ──────────
  (     push                [ ( ]
  {     push                [ {  ( ]
  [     push                [ [  {  ( ]
  ]     pop [ match ] ✓     [ {  ( ]
  }     pop { match } ✓     [ ( ]
  )     pop ( match ) ✓     [ ] empty

  Stack empty → VALID

DIAGRAM

  Failure on "({)}"
  ─────────────────
  (     push                [ ( ]
  {     push                [ {  ( ]
  )     pop { expect ( → MISMATCH ✗

  → INVALID

Key Takeaway

Balanced parentheses validation uses a stack because brackets must close in the reverse order they opened, which is LIFO. I scan the string once, push each opener, and on each closer I pop and verify the types match using a small map. The two failure conditions are an empty stack when a closer arrives and a non-empty stack after the full scan, and both are essential for correctness.

The algorithm runs in O(n) time with O(n) worst-case space. I use ArrayDeque through the Deque interface rather than the legacy Stack class, and I keep the matching in a Map from closer to expected opener, which makes the logic clean and easily extensible to new bracket types.

This technique is the gateway to real parsing. The identical stack discipline validates HTML/XML tags, nested expressions, and balanced quotes. In production, running a bracket check before the full parser rejects malformed input early, saving the parser from wasting resources on corrupt data.

In my project at the National Bank of India, I used this as a pre-check on structured transaction messages with nested bracket segments. Malformed messages are rejected to a dead-letter path before the real parser ever sees them, giving the operations team a clean audit trail of every rejected message.

Remember one sentence: push every opener, pop and type-match on every closer, and the string is valid only if the stack ends empty.

---