parsing nested parentheses in python, grab content

Question

Apparently this problem comes up fairly often, after reading

Regular expression to detect semi-colon terminated C++ for & while loops

and thinking about the problem for a while, i wrote a function to return the content contained inside an arbitrary number of nested ()

The function could easily be extended to any regular expression object, posting here for your thoughts and considerations.

any refactoring advice would be appreciated

(note, i'm new to python still, and didn't feel like figuring out how to raise exceptions or whatever, so i just had the function return 'fail' if it couldin't figure out what was going on)

Edited function to take into account comments:

def ParseNestedParen(string, level):
    """
    Return string contained in nested (), indexing i = level
    """
    CountLeft = len(re.findall("\(", string))
    CountRight = len(re.findall("\)", string))
    if CountLeft == CountRight:
        LeftRightIndex = [x for x in zip(
        [Left.start()+1 for Left in re.finditer('\(', string)], 
        reversed([Right.start() for Right in re.finditer('\)', string)]))]

    elif CountLeft > CountRight:
        return ParseNestedParen(string + ')', level)

    elif CountLeft < CountRight:
        return ParseNestedParen('(' + string, level)

    return string[LeftRightIndex[level][0]:LeftRightIndex[level][1]]

Answer 1

You don't make it clear exactly what the specification of your function is, but this behaviour seems wrong to me:

>>> ParseNestedParen('(a)(b)(c)', 0)
['a)(b)(c']
>>> nested_paren.ParseNestedParen('(a)(b)(c)', 1)
['b']
>>> nested_paren.ParseNestedParen('(a)(b)(c)', 2)
['']

Other comments on your code:

• Docstring says "generate", but function returns a list, not a generator.
• Since only one string is ever returned, why return it in a list?
• Under what circumstances can the function return the string fail?
• Repeatedly calling re.findall and then throwing away the result is wasteful.
• You attempt to rebalance the parentheses in the string, but you do so only one parenthesis at a time:

>>> ParseNestedParen(')' * 1000, 1)
RuntimeError: maximum recursion depth exceeded while calling a Python object

As Thomi said in the question you linked to, "regular expressions really are the wrong tool for the job!"

---

The usual way to parse nested expressions is to use a stack, along these lines:

def parenthetic_contents(string):
    """Generate parenthesized contents in string as pairs (level, contents)."""
    stack = []
    for i, c in enumerate(string):
        if c == '(':
            stack.append(i)
        elif c == ')' and stack:
            start = stack.pop()
            yield (len(stack), string[start + 1: i])

>>> list(parenthetic_contents('(a(b(c)(d)e)(f)g)'))
[(2, 'c'), (2, 'd'), (1, 'b(c)(d)e'), (1, 'f'), (0, 'a(b(c)(d)e)(f)g')]

Answer 2

Parentheses matching requires a parser with a push-down automaton. Some libraries exist, but the rules are simple enough that we can write it from scratch:

def push(obj, l, depth):
    while depth:
        l = l[-1]
        depth -= 1

    l.append(obj)

def parse_parentheses(s):
    groups = []
    depth = 0

    try:
        for char in s:
            if char == '(':
                push([], groups, depth)
                depth += 1
            elif char == ')':
                depth -= 1
            else:
                push(char, groups, depth)
    except IndexError:
        raise Exception('Parentheses mismatch')

    if depth > 0:
        raise Exception('Parentheses mismatch')
    else:
        return groups

print(parse_parentheses('a(b(cd)f)')) # ['a', ['b', ['c', 'd'], 'f']]

Answer 3

#!/usr/bin/env python
import re

def ParseNestedParen(string, level):
    """
    Generate strings contained in nested (), indexing i = level
    """
    if len(re.findall("\(", string)) == len(re.findall("\)", string)):
        LeftRightIndex = [x for x in zip(
        [Left.start()+1 for Left in re.finditer('\(', string)], 
        reversed([Right.start() for Right in re.finditer('\)', string)]))]

    elif len(re.findall("\(", string)) > len(re.findall("\)", string)):
        return ParseNestedParen(string + ')', level)

    elif len(re.findall("\(", string)) < len(re.findall("\)", string)):
        return ParseNestedParen('(' + string, level)

    else:
        return 'fail'

    return [string[LeftRightIndex[level][0]:LeftRightIndex[level][1]]]

Tests:

if __name__ == '__main__':

    teststring = "outer(first(second(third)second)first)outer"

    print(ParseNestedParen(teststring, 0))
    print(ParseNestedParen(teststring, 1))
    print(ParseNestedParen(teststring, 2))

    teststring_2 = "outer(first(second(third)second)"

    print(ParseNestedParen(teststring_2, 0))
    print(ParseNestedParen(teststring_2, 1))
    print(ParseNestedParen(teststring_2, 2))

    teststring_3 = "second(third)second)first)outer"

    print(ParseNestedParen(teststring_3, 0))
    print(ParseNestedParen(teststring_3, 1))
    print(ParseNestedParen(teststring_3, 2))

output:

Running tool: python3.1

['first(second(third)second)first']
['second(third)second']
['third']
['first(second(third)second)']
['second(third)second']
['third']
['(second(third)second)first']
['second(third)second']
['third']
>>>