Let's say:

• '(', '{', '[' are called "openers."
• ')', '}', ']' are called "closers."

Write an efficient function that tells us whether or not an input string's openers and closers are properly nested.

Examples:

• "{ [ ] ( ) }" should return True
• "{ [ ( ] ) }" should return False
• "{ [ }" should return False

### Solution

We iterate through our string, making sure that:

1. each closer corresponds to the most recently seen, unclosed opener
2. every opener and closer is in a pair

We use a stack to keep track of the most recently seen, unclosed opener. And if the stack is ever empty when we come to a closer, we know that closer doesn't have an opener.

So as we iterate:

• If we see an opener, we push it onto the stack.
• If we see a closer, we check to see if it is the closer for the opener at the top of the stack. If it is, we pop from the stack. If it isn't, or if the stack is empty, we return False.

If we finish iterating and our stack is empty, we know every opener was properly closed.

BrackedValidator
``````def is_valid(code):
openers_to_closers = {
'(' : ')',
'{' : '}',
'[' : ']',
}
openers = set(openers_to_closers.keys())
closers = set(openers_to_closers.values())

openers_stack = []
for char in code:
if char in openers:
openers_stack.append(char)
elif char in closers:
if not openers_stack:
return False
else:
last_unclosed_opener = openers_stack.pop()
# If this closer doesn't correspond to the most recently
# seen unclosed opener, short-circuit, returning False
if not openers_to_closers[last_unclosed_opener] == char:
return False

return openers_stack == []

print(is_valid("{[()]})"))``````
BracketValidator with C#
``````using System.Collections.Generic;

public static bool IsValid(String code)
{
var openersToClosers = new Dictionary<char, char>
{
{ '(', ')' },
{ '[', ']' },
{ '{', '}' }
};

var openers = new HashSet<char>(openersToClosers.Keys);
var closers = new HashSet<char>(openersToClosers.Values);

foreach (char c in code)
{
if (openers.Contains(c))
{
}
else if (closers.Contains(c))
{
{
return false;
}
else
{

// If this closer doesn't correspond to the most recently
// seen unclosed opener, short-circuit, returning false
if (openersToClosers[lastUnclosedOpener] != c)
{
return false;
}
}
}
}
$O(n)$
$O(n)$