## Nested Brackets

It’s the final year of my degree, so I’m doing a few job interviews at the moment. And I’ve run in to the following problem a few times:

Given an input string

Determine if can be generated in the grammar:

S

S {S} S

S [S] S

S (S) S

In other words, we want to recognise any sequence of brackets that might be used to represent a branching structure like a tree.

So we know that strings like `{}()[]`

and `([])[({})]`

are valid.

But strings like `{]`

and `{(})`

are invalid.

How do we recognise these valid strings?

If you look up this question in Google, the solutions you’ll find will (almost) all use a **stack** to record the last seen opening bracket as we scan from left to right along the string.

Now that makes sense, given that the above is a context free grammar, which can be recognised with a push-down automaton.
Push-down automata are like their less powerful cousins finite-state automata, but crucially they can employ a **stack** to push and pop from.

But with modern programming languages, we’re provided with so many string processing tools for free that we don’t need to explicitly allocate a stack, at least not for the purposes of our problem.

# Towards a more elegant solution

What if, instead, we looked at our string and removed the sequences `{}`

, `[]`

, and `()`

until the string is empty or no more can be removed?

So, after one pass this valid string: `([])[({})]`

will be transformed to: `{}()[()]`

and after another pass: `()`

until after one last pass we’re left with the empty string .

But applying the same process to the invalid string: `{(})`

will yield the same string again.

You can think of the above as repeatedly removing the leaves of a tree represented by our string, after each pass, our tree gets smaller until it can shrink no more: in which case it’s empty - or it’s not a tree :(

So in python, our method might look like this:

```
def brackets(s):
brackets = ["{}", "()", "[]"]
oldString = s
for br in brackets:
s = s.replace(br, "")
if len(s) == 0:
return True
else:
if oldString == s:
return False
else:
return brackets(s)
```

Now this recursive solution is OK, but now we’re using another stack implicitly: the call stack. ugh.

We actually don’t need this recursive feature if we update some bits of state ourselves:

```
def bracketsIter(s):
brackets = ["{}", "()", "[]"]
oldString = ""
while(oldString != s):
oldString = s
for br in brackets:
s = s.replace(br, "")
if len(s) == 0:
return True
return False
```

So this new iterative approach will terminate, returning `False`

, if our string can’t be reduced further. Or returning `True`

if our string is ever empty.

Now this algorithm has a worse asymptotic time complexity than the standard approach with a stack.

But it can run in place on the string, whereas the method with a stack required O(n) space.