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