Биекция правильной скобочной последовательности и бинарного дерева.

BinaryTreeFromBracketsString.py

class BinaryNode(object):
    def __init__(self):
        self.right_node = False
        self.left_node = False

    def to_brackets_string(self):
        result = "("
        if self.left_node is not False:
            result += self.left_node.to_brackets_string()
        result += ")"
        if self.right_node is not False:
            result += self.right_node.to_brackets_string()
        return result


def close_bracket_index_for_first_break(brackets):
    """
    Нахождения позиции закрывающей скобки для первой открытой скобки
    в правильной скобочной последовательности
    :param brackets: строка содержащяя скобочную последовательность
    :return: индекс символа в строке
    """
    # первая скобка открывающаяся
    assert brackets[0] == "("
    count_opened = 1
    for i in range(1, len(brackets)):
        count_opened = count_opened + 1 if brackets[i] == "(" else count_opened - 1
        if count_opened == 0:
            return i
    # Неверная скобочная последовательность
    assert False


def build_tree(brackets_str):
    """
    Построение бинарного дерева по правильной скобочной последовательности
    :param brackets_str: скобочная последовательность
    :return: ссылка на корень бинарного дерева
    """
    if brackets_str == '':
        return False
    tree = BinaryNode()
    index = close_bracket_index_for_first_break(brackets_str)
    tree.left_node = build_tree(brackets_str[1:index])
    tree.right_node = build_tree(brackets_str[(index + 1):])
    return tree


def tests():
    assert close_bracket_index_for_first_break("(())()") == 3
    assert close_bracket_index_for_first_break("()") == 1
    assert close_bracket_index_for_first_break("()()") == 1
    assert close_bracket_index_for_first_break("(()())") == 5

    print("(())()")
    print(build_tree("(())()").to_brackets_string())
    print("()")
    print(build_tree("()").to_brackets_string())
    print("()()")
    print(build_tree("()()").to_brackets_string())
    print("(())()(())")
    print(build_tree("(())()(())").to_brackets_string())


if __name__ == "__main__":
    tests()