| 94 | |
| 95 | current_idx = 0 |
| 96 | def str2tree(s, word2idx): |
| 97 | # take a string that starts with ( and MAYBE ends with ) |
| 98 | # return the tree that it represents |
| 99 | # EXAMPLE: "(3 (2 It) (4 (4 (2 's) (4 (3 (2 a) (4 (3 lovely) (2 film))) (3 (2 with) (4 (3 (3 lovely) (2 performances)) (2 (2 by) (2 (2 (2 Buy) (2 and)) (2 Accorsi))))))) (2 .)))" |
| 100 | # NOTE: not every node has 2 children (possibly not correct ??) |
| 101 | # NOTE: not every node has a word |
| 102 | # NOTE: every node has a label |
| 103 | # NOTE: labels are 0,1,2,3,4 |
| 104 | # NOTE: only leaf nodes have words |
| 105 | # s[0] = (, s[1] = label, s[2] = space, s[3] = character or ( |
| 106 | |
| 107 | # print "Input string:", s, "len:", len(s) |
| 108 | |
| 109 | global current_idx |
| 110 | |
| 111 | label = int(s[1]) |
| 112 | if s[3] == '(': |
| 113 | t = Tree(None, label) |
| 114 | # try: |
| 115 | |
| 116 | # find the string that represents left child |
| 117 | # it can include trailing characters we don't need, because we'll only look up to ) |
| 118 | child_s = s[3:] |
| 119 | t.left = str2tree(child_s, word2idx) |
| 120 | |
| 121 | # find the string that represents right child |
| 122 | # can contain multiple ((( ))) |
| 123 | # left child is completely represented when we've closed as many as we've opened |
| 124 | # we stop at 1 because the first opening paren represents the current node, not children nodes |
| 125 | i = 0 |
| 126 | depth = 0 |
| 127 | for c in s: |
| 128 | i += 1 |
| 129 | if c == '(': |
| 130 | depth += 1 |
| 131 | elif c == ')': |
| 132 | depth -= 1 |
| 133 | if depth == 1: |
| 134 | break |
| 135 | # print "index of right child", i |
| 136 | |
| 137 | t.right = str2tree(s[i+1:], word2idx) |
| 138 | |
| 139 | # except Exception as e: |
| 140 | # print "Exception:", e |
| 141 | # print "Input string:", s |
| 142 | # raise e |
| 143 | |
| 144 | # if t.left is None or t.right is None: |
| 145 | # raise Exception("Tree node has no word but left and right child are None") |
| 146 | return t |
| 147 | else: |
| 148 | # this has a word, so it's a leaf |
| 149 | r = s.split(')', 1)[0] |
| 150 | word = r[3:].lower() |
| 151 | # print "word found:", word |
| 152 | |
| 153 | if word not in word2idx: |