19

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]]

4 Answers 4

49

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')]
5
  • The behavior associated with ParseNestedParen('(a)(b)(c)', 0) is actually correct, but my function is the wrong tool for the job, i wrote the function with string = "some_function(another_function(some_argument))" in mind. why return in a list? shouldn't have. great point, thanks! when will I return fail? I don't know. maybe never. its there from when i was coding the function repatedly calling find all is wasteful? So should I just make list countparen = [re.findall(str) for str in ["(",")"]] and use that instead? how else should I rebalnce the parenthesis? thanks for comments! Commented Nov 26, 2010 at 12:18
  • It's hard to say what the right thing to do about unbalanced parentheses is, because I don't know what the function is going to be used for. Most likely unbalanced strings are a kind of input error, and should be either ignored (for applications like syntax highlighting) or raised as errors (for applications like compiling). Commented Nov 26, 2010 at 12:41
  • 1
    list(parenthetic_contents('a(b(c)(d)e)(f)g')) actually gives me [(1, 'c'), (1, 'd'), (0, 'b(c)(d)e'), (0, 'f')]
    – Peter
    Commented Oct 5, 2020 at 14:35
  • @Peter: That's not the same as the example code in the post. Commented Oct 5, 2020 at 14:39
  • 1
    In awe at the beauty of this solution. Absolute code.
    – Martin
    Commented Feb 7, 2023 at 16:01
15

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 ValueError('Parentheses mismatch')

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

print(parse_parentheses('a(b(cd)f)')) # ['a', ['b', ['c', 'd'], 'f']]
2
  • this is awesome, do you have more refs about the behavior of different automata in Python, or how to code them in Python in simple ways like this?
    – DaniPaniz
    Commented Aug 18, 2020 at 17:54
  • @DaniPaniz This is a canonical example which has very few states, this is why it's easily writable in Python. More complex examples usually require a parser generator, you won't write them by hand. Commented Aug 19, 2020 at 15:18
4

Below is my Python solution with a time complexity of O(N)

str1 = "(a(b(c)d)(e(f)g)hi)"

def content_by_level(str1, l):
    level_dict = {}
    level = 0
    level_char = ''
    for s in str1:
        if s == '(':
            if level not in level_dict:
                level_dict[level] = [level_char]
            elif level_char != '':
                level_dict[level].append(level_char)
            level_char = ''
            level += 1
        elif s == ')':
            if level not in level_dict:
                level_dict[level] = [level_char]
            elif level_char != '':
                level_dict[level].append(level_char)
            level_char = ''
            level -= 1
        else:
            level_char += s
    
    print(level_dict) # {0: [''], 1: ['a', 'hi'], 2: ['b', 'd', 'e', 'g'], 3: ['c', 'f']}
    return level_dict[l]

print(content_by_level(str1,0)) # ['']
print(content_by_level(str1,1)) # ['a', 'hi']
print(content_by_level(str1,2)) # ['b', 'd', 'e', 'g']
print(content_by_level(str1,3)) # ['c', 'f']
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']
>>> 
1
  • So, as you can tell, the function allows unbalanced parentheses, though not in a very elegant way. Commented Nov 26, 2010 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.