Last active
October 12, 2018 19:13
-
-
Save dtranhuusm/27aa54c806c474aaf7dc6b13b06a28ac to your computer and use it in GitHub Desktop.
Convert tree string to dictionary
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ Function to convert a tree in string format to a dictionary. | |
| There is no error handling. | |
| It doesn't allow a level to be skipped. | |
| """ | |
| def tree_child(acc, path, element): | |
| node = element.lstrip() | |
| current = None | |
| for p in path: | |
| if current: | |
| current = current[p] | |
| else: | |
| current = acc[p] | |
| current[node] = dict() | |
| return node | |
| def tree_sibling(acc, path, element): | |
| return tree_child(acc, path[:-1], element) | |
| def _parse_tree(acc, path, indent, tree_ls): | |
| """ Recursive function parsing a list. | |
| Args: | |
| acc(dictionary): accumulator dictionary used both as in-out | |
| path(list): current node | |
| indent(str): indentation value used to identify depth of tree | |
| tree_ls(list): list of lines indented following indent | |
| Returns: | |
| dictionary: dictionary corresponding to tree_ls provided | |
| """ | |
| #print(acc, path) | |
| if tree_ls: | |
| line = tree_ls[0].rstrip() | |
| if not line: | |
| return _parse_tree(acc, path, indent, tree_ls[1:]) | |
| if not path: | |
| node = line.lstrip() | |
| acc[node] = dict() | |
| return _parse_tree(acc, [node], indent, tree_ls[1:]) | |
| next_indent = indent * len(path) | |
| current_indent = next_indent[:-len(indent)] | |
| if len(line) > len(next_indent) and line[:len(next_indent)]==next_indent: | |
| node = tree_child(acc, path, line[len(next_indent):]) | |
| return _parse_tree(acc, path+[node], indent, tree_ls[1:]) | |
| if len(line) > len(current_indent) and line[:len(current_indent)]==current_indent: | |
| node = tree_sibling(acc, path, line[len(current_indent):]) | |
| return _parse_tree(acc, path[:-1]+[node], indent, tree_ls[1:]) | |
| # back up the tree and parse recursively | |
| return _parse_tree(acc, path[:-1], indent, tree_ls) | |
| # end of recursion | |
| return acc | |
| def parse_tree(tree_st, indent): | |
| res = dict() | |
| path = [] | |
| val_ls = tree_st.split('\n') | |
| return _parse_tree(res, path, indent, val_ls) | |
| if __name__=="__main__": | |
| tree = """ | |
| one | |
| one | |
| one | |
| two | |
| two | |
| one | |
| three | |
| one | |
| two | |
| three | |
| """ | |
| print(parse_tree(tree, " ")) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment