# -*- coding: utf-8 -*-

#%% Важные константы.

# binary -- все бинарные операции
binary = set("+*/^")
# unary -- все функции
unary = set(["sin", "cos", "tan", "asin", "acos", "atan", "exp", "sqrt", "ln"])
# variables -- все переменные
variables = set("xyz")
# Переменная дифференцирования
diff_with_respect = "x"
# Все переменные за исключением переменной интегрирования.
yz = variables.difference(diff_with_respect)

#%% Предобработка

def pretreatment(expression):
    """Предобработка выражения. Убирает пробелы и заменяет выражения вида
    (expr1 func -expr2).
    Техническая функция"""
    # убьем пробелы
    expression = expression.replace(" ", "")
    # Чтобы не возиться с минусами (-5+3), заменим:
    # x *- y -> x *-1* y
    expression = expression.replace("*-", "*-1*")
    # x -- y -> x + y
    expression = expression.replace("*--", "+")
    # x / -y -> x /-1/ y
    expression = expression.replace("/-", "/-1/")
    # x +- y -> x - y
    expression = expression.replace("+-", "-")
    # (- x ... -> (-1* x ...
    expression = expression.replace("(-", "(-1*")
    # )- x ... -> )-1* x ...
    expression = expression.replace(")-", ")-1*")
    return expression

#%% парсинг.

def parsing_expression(expression):
    """Парсит выражение. На выходе дает дерево (словарь словарей), ветви
    которого функции либо операции, листы -- числа либо переменные."""
    # Проверяем, не пришла ли пустая строка.
    if (expression == ""):
        raise ValueError("Invalid expression")
    # Проверяем, что исследуемая часть выражения не запихана в скобки
    # если запихана, извлекаем.
    in_bracket = True # Показывает, нужно ли обрывать крайние скобки.
    while(in_bracket):
        bracket = 1 # счетчик скобок
        if (expression[0] == "(" and expression[-1] == ")"):
            for i in range(1, len(expression)-1):
                if (expression[i] == "("):
                    bracket += 1
                elif (expression[i] == ")"):
                    bracket -= 1
                if (bracket == 0):
                    in_bracket = False
                    break
        else:
            in_bracket = False
        if (in_bracket):
            expression = expression[1:(len(expression)-1)]
    # Проверяем, не является ли наше выражение числом. Если является,
    # вернем это число.
    try:
        return(int(expression))
    except:
        pass
    try:
        return(float(expression))
    except:
        pass
    # Проверяем, не является ли наше выражение переменной. Если является,
    # вернем ее
    if (expression in variables):
        return(expression)
    # Теперь нужно разорвать наше выражение на части по операциям с наименьшим
    #приоритетам, находящимся вне скобок.
    priority = {i : -1 for i in binary} # словарь приоритетов.
    bracket = 0 # счетчик скобок
    for i in range(len(expression)):
        if (expression[i] == "("):
            bracket += 1
        elif (expression[i] == ")"):
            bracket -= 1
        if (bracket == 0 and
            expression[i] in priority):
            priority[expression[i]] = i
        # просто для ускорения: если найдена операция с наименьшим приоритетом,
        # то дальше можно не считать.
        if (priority["+"] != -1):
            break
    if (priority["+"] != -1):
        return {"+" : [parsing_expression(expression[:priority["+"]]),
                parsing_expression(expression[priority["+"]+1:])]}
    elif (priority["*"] != -1):
        return {"*" : [parsing_expression(expression[:priority["*"]]),
                parsing_expression(expression[priority["*"]+1:])]}
    elif (priority["/"] != -1):
        return {"/" : [parsing_expression(expression[:priority["/"]]),
                parsing_expression(expression[priority["/"]+1:])]}
    elif (priority["^"] != -1):
        return {"^" : [parsing_expression(expression[:priority["^"]]),
                parsing_expression(expression[priority["^"]+1:])]}
    # Отлично, мы разобрали случаи бинарных операций (у дерева 2 ветвления)
    # Теперь нужно смотреть на унарные.
    # К этому месту у нас остались лишь выражения f(expression)
    if expression[:3] == "sin":
        return {"sin": parsing_expression(expression[3:])}
    elif expression[:3] == "cos":
        return {"cos": parsing_expression(expression[3:])}
    elif expression[:3] == "tan":
        return {"tan": parsing_expression(expression[3:])}
    elif expression[:4] == "asin":
        return {"asin": parsing_expression(expression[4:])}
    elif expression[:4] == "acos":
        return {"acos": parsing_expression(expression[4:])}
    elif expression[:4] == "atan":
        return {"atan": parsing_expression(expression[4:])}
    elif expression[:3] == "exp":
        return {"exp": parsing_expression(expression[3:])}
    elif expression[:4] == "sqrt":
        return {"sqrt": parsing_expression(expression[4:])}
    elif expression[:2] == "ln":
        return {"ln": parsing_expression(expression[2:])}
    else:
        raise ValueError("Invalid expression: " + expression)

