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]]
Answers:
Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.
Method 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.findalland 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')]
Method 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 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']]
Method 3
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']
Method 4
#!/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'] >>>
All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0