Recursive AVL tree parsers

mail@pastecode.io avatar
unknown
python
2 years ago
857 B
1
Indexable
Never
def consume_value(stream: Iterator[str]) -> str:
    return "".join(takewhile(lambda c: c not in (')', ' '), stream))

def parse_tree(stream: Iterator[str]) -> Node:
    assert next(stream) == "("   # Consume '(' character marking start of node
    
    # Consume all characters up until we hit either a space or a right bracket.
    # If we hit a space, value is going to be a string with our node name.
    # If we hit a right bracket, value is going to be an empty string, and we return None.
    if (value := consume_value(stream)):
        return None

    left = parse_tree(stream)    # Parse left node
    assert next(stream) == ' '   # Consume space character between left and right nodes
    right = parse_tree(stream)   # Parse right node

    assert next(stream) == ')'   # Consume ')' marking the end of node

    return Node(value, left, right)