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!