423,850 Members | 1,074 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 423,850 IT Pros & Developers. It's quick & easy.

Need help to tree-ify nested parenthesis...

P: n/a
hello,

i need some help to 'tree-ify' a string...

for example i have strings such as :

s = """A(here 's , B(A ) silly test) C(to show D(what kind) of stuff i
need))"""

and i need to parse them to have a tree representation such as :

["A", [
"here 's" ,
[ "B", [
'A ) "silly test'
]],
["C", [
"to show",
["D", [
"what kind"
]],
"of stuff i need",
]]
]]

notes : "ALLCAPS(something else)" are some kind of tag, "something
else" may contain ALLCAPS() and thus be nested or contain others
characters. the parenthesis between 'A' and 'silly test' isn't a
mistake but a case to handle string is quite well formed = orphan
parenthesis will always be surrounded by whitespace - like in 'A )
silly test' or 'A ( silly test'

if have started to write a function which give me pos and nested
string, but still need help to finish to tree-ify it from there... or
maybe there is a more obvious way ? (i think i didn't need to create
real finite state automata for this stuff)

thanks
parse(d)

-1 D what kind 42 @ 51
-1 C to show D(what kind) of stuff i need 32 @ 68
-1 B A ) silly test 14 @ 28
-1 A here 's , B(A ) silly test) C(to show D(what kind) of stuff i
need) 2 @ 69
-------------------%<------------------

def parse(s):

n = len(s)

p = re.compile(r'([A-Z_]+\()')
pos = []
iterator = p.finditer(s)
for match in iterator:
pos.append(match.span())

j = 0
pos.reverse()
for (start, end) in pos:
opened = 0
i = end
while i < n - j:
if s[i] == '(':
opened += 1
if s[i] == ')' and s[i - 1] != ' ':
opened -= 1
if opened < 0:
print opened, s[start:end-1], s[end:i], "%s @ %s" % (end,
i)
break
i += 1

Jul 18 '05 #1
Share this question for a faster answer!
Share on Google+

This discussion thread is closed

Replies have been disabled for this discussion.