Creating formula based on binary tree leaves

Question

I have list of points with length n (in below example n = 6) after that I have made some other points based on these default point for example point 7 are made by "anding" point 5 and point 4 and so on now my question is based on the data structure I have, how can I retrieve the chain of formula? for example for the point 10 (recursive or non recursive) how can I say from where this point is coming?.

If I want to know how point 10 is made it must return something like this:

(((5 & 4) | 3) | 2) & (5 & 4)

Answer 1

You need a representation of what you've got before you start. I suggest sth like this:

points = [ None,  # dummy value to fill index 0 (we want to start at 1)
           None, None, None, None, None, None,  # for the first six atoms
           (5, 4, '&'),  # for point 7
           (7, 3, '|'),  # for point 8
           (8, 2, '|'),  # for point 9
           (9, 7, '&') ]  # for point 10

Then creating a formula as a string is just recursive:

def formula(points, n):
  if points[n] is None:
    return str(n)
  a, b, operator = points[n]
  return '(%s %s %s)' % (formula(points, a), operator, formula(points, b))

print formula(points, 10)

This will print

((((5 & 4) | 3) | 2) & (5 & 4))

To get all points used in a formula as a set, just use this:

def used(points, n):
  if points[n] is None:
    return { n }
  a, b, operator = points[n]
  return used(points, a) | used(points, b)

print used(points, 10)

will print:

set([2, 3, 4, 5])