#%% Поиск производной.

# Идея такая. Начинаем протаскивать производную, начиная с корня. На каждом
# шаге у нас либо кусочек дерева {func:[f, g]} (ему соответствует выражение
# f func g), либо {func:f} (соответствующее выражение func(f)). В обоих случаях
# мы можем взять производную в терминах f, g, f', g' и для нее написать дерево.
# Далее запускаем эту функцию для всех f', g'.
def D(tree):
    """По дереву выражения строит дерево производной выражения."""
    # получили функцию на вершине
    func = list(tree.keys())[0]
    # случай бинарной операции
    if func in binary:
        f,g = tree[func]
        # Сначала посчитаем значение производной.
        if (type(f) != dict and (isinstance(f, (int, float)) or (f in yz))):
            Df = 0
        elif (f == "x"):
            Df = 1
        else:
            Df = D(f)
        if (type(g) != dict and
            (isinstance(g, (int, float)) or (g in yz))):
            Dg = 0
        elif (g == "x"):
            Dg = 1
        else:
            Dg = D(g)
        # Теперь пишем дерево для формулы (f func g)'
        if (func == "+"):
            # (f+g)' = f' + g'
            return {"+": [Df, Dg]}
        elif (func == "*"):
            # (fg)' = f'g + fg'
            return {"+":
                        [{"*":[Df, g]},
                         {"*":[f, Dg]}]}
        elif (func == "/"):
            # (f/g)' = f'g^(-1) - fg'g^(-2)
            return {"+":
                        [{"/":
                              [Df, {"^": [g, -1]}]},
                         {"*": [{"*" : [f, Dg]},
                                {"^" : [g, -2]}]}]}
        elif (func == "^"):
            # (f^g)' = (f^g)g'ln(f) + f'g(f^(g-1)) = Aln(f) + B
            return { "+" :
                           [{"*" : [{"^": [f, g]},
                                    {"*": [Dg, {"ln":f}]}]},
                            {"*" : [{"^" : [f,
                                                {"+":[g, -1]}]},
                                    {"*" : [g, Df]}]}]}
        else:
            print("Что-то пошло не так")
    # Случай унарной операции
    elif func in ["sin", "cos", "tan", "asin", "acos", "atan", "exp", "sqrt", "ln"]:
        f = tree[func]
        # Считаем значение производной.
        if (type(f) != dict and
            (isinstance(f, (int, float)) or (f in "yz"))):
            Df = 0
        elif (f == "x"):
            Df = 1
        else:
            Df = D(f)
        # (func(f))' = f' * func'(f) = f' * right
        if(func == "sin"):
            right = {"cos" : f}
        elif(func == "cos"):
            right = {"*": [-1, {"sin":f}]}
        elif(func == "tan"):
            right = {"^" : [{"cos":f}, -2]}
        elif(func == "asin"):
            right = {"^": [{"+":[1, {"*":[-1, {"^":[f,2]}]}]},-0.5]}
        elif(func == "acos"):
            right = {"/":[-1, {"sqrt":{"+":[1, {"*":[-1, {"^":[f,2]}]}]}}]}
        elif(func == "atan"):
            right = {"/":[1,{"+":[1, {"^":[f, 2]}]}]}
        elif(func == "exp"):
            right = {"exp": f}
        elif(func == "sqrt"):
            right = {"*":[0.5, {"^":[f, -0.5]}]}
        elif(func == "ln"):
            right = {"/": [1,f]}
        else:
            right = {}
            print("Что-то пошло не так")
        return {"*":[right, Df]}

