Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers 2

  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. ;)

share|improve this answer
add comment

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]))
share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.