build_ast.py

from typing import Dict, Tuple, List

Letter = str
Type = str
AST = List[Tuple[Letter, 'AST']]


def build_ast(tokens: List[Tuple[Letter, Type]]) -> AST:
    if len(tokens) == 0:
        return []
    elif len(tokens) == 1:
        return [tokens[0][0]]
    start = tokens[0]
    depth = 1
    index = 1
    while depth > 0:
        token = tokens[index]
        if token[0] == start[0] and token[1] == "END":
            depth -= 1
        elif token[0] == start[0] and token[1] == "START":
            depth += 1
        index += 1
    result = [(start[0], build_ast(tokens[1:index - 1]))]
    return result + build_ast(tokens[index:])


STACK = []
RESULT = []


def build_ast_2(token: Tuple[Letter, Type]) -> None:
    global STACK
    global RESULT
    if len(STACK) == 0:
        node = (token[0], [])
        STACK.append(node)
        RESULT.append(node)
    else:
        current_token = STACK[-1]
        if token[0] == current_token[0] and token[1] == "END":
            STACK.pop()
        elif token[1] == "START":
            node = (token[0], [])
            current_token[1].append(node)
            STACK.append(node)
        else:
            node = token[0]
            current_token[1].append(node)

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []


def build_ast_for_dumbass_google_interviewer(token: Node) -> None:
    global STACK
    global RESULT
    if len(STACK) == 0:
        node = Node(token[0])
        STACK.append(node)
        RESULT.append(node)
    else:
        current_token = STACK[-1]
        if token[0] == current_token.value and token[1] == "END":
            STACK.pop()
        elif token[1] == "START":
            node = Node(token[0])
            current_token.children.append(node)
            STACK.append(node)
        else:
            node = Node(token[0])
            current_token.children.append(node)


test = [("C", "START"), ("T", "START"), ("hello", "TEXT"), ("T", "END"), ("C", "END"), ("A", "START"), ("A", "END")]
test2 = [('a', "START"), ('b', "START"), ('c', "START"), ('foo', "TEXT"), ('c', "END"),
         ('f', "START"), ('bar', "TEXT"), ('f', "END"), ('c', "START"), ('c', "END"),
         ('f', "START"), ('baz', "TEXT"), ('f', "END"), ('b', "END"), ('a', "END")]
print(build_ast(test2))

# print(RESULT)
for i in test2:
    build_ast_2(i)
    # print(RESULT)


print(RESULT)