class ExpressionTreeNode:
    def __init__(self, symbol):
        self.symbol = symbol
        self.left, self.right = None, None


def _symbol_type(symbol):
    if symbol.isnumeric():
        symbol_type = 'NUMBER'
    elif symbol in '+-*/':
        symbol_type = 'OPERATOR'
    elif symbol == '(':
        symbol_type = 'LP'
    elif symbol == ')':
        symbol_type = 'RP'
    return symbol_type


class Expression:
    def __init__(self, expr):
        self.expr = expr
        self._current = 0

    def __next__(self):
        symbol = self.expr[self._current]
        self._current = self._current + 1
        return symbol, _symbol_type(symbol)

    def __getitem__(self, index):
        symbol = self.expr[self._current+index-1]
        return symbol, _symbol_type(symbol)

    def has_next(self):
        return self._current < len(self.expr)


def build_node(expr):
    next_symbol, next_symbol_type = expr[1]
    if next_symbol_type == 'RP':
        return
    symbol, symbol_type = next(expr)
    if symbol_type == 'NUMBER':
        return ExpressionTreeNode(symbol)
    else:
        assert symbol_type == 'LP'
        node = build_expr(expr)
        assert next(expr) == (')', 'RP')
        return node


def is_expr_end(expr):
    if not expr.has_next():
        return True
    if expr[1][1] == 'RP':
        return True
    return False


def build_expr(expr):
    left = build_node(expr)
    if is_expr_end(expr):
        return left
    symbol, symbol_type = next(expr)
    assert symbol_type == 'OPERATOR', f'symbol: {symbol}'
    current_operator = ExpressionTreeNode(symbol)
    right = build_node(expr)
    while True:
        while True:
            next_operator = None
            if is_expr_end(expr):
                break
            symbol, symbol_type = next(expr)
            assert symbol_type == 'OPERATOR', f'symbol: {symbol}'
            next_operator = ExpressionTreeNode(symbol)
            if symbol not in '*/':
                break
            next_operator.left = right
            next_operator.right = build_node(expr)
            right = next_operator
        # breakpoint()
        if current_operator.symbol in '*/':
            if right.symbol not in '*/':
                current_operator.left = left
                current_operator.right = right
                left = current_operator
            else:
                left_operator = right
                while left_operator.left.left:
                    left_operator = left_operator.left
                current_operator.left = left
                current_operator.right = left_operator.left
                left_operator.left = current_operator
                left = right
        else:
            assert current_operator.symbol in '+-'
            current_operator.left = left
            current_operator.right = right
            left = current_operator
        if next_operator is not None:
            current_operator = next_operator
            right = build_node(expr)
        else:
            break
    return left


def format_tree(root):
    result = []
    nodes = [root]
    while True:
        next_level = []
        for node in nodes:
            if node is None:
                result.append('#')
                next_level.extend([None, None])
            else:
                result.append(node.symbol)
                next_level.extend([node.left, node.right])
        if all(item is None for item in next_level):
            break
        else:
            nodes = next_level
    return result


if __name__ == '__main__':
    #print(format_tree(build_expr(Expression(
    #    ["10","+","(","3","-","5",")","+","7","*","7","-","2"]
    #    )))
    #)

    #print(format_tree(build_expr(Expression(
    #    ["(","(","(","(","(",")",")",")",")",")"]
    #    )))
    #)
    #print(format_tree(build_expr(Expression(
    #    ['(', '(', '2', ')', '*', '3', ')']
    #    )))
    #)
    #print(format_tree(build_expr(Expression(
    #    ["(","(","1","+","(","2",")",")","*","3","+","(","4","/","2",")","-","5",")"]
    #    )))
    #)
    # print(format_tree(build_expr(Expression(
    #     ["2","*","6","-","(","23","+","7",")","/","(","1","+","2",")"]
    #     )))
    # )
    print(format_tree(build_expr(Expression(
        ["77","*","(","987631","+","14358960","/","11","/","5","/","28","-","838415",")"]
        )))
    )

class ExpressionTreeNode:
    def __init__(self, symbol):
        self.symbol = symbol
        self.left, self.right = None, None


def _symbol_type(symbol):
    if symbol.isnumeric():
        symbol_type = 'NUMBER'
    elif symbol in '+-*/':
        symbol_type = 'OPERATOR'
    elif symbol == '(':
        symbol_type = 'LP'
    elif symbol == ')':
        symbol_type = 'RP'
    return symbol_type


