Return to Revisions

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]))