From a coding interview I did. The problem was to come up with an encoding for a tree of integers

IntTree.py

'''Problem: come up with an encoding for a tree of integers.

Tree representing
       1
      /|\ 
     2 3 4 
    /\   |\
   5  6  9 11
      /\  \
     7  8  10
     
Eventually during the interview I arrived at an encoding of a stream of <integer> and <operation> where operation is 
+ to indicate a child level and - to indicate popping up a level.

i.e. 1 + 2 + 5 6 + 7 8 - - 3 4 + 9 + 10 - 11 for the tree above
     
If I'd had my head screwed on straight, I would've realized this was just another S-expression, and possibly 
encoded it something like this:

(1(2(5 6(7 8))3 4(9(10)11)))

don't think it affects the implementation much.
'''

# encoding for tree above as preorder traversal
test_input = '1 + 2 + 5 6 + 7 8 - - 3 4 + 9 + 10 - 11'

class IntNode():
	def __init__(self, value):
		self.children = []
		self.value = value
	
	def __str__(self):
		return "%s - %s" % (self.value, str(self.children))
	
	def __repr__(self):
		return "(%r,%r)" % (self.value,self.children)

def is_int(s):
    try:
        int(s)
        return True
    except ValueError:
        return False
        
def preorder_parse(field_gen):
	new_nodes = []
	while True:
		try:
			op = next(field_gen)[1]
			print(op)
			if is_int(op):
				new_nodes.append(IntNode(int(op)))
			elif op == '+':
				new_nodes[-1].children = preorder_parse(field_gen)
			elif op == '-':
				return new_nodes
		except StopIteration:
			return new_nodes
	
def write_preorder(tree):
	values = [str(tree.value)]
	if len(tree.children) > 0:
		values.append('+')
	for c in tree.children:
		values.extend(write_preorder(c))
	if len(tree.children) > 0:
		values.append('-')
	return values

def main():
	tree = preorder_parse(enumerate(test_input.split(' ')))
	print("%r" % (tree[0]))
	test_output = ' '.join(write_preorder(tree[0]))
	print(test_output)
	
#if __name__ == "__main__":
main()