8.9 Validate Properly Nested Brackets

8.9.1 Metadata

8.9.2 Description

Given a string, check if all brackets (‘()’, ‘{}’, ‘[]’) are properly matched and nested. Return 1 if valid, otherwise return 0.

Example 1:

Input:

code_snippet = "if (a[0] > b[1]) { doSomething(); }"

Output:

1

Explanation: All brackets are properly matched: ‘(’ with ‘)’, ‘[’ with ’]’, and ‘{’ with ‘}’. No mismatches or improper nesting.

Example 2:

Input:

code_snippet = "int x = 42; // no brackets here"

Output:

1

Example 3:

Input:

code_snippet = "() {} []"

Output:

1

Constraints:

  • \(0 \le\) code_snippet.length \(\le 1000\)
  • code_snippet consists of printable ASCII characters (character codes 32 to 126 inclusive)
  • code_snippet may contain any combination of ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ’]’, letters, digits, symbols, and whitespace
  • code_snippet may be empty

8.9.3 Walkthrough

This is a classic bracket matching problem that uses a stack to track opening brackets and validate proper nesting.

Key Insight: For valid bracket sequences: 1. Every closing bracket must have a corresponding opening bracket before it 2. The most recent unmatched opening bracket must match the current closing bracket 3. All opening brackets must eventually be closed

Strategy: - Use a stack to store opening brackets as we encounter them - When we see a closing bracket, check if it matches the top of the stack - If the stack is empty when we see a closing bracket, or if brackets don’t match, return false - After processing all characters, the stack should be empty (all brackets matched)

Example trace for "if (a[0] > b[1]) { doSomething(); }":

  1. Skip characters until ( → Push ( onto stack: ['(']
  2. Skip until [ → Push [ onto stack: ['(', '[']
  3. Hit ] → Check top [ matches → Pop → Stack: ['(']
  4. Hit ) → Check top ( matches → Pop → Stack: []
  5. Skip until { → Push { onto stack: ['{']
  6. Skip until } → Check top { matches → Pop → Stack: []
  7. End of string, stack is empty → Valid!

8.9.4 Analysis

Time Complexity: \(O(n)\) where n is the length of the code snippet. We iterate through each character exactly once.

Space Complexity: \(O(n)\) in the worst case when all characters are opening brackets (e.g., "(((((("). The stack can grow up to the size of the input string.

8.9.5 Implementation Steps

  1. Handle edge case: Return true for empty strings (no brackets to validate)

  2. Initialize data structures:

    • Create a stack to store opening brackets
    • Create a map to pair opening brackets with their corresponding closing brackets

  3. Iterate through each character:

    • If it’s an opening bracket ((, {, [), push it onto the stack
    • If it’s a closing bracket:
      • Check if stack is empty → return false (no matching opening bracket)
      • Check if top of stack matches this closing bracket → if not, return false
      • Pop the matching opening bracket from the stack
    • Otherwise, skip non-bracket characters

  4. Final validation: After processing all characters, check if stack is empty

    • Empty stack → all brackets matched → return true
    • Non-empty stack → unmatched opening brackets remain → return false

8.9.6 Java Code

class Result {

    /*
     * Complete the 'areBracketsProperlyMatched' function below.
     *
     * The function is expected to return a BOOLEAN.
     * The function accepts STRING code_snippet as parameter.
     */
     
     private static Map<Character, Character> bracketMap = new HashMap<>(); 

    public static boolean areBracketsProperlyMatched(String code_snippet) {
        if(code_snippet.isEmpty()) {
            return true;
        }
        
        // Write your code here
        Stack<Character> openParenStack = new Stack<>();
        bracketMap.put('{', '}');
        bracketMap.put('(', ')');
        bracketMap.put('[', ']');
        
        for(char c : code_snippet.toCharArray()) {
            //System.out.println(c);
            if(isOpenParenthesis(c)) {
                openParenStack.add(c);
            } else if(isCloseParenthesis(c)) {
                if(openParenStack.isEmpty()) {
                    return false;
                }
                char expected = bracketMap.get(openParenStack.peek());
                //System.out.println("expected " + expected + " vs actual " + c );
                if(expected != c) {
                    return false;
                }
                //pop the top open parentheiss
                openParenStack.pop();
            } else {
                //skip
            }
        }
        
        // if there are still open parenthesis left in the stack
        if(!openParenStack.isEmpty()) {
            return false;
        }
        
        return true;
    }
    
    private static boolean isOpenParenthesis(char c) {
        return bracketMap.keySet().contains(c);
    }
    
    private static boolean isCloseParenthesis(char c) {
        return bracketMap.values().contains(c);
    }

}