Check if a given string has its open brackets closed by the same type of brackets?

[noahverner1995]

I hope not to sound very weird here, basically, suppose that you have the following strings:

    s1 = '{[]}'

    s2 = '[(])'

    s3 = '()[]{}'

And you want to build a program/function that verifies that such strings are 'valid' if:

> **Open brackets are closed by the same type of brackets**

So the output for the cases above would be:

    theFunction(s1)

> **valid**

    theFunction(s2)

> **NOT valid**

    theFunction(s3)

> **valid**

I was thinking of building it like this:

    def theFunction(s):
       the_dic = {'(':')',
                  '[':']',
                  '{':'}',
                  }

       if any(s.startswith(ch) for ch in the_dic.keys()):
          for char in s:
             #...?
             result = 'valid'
       else: 
          result = 'NOT valid'

       return result

However, I'm not good enough at advanced nested-looping, may I get some help please?

[deanhystad]

If I did this by hand I would start at the left and scan right through the string. When encountering an opening bracket I would write it down on a scratch pad. When encountering a closing bracket I would look at the last opening bracket, verify the closing bracket matches the last opening bracket, and if it matched, erase the last opening bracket. The string is invalid if there is ever a mismatched closing bracket or if there are any opening brackets remaining on the scratch pad at the end of the string.

There is no need for nested loops.