import re class Node(): def __init__(self, data=None,left=None,right=None): self.data = data self.next = list() self.left = left self.right = right def __str__(self): return str(self.data) def add_child(self, node): self.next.append(node) class Tree: def __init__(self): self.root = Node() self.tree = list() def Nested_Tree(self,text): #스택을 사용하여 '('와 ')'를 사용해 구현 stack = list() for calc in text: if calc == '(': stack.append(calc) elif calc == ')': input_n = stack.pop() stack.pop() if not stack: self.root = input_n break else: k=stack.pop() k.add_child(input_n) #self.tree.append(k) stack.append(k) else: t= Node(calc) stack.append(t) self.tree.append(t) def PrintLL(self,list): for i in range(0,len(list)): if not list[i].next: continue print() print(list[i],'--> [', end=" ") for j in range(0,len(list[i].next)): print("'",list[i].next[j], end="' ") if j < len(list[i].next) - 1: print(",",end="") print("]") def left_right(self,tree): for i in range(0,len(tree)): if not tree[i].next: continue else: tree[i].left = tree[i].next[0] for j in range(0,len(tree[i].next)-1): tree[i].next[j].right = tree[i].next[j+1] def left_right_print(self,list): for i in range(0,len(list)): if not list[i].left: continue print(list[i],'--> [ child : ',list[i].left,', sibling : ', end ='') right = list[i].left.right while right: print(right,' ', end = '') right = right.right print('] \n') if __name__ == "__main__": text = "(A(B(C)(D(E)(F)))(G(H))(I(J(K))))" text = re.sub('([\(\)])' , ' \g<1> ' , text) calc = text.split() k = Tree() k.Nested_Tree(calc) # print(k.tree[0] ,'-->',k.tree[0].next[0],k.tree[0].next[1]) print('\n') print("ROOT --> ['",k.root,"']") k.PrintLL(k.tree) print('\n') print('left child right sibling structure \n') k.left_right(k.tree) k.left_right_print(k.tree) |
'파이썬으로 구현한 알고리즘' 카테고리의 다른 글
| Postfix 구현하기 (0) | 2017.11.16 |
|---|---|
| Regular Expression으로 전화번호 Search 구현하기 (0) | 2017.11.16 |
| Boyer-Moore Algorithm 구현하기 (0) | 2017.11.11 |
| KMP Algorithm 구현하기 (0) | 2017.11.11 |
| Priority Que 구현하기(우선순위 큐) (0) | 2017.09.25 |