import re
def solve(input):
#
# build complete binary tree
#
tree = [None]*256
def put(node, index, path):
if not path:
tree[index] = node
elif path[0] == 'L':
put(node, 2*index+1, path[1:])
elif path[0] == 'R':
put(node, 2*index+2, path[1:])
input = [x.split(',') for x in re.findall('\((.*?)\)', input)]
for node, path in input:
put(node, 0, path)
#
# check completeness -- all nodes except the root have parent
#
complete = True
for i in range(1, len(tree)):
if tree[i] is not None:
if tree[(i-1)/2] is None:
complete = False
break
if complete:
print [x for x in tree if x is not None]
else:
print 'not complete'
solve('(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR)')
solve('(3,L) (4,R)')
import re
def solve(input):
complete = [True]
#
# build complete binary tree
#
tree = [None]*256
def put(node, index, path):
if not path:
if tree[index] is None:
tree[index] = node
else:
complete[0] = False
elif path[0] == 'L':
put(node, 2*index+1, path[1:])
elif path[0] == 'R':
put(node, 2*index+2, path[1:])
for node, path in input:
put(node, 0, path)
#
# check completeness -- all nodes except the root have parent
#
for i in range(1, len(tree)):
if tree[i] is not None:
if tree[(i-1)/2] is None:
complete[0] = False
break
if complete[0]:
print [x for x in tree if x is not None]
else:
print 'not complete'
def solve_all():
s = """
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(11,LL) (7,LLL) (8,R) (8,LL)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
"""
t = []
for x in re.findall('\((.*?)\)', s):
if not x:
solve(t)
t = []
else:
t.append(x.split(','))
solve_all()
open System.Text.RegularExpressions //use alternative if use ocaml
open System //use alternative if use ocaml
let hd = List.head //ignore this if use SML
let tl = List.tail //ignore this if use SML
let ofstr (str:string)=
let heap = Array.create(256) -1
let heapWrite index n = if heap.[index] <> -1 then
failwith "incomplete" else heap.[index] <- n
let conv (num,path:string)=
Int32.Parse(num),path.ToCharArray()|>List.ofArray
let heapL n = n * 2 + 1
let heapR n = n * 2 + 2
let rec cInsert num path counter =
match path with
| [] -> heapWrite counter num
| head::tail when head = 'L' -> cInsert num tail (heapL counter)
| head::tail when head = 'R' -> cInsert num tail (heapR counter)
| _ -> failwith "unknown"
str.Split(' ')|>Array.map(fun x->Regex.Match(x,@"\((\d*),(\w*)\)"))|>
Array.map(fun x->(x.Groups.[1].Value,x.Groups.[2].Value)) |>
Array.map conv |> Array.iter(fun (n,p) -> cInsert n p 0)
heap
let isComplete (heap:int [])=
let rec isCompleteRec n =
if n=1 then true else
let nP=(n-(2-n%2)) / 2
if heap.[nP] = -1 && heap.[n] <> -1 then false
else isCompleteRec (n - 1)
isCompleteRec (heap.Length-1)
let printHeap heap=
heap |> Array.filter(fun x->x <> -1)
let heap = ofstr "(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR)"
heap |> isComplete |> printfn "heap is completed?%b"
heap |> printHeap |> printfn "data : %A"
class Node:
def __init__(self, left=None, right=None, value=None):
self.left = left
self.right = right
self.value = value
def build_child(node, value, path):
branch, path = path[:1], path[1:]
if branch == 'L':
if node.left is None:
node.left = Node()
return build_child(node.left, value, path)
elif branch == 'R':
if node.right is None:
node.right = Node()
return build_child(node.right, value, path)
else:
if node.value is None:
node.value = value
return True
else:
return False
def build_tree(input):
tree = Node()
for value, path in input:
if not build_child(tree, value, path):
return
return tree
def is_complete(node):
if node is None:
return True
elif node.value is not None and is_complete(node.left) and is_complete(node.right):
return True
else:
return False
def breadth_first_search(node):
q = [node]
path = []
while q:
node = q.pop(0)
if node is None or node in path:
continue
path.append(node.value)
q.append(node.left)
q.append(node.right)
return path
def solve(input):
tree = build_tree(input)
if tree and is_complete(tree):
print breadth_first_search(tree)
else:
print 'not complete'
def test():
import re
s = """
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(11,LL) (7,LLL) (8,R) (8,LL)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
"""
t = []
for x in re.findall('\((.*?)\)', s):
if not x:
solve(t)
t = []
else:
t.append(x.split(','))
if __name__ == '__main__':
test()