# Learning Python - Parsing s-expression structure into tree and summing the paths

I'm new to Python, just attempted the task at https://www.cs.duke.edu/courses/cps100/fall03/assign/extra/treesum.html

The part I found hardest was parsing the expression into the tree structure. I was originally trying to build a regular tree structure (ie a Node object with left and right nodes), but without any logic for the insertion (ie newNode < node then insert left, newNode > node then insert right) I couldn't find a way.

In the end I've used Python's lists to kind of replicate the expression structure, and walk the paths as they're created. Each time I find a leaf, I calculate the cumulative sum, pop the last added node, and carry on.

The one part of the code I really don't like is the way I'm finding leafs:

if tree and expression[i-1:i+3] == ['(',')','(',')']:

and I don't like that I've done:

pair[1].replace('(', ' ( ').replace(')', ' ) ').split()

twice.

Any guidance on any part of this - style, Pythonicness or just general approach and logic would be great. My code in full is:

def pairs(value):
""" Yields pairs (target, expression) """
nest_level = 0
expr = ""
target = 0

value = value.replace('(', ' ( ').replace(')', ' ) ').split()
for x in value:
if x.isdigit() and not expr:
target = x
else:
expr += x

if x is '(':
nest_level += 1
elif x is ')':
nest_level -= 1
if nest_level is 0:
yield target, expr
expr = ''
target = 0

def main():
with open('input') as f:
expr_input = f.read()

level = 0
current_target = 0

for pair in pairs(expr_input):
current_target = pair[0]
# stack representing the 'current path'
tree = list()
# store the cumulative total of each path for this expression
cumulative_totals = list()
running_total = 0

expression = pair[1].replace('(', ' ( ').replace(')', ' ) ').split()
for i, s in enumerate(expression):
if s is '(':
level += 1
elif s == ')':
level -= 1
# "is leaf?" ugh.
if tree and expression[i-1:i+3] == ['(',')','(',')']:
cumulative_totals.append(running_total)
# remove the node and carry on down the next path
node = tree.pop()
running_total = running_total - int(node)
if level is 0:
if int(current_target) in cumulative_totals:
print "yes"
else:
print "no"
else:
running_total += int(s)
tree.append(s)

if __name__ == '__main__':
main()

Thanks!

-

## 2 Answers

1. Avoid indentation.

print "no"

When you need this amount of spaces in front of your code, I'd say no too.

This is clearly a sign that what you're writing could be extracted into a function call, our main could be a chain of function calls instead of a big clump of code.

with open('input') as f:
parseFile(f)

def parseFile(...):
...
for pair in pairs(expr_input): parsePair(pair)
...

def parsePair(...):
...
for i, s in enumerate(expression): addExpressionToSummation(i, s)
...

Of course, this won't work out of the box; that's what object-oriented programming will help with.

Also, if you need to map one-to-one, use list comprehensions or functions like map.

2. Regular expressions might sometimes be valuable.

value = value.replace('(', ' ( ').replace(')', ' ) ').split()

can be

value = re.sub(r'($$|$$)', r' \1 ', value).split();

which can be improved to not add multiple spaces by restricting the match or by doing another replace where you replace r' +' by r' '. Of course this example might not be worth it, but if you've got to do heavier duty then you'll quickly want to resort to a regular expression instead of much longer trial-and-error code.

3. Conditions can be functions, too.

# "is leaf?" ugh.
if tree and expression[i-1:i+3] == ['(',')','(',')']:

Imagine that'd be

if isLeaf(tree, expression):

Oh look, our documentation line is gone. ;)

-

EDIT: Thanks for the comments Matt!

This is not per-ce what you asked, but code can be split into two distinct steps:

1. Parse the given string to some data structure.
2. Execute algorithm on that structure.

Step [1] can be done in 3 lines, as the string is almost a python syntax as is:

s = '(5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )'
s = s.replace('(',',[')
s = s.replace(')',']')
s = s[1:]

Now s is a valid python list:

'[5 ,[4 ,[11 ,[7 ,[] ,[]] ,[2 ,[] ,[]] ] ,[]] ,[8 ,[13 ,[] ,[]] ,[4 ,[] ,[1 ,[] ,[]] ] ] ]'

Let's put it into a variable:

ltree = eval(s)

Now ltree is a good tree representation - it is in fact a DFS walk on the tree.

ltree[0] is the root value, ltree[1] is the left subtree, and ltree[2] is the right subtree - and so on.

And the code to test the walk becomes simple:

def is_sum(tree, num):
if (len(tree) == 0):   # 'in' a leaf
return False
if (len(tree[1]) == 0 & len(tree[2]) == 0):   # leaf
return num == tree[0]
return (is_sum(tree[1], num-tree[0]) | is_sum(tree[2], num-tree[0]))
-
Why not ltree = eval(str) and str = str[1:]? Also, you shouldn't use str as a variable, it is a built-in function. –  Matt Nov 8 '12 at 19:19