Matching Brackets

Not Started

Validate that brackets are properly nested and matched using a stack. Push opening brackets, pop and compare when you see closers. If the stack is empty at the end, everything matched correctly.

When to Use

Bracket validation: Check if parentheses, braces, and square brackets are balanced and properly nested

Expression parsing: Validate mathematical expressions or code syntax with nested delimiters

HTML/XML tag matching: Ensure opening and closing tags are properly paired

Nested structure validation: Any problem involving matching pairs that can be nested

Basic Bracket Matching

def is_valid(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    
    for ch in s:
        if ch in pairs:  # closing bracket
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)  # opening bracket
    
    return len(stack) == 0  # empty = all matched

bool isValid(string s) {
    vector<char> st;
    unordered_map<char,char> pairs = {
        {')','('}, {'}','{'}, {']','['}};
    
    for (char ch : s) {
        if (pairs.count(ch)) {  // closing bracket
            if (st.empty() || st.back() != pairs[ch])
                return false;
            st.pop_back();
        } else {
            st.push_back(ch);  // opening bracket
        }
    }
    return st.empty();  // empty = all matched
}

bool IsValid(string s) {
    var st = new Stack<char>();
    var pairs = new Dictionary<char,char> {
        {')','('}, {'}','{'}, {']','['}};
    
    foreach (char ch in s) {
        if (pairs.ContainsKey(ch)) {  // closing bracket
            if (st.Count == 0 || st.Peek() != pairs[ch])
                return false;
            st.Pop();
        } else {
            st.Push(ch);  // opening bracket
        }
    }
    return st.Count == 0;  // empty = all matched
}

boolean isValid(String s) {
    Stack<Character> st = new Stack<>();
    Map<Character,Character> pairs = Map.of(
        ')','(', '}','{', ']','[');
    
    for (char ch : s.toCharArray()) {
        if (pairs.containsKey(ch)) {  // closing bracket
            if (st.isEmpty() || st.peek() != pairs.get(ch))
                return false;
            st.pop();
        } else {
            st.push(ch);  // opening bracket
        }
    }
    return st.isEmpty();  // empty = all matched
}

The Pattern

Step 1: Create a map of closing -> opening bracket pairs

Step 2: For each character: if it's a closer, check if stack top matches the expected opener

Step 3: If it's an opener, push it onto the stack

Step 4: At the end, the stack should be empty (all openers were matched)