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]]
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:
fail
?re.findall
and then throwing away the result is wasteful.>>> 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')]
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']]
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']
#!/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']
>>>
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With