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.replace('(', ' ( ').replace(')', ' ) ').split()
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 # 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.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()