Bracket Matching

Problem:
https://open.kattis.com/problems/bracketmatching

This problem asks you to determine whether a string of brackets is valid.
A string is valid if:

• Every opening bracket has a matching closing bracket
• Brackets are properly nested
• No unmatched closing bracket appears
• No leftover unmatched opening brackets remain

This is a classic stack problem.

💡 Approach

We use:

• A stack to store opening brackets
• A dictionary mapping opening → closing
• A loop over the string to validate the structure
• Three invalid scenarios:
  1. Closing bracket appears but stack is empty
  2. Closing bracket does not match the most recent opening bracket
  3. After processing all characters, the stack is not empty

Time complexity: O(n)
Space complexity: O(n) (worst case, all openings)

# 2.1 Bracket Matching
# stack-based validation

import sys
sys.stdin = open('test.txt', 'r')

n = int(sys.stdin.readline())
# without strip, '\n' is treated as a character
s = sys.stdin.readline().strip()

# list of open brackets
o = ['(', '[', '{']

# dictionary mapping open to close brackets
d = {
    '(': ')',
    '[': ']',
    '{': '}'
}

# stack for open brackets
stack = []
v = 'Valid'

for c in s:
    # if open bracket, push to stack
    if c in o:
        stack.append(c)
    else:
        # if closing bracket, ensure stack is not empty
        if stack:
            x = stack.pop()
            # mismatch?
            if d[x] != c:
                v = 'Invalid'
                break
        else:
            v = 'Invalid'
            break

# leftover opening brackets = invalid
if stack:
    v = 'Invalid'

print(v)