I am attempting to create a Python function which parses through a bracket representation of a binary tree and outputs a line-by-line bipartite graph representation of it, where the partitions are separated by a "|", thus:
Binary tree bracket representation:
(((A, B), C), D)
Bipartite graph relationship output:
A B | C D
A B C | D
I approached it using recursion, maintaining each bipartite relationship line in a list, taking the original bracket notation string and the starting index of parsing as input.
def makeBipartRecursive(treeStr, index):
bipartStr = ""
bipartList = []
for ind, char in enumerate(treeStr, start=index):
if char == '(':
# Make recursive call to makeBipartRecursive
indx = ind
bipartList.append(makeBipartRecursive(treeStr, indx+1))
elif char == ')':
group1 = treeStr[0:index-1] + treeStr[ind+1::]
group2 = treeStr[index:ind]
return group1 + " | " + group2
elif char == ',':
bipartStr += " "
else:
# Begin construction of string
bipartStr += char
Each time an open-parenthesis is encountered, a recursive call is made, beginning enumeration at the index immediately following the open-parenthesis, so as to prevent infinite recursion (Or so I think). If possible, try to ignore the fact that I'm not actually returning a list. The main issue is that I encounter infinite recursion, where the enumeration never progresses beyond the first character in my string. Should my recursive call with the incremented start position for the enumeration not fix this?
Thanks in advance.
You are misinterpreting the use of the start
parameter of enumerate
. It does not mean start the enumeration at this position but start counting from this index. See help(enumerate)
:
| The enumerate object yields pairs containing a count (from start, which
| defaults to zero) and a value yielded by the iterable argument.
So basically each time you perform a recursive call you start again from the beginning of your string.