Indices of matching parentheses in Python

Question

Is there a way to get indices of matching parentheses in a string? For example for this one:

text = 'aaaa(bb()()ccc)dd'

I'd like to get a dictionary with values:

result = {4:14, 7:8, 9:10}

which means that parentheses on index 4 and 14 are matching , 7 and 8 an so on. Thanks a lot.

Answer 1

You mean an automated way? I don't think so.

You need to create a program using a stack, in which you push the index when you find an open parenthesis, and pop it when you find a closing parenthesis.

In Python, you can easily use a list as a stack, since they have the append() and pop() methods.

def find_parens(s):
    toret = {}
    pstack = []

    for i, c in enumerate(s):
        if c == '(':
            pstack.append(i)
        elif c == ')':
            if len(pstack) == 0:
                raise IndexError("No matching closing parens at: " + str(i))
            toret[pstack.pop()] = i

    if len(pstack) > 0:
        raise IndexError("No matching opening parens at: " + str(pstack.pop()))

    return toret

Hope this helps.

Answer 2

The standard way to check for balanced brackets is to use a stack. In Python, this can be done by appending to and popping from a standard list:

text = 'aaaa(bb()()ccc)dd'
istart = []  # stack of indices of opening parentheses
d = {}

for i, c in enumerate(text):
    if c == '(':
         istart.append(i)
    if c == ')':
        try:
            d[istart.pop()] = i
        except IndexError:
            print('Too many closing parentheses')
if istart:  # check if stack is empty afterwards
    print('Too many opening parentheses')
print(d)

Result:

In [58]: d
Out[58]: {4: 14, 7: 8, 9: 10}