-
Notifications
You must be signed in to change notification settings - Fork 0
/
node.py
97 lines (72 loc) · 2.5 KB
/
node.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class Node:
def __init__(self, label, children=None):
self.label = label
self.children = children if children else []
def get_max_depth(self):
max_child_depth = 0
for child in self.children:
max_child_depth = max(max_child_depth, child.get_max_depth())
return 1 + max_child_depth
def get_max_branching(self):
max_branching = 1
if self.children:
max_branching = len(self.children)
for child in self.children:
max_branching = max(max_branching, child.get_max_branching())
return max_branching
def get_num_nodes(self):
node_count = 1
for child in self.children:
node_count += child.get_num_nodes()
return node_count
def __repr__(self, max_len=None, depth=0, add_parens=True):
label_key = self.label
if self.children:
child_rep = ""
for c, child in enumerate(self.children):
flat_child = len(child.children) == 0
child_text = child.__repr__(depth=depth+1, add_parens=(not flat_child))
if max_len and depth==0 and len(child_text) > max_len:
child_text = child_text[0:max_len] + "..."
if c:
child_rep += " " + child_text
else:
child_rep += child_text
rep = "{} {}".format(label_key, child_rep)
else:
# simple node without children
rep = label_key
if add_parens:
rep = "( {} )".format(rep)
return rep
def __str__(self):
return self.__repr__()
def str(self, max_len=0):
return self.__repr__(max_len)
def text_tree_to_node(tree):
'''
text tree conventions:
( A ) ==> parent A
( A B ) ==> parent A with child B
( A B C ) ==> parent A with children B and C
( A ( B C) ) ==> parent A with child B (B has child C)
'''
prev_tok = None
stack = []
parent = None
for tok in tree.split():
if prev_tok == '(':
label = tok
parent = Node(label)
stack.append(parent)
elif tok == ')':
child = parent
stack.pop()
if len(stack) > 0:
parent = stack[-1]
parent.children.append(child)
elif tok != '(':
label = tok
parent.children.append(Node(label))
prev_tok = tok
return parent