class Expression:
    def __init__(self, expr):
        self.expr = expr
        self._current = 0

    def __next__(self):
        symbol = self.expr[self._current]
        self._current = self._current + 1
        return symbol, _symbol_type(symbol)

    def __getitem__(self, index):
        symbol = self.expr[self._current+index-1]
        return symbol, _symbol_type(symbol)

    def has_next(self):
        return self._current < len(self.expr)


def build_node(expr):
    next_symbol, next_symbol_type = expr[1]
    if next_symbol_type == 'RP':
        return
    symbol, symbol_type = next(expr)
    if symbol_type == 'NUMBER':
        return ExpressionTreeNode(symbol)
    else:
        assert symbol_type == 'LP'
        node = build_expr(expr)
        assert next(expr) == (')', 'RP')
        return node


def is_expr_end(expr):
    if not expr.has_next():
        return True
    if expr[1][1] == 'RP':
        return True
    return False


def build_expr(expr):
    left = build_node(expr)
    if is_expr_end(expr):
        return left
    symbol, symbol_type = next(expr)
    assert symbol_type == 'OPERATOR', f'symbol: {symbol}'
    current_operator = ExpressionTreeNode(symbol)
    right = build_node(expr)
    while True:
        while True:
            next_operator = None
            if is_expr_end(expr):
                break
            symbol, symbol_type = next(expr)
            assert symbol_type == 'OPERATOR', f'symbol: {symbol}'
            next_operator = ExpressionTreeNode(symbol)
            if symbol not in '*/':
                break
            next_operator.left = right
            next_operator.right = build_node(expr)
            right = next_operator
        # breakpoint()
        if current_operator.symbol in '*/':
            if right.symbol not in '*/':
                current_operator.left = left
                current_operator.right = right
                left = current_operator
            else:
                left_operator = right
                while left_operator.left.left:
                    left_operator = left_operator.left
                current_operator.left = left
                current_operator.right = left_operator.left
                left_operator.left = current_operator
                left = right
        else:
            assert current_operator.symbol in '+-'
            current_operator.left = left
            current_operator.right = right
            left = current_operator
        if next_operator is not None:
            current_operator = next_operator
            right = build_node(expr)
        else:
            break
    return left


def format_tree(root):
    result = []
    nodes = [root]
    while True:
        next_level = []
        for node in nodes:
            if node is None:
                result.append('#')
                next_level.extend([None, None])
            else:
                result.append(node.symbol)
                next_level.extend([node.left, node.right])
        if all(item is None for item in next_level):
            break
        else:
            nodes = next_level
    return result


if __name__ == '__main__':
    #print(format_tree(build_expr(Expression(
    #    ["10","+","(","3","-","5",")","+","7","*","7","-","2"]
    #    )))
    #)

    #print(format_tree(build_expr(Expression(
    #    ["(","(","(","(","(",")",")",")",")",")"]
    #    )))
    #)
    #print(format_tree(build_expr(Expression(
    #    ['(', '(', '2', ')', '*', '3', ')']
    #    )))
    #)
    #print(format_tree(build_expr(Expression(
    #    ["(","(","1","+","(","2",")",")","*","3","+","(","4","/","2",")","-","5",")"]
    #    )))
    #)
    # print(format_tree(build_expr(Expression(
    #     ["2","*","6","-","(","23","+","7",")","/","(","1","+","2",")"]
    #     )))
    # )
    print(format_tree(build_expr(Expression(
        ["77","*","(","987631","+","14358960","/","11","/","5","/","28","-","838415",")"]
        )))
    )

# breakpoint() #print(format_tree(build_expr(Expression( #    ["10","+","(","3","-","5",")","+","7","*","7","-","2"] #    ))) #) #print(format_tree(build_expr(Expression( #    ["(","(","(","(","(",")",")",")",")",")"] #    ))) #) #print(format_tree(build_expr(Expression( #    ['(', '(', '2', ')', '*', '3', ')'] #    ))) #) #print(format_tree(build_expr(Expression( #    ["(","(","1","+","(","2",")",")","*","3","+","(","4","/","2",")","-","5",")"] #    ))) #) # print(format_tree(build_expr(Expression( #     ["2","*","6","-","(","23","+","7",")","/","(","1","+","2",")"] #     ))) # )