#%% Упрощение
def simplify(tree):
    """Упрощение дерева выражений"""
    # Это условие не должно выполняться!
    if (type(tree) != dict):
        print("Это условие не должно выполняться!")
    func = list(tree.keys())[0]
    # Разбор бинарного случая
    if (func in binary):
        f,g = tree[func]
        # упрощаем
        if (type(f) == dict):
            f = simplify(f)
        if (type(g) == dict):
            g = simplify(g)
        # Считаем, что f и g максимально упрощены. Применяем к ним func
        if(func == "+"):
            if(f == 0):
                return g
            elif(g == 0):
                return f
            elif(isinstance(f, (int, float)) and isinstance(g, (int, float))):
                return (f+g)
        elif(func == "*"):
            if(f == 0 or g == 0):
                return 0
            elif(f == 1):
                return g
            elif(g == 1):
                return f
            elif(isinstance(f, (int, float)) and isinstance(g, (int, float))):
                return (f*g)
        elif(func == "/"):
            if(f == 0):
                return 0
            elif(g == 0):
                return("ERROR")
                print("Деление на 0")
            elif(g == 1):
                return f
            elif(isinstance(f, (int, float)) and isinstance(g, (int, float))):
                return (f/g)
        elif(func == "^"):
            if(f == 0 and g != 0):
                return 0
            elif(g == 0):
                return(1)
            elif(f == 1):
                return(1)
            elif(g == 1):
                return f
            elif(isinstance(f, (int, float)) and isinstance(g, (int, float))):
                return (f**g)
        return({func:[f,g]})
    # Разбор унарного случая
    if (func in unary):
        f = tree[func]
        # упрощаем
        if (type(f) == dict):
            f = simplify(f)
        # Считаем, что f максимально упрощена. Применяем к ним func
        if(f == 0):
            if func in ["sin", "tan", "asin", "atan", "sqrt"]:
                return(0)
            elif func == "exp":
                return(1)
            elif func == "ln":
                print("Деление на 0")
                return("ERROR")
        elif(f == 1):
            if func == "sqrt":
                return(1)
            elif func == "ln":
                return(0)
        else:
            return({func : f})

#%% Перевод дерева в строку

# Для уменьшения числа скобок используются следующие правила:
# 1. Унарная функция обязана быть записанной в скобках.
# 2. Для бинарной функции. пусть есть f, g, func. Если в записи f или g вне
# скобок стоят операции с не меньшим приоритетом,  чем операция func. Тогда
# для соответствующей части (или 2 частей) скобки не нужны.
def to_string(tree, min_priority = 0):
    """Переводит дерево в строковое выражение, пытаясь уменьшить количество
    скобочек.

    tree -- дерево, переводящееся в строку
    min_priority -- минимальный приоритет используемой вне скобок операции
    в записи на данный момент. Этот параметр задавать не нужно, он используется
    лишь в рекурсивных вызовах! Словарь приоритетов:
    {"+" : 0, "*" : 1, "/" : 1, "^" : 2}"""
    if (type(tree) != dict):
        # Видимо, этот случай бывает лишь когда на вход подают строку-ответ.
        return(tree, 0)
    func = list(tree.keys())[0]
    # Разбор бинарного случая
    if (func in binary):
        f,g = tree[func]
        min_priority_f = min_priority_g = 999
        # упрощаем
        if (type(f) == dict):
            f, min_priority_f = to_string(f)
        if (type(g) == dict):
            g, min_priority_g = to_string(g)
        # 2. Для бинарной функции. пусть есть f, g, func. Если в записи f или g
        # вне скобок стоят операции с не меньшим приоритетом,  чем операция
        # func. Тогда для соответствующей части (или 2 частей) скобки не нужны.
        priority = {"+" : 0, "*" : 1, "/" : 1, "^" : 2}
        p1 = (str(f) if(priority[func] <= min_priority_f)
                     else "(" + str(f) + ")")
        p2 = (str(g) if(priority[func] <= min_priority_g)
                     else "(" + str(g) + ")")
        return(p1 + func + p2, priority[func])
    if(func in unary):
        f = tree[func]
        # упрощаем
        if (type(f) == dict):
            f, min_priority_f = to_string(f)
        # 1. Унарная функция обязана быть записанной в скобках.
        return(func + "(" + str(f) + ")", 999)


#%%
if __name__ == "__main__":
    expression = "x^(x*y)"
    expression = pretreatment(expression)
    tree = parsing_expression(expression)
    D_expression = D(tree)
    simp_D = simplify(D_expression)
    ans = to_string(simp_D)[0]
    print(ans)