derivatives

import collections
import math
import re

class Tree:
    class Position:
        def element(self):
            raise NotImplementedError('must be implemented by subclass')

        def __eq__(self, other):
            raise NotImplementedError('must be implemented by subclass')

        def __ne__(self, other):
            return not (self == other)

    def root(self):
        raise NotImplementedError('must be implemented by subclass')

    def parent(self, p):
        raise NotImplementedError('must be implemented by subclass')

    def num_children(self, p):
        raise NotImplementedError('must be implemented by subclass')

    def children(self, p):
        raise NotImplementedError('must be implemented by subclass')

    def __len__(self):
        raise NotImplementedError('must be implemented by subclass')

    def is_root(self, p):
        return self.root() == p

    def is_leaf(self, p):
        return self.num_children(p) == 0

    def is_empty(self):
        return len(self) == 0

    def depth(self, p):
        if self.is_root(p):
            return 0
        else:
            return 1 + self.depth(self.parent(p))

    def _height1(self):
        return max(self.depth(p) for p in self.positions() if self.is_leaf(p))

    def _height2(self, p):
        if self.is_leaf(p):
            return 0
        else:
            return 1 + max(self._height2(c) for c in self.children(p))

    def height(self, p=None):
        if p is None:
            p = self.root()
        return self._height2(p)

    def __iter__(self):
        for p in self.positions():
            yield p.element()

    def positions(self):
        return self.preorder()

    def preorder(self):
        if not self.is_empty():
            for p in self._subtree_preorder(self.root()):
                yield p

    def _subtree_preorder(self, p):
        yield p
        for c in self.children(p):
            for other in self._subtree_preorder(c):
                yield other

    def postorder(self):
        if not self.is_empty():
            for p in self._subtree_postorder(self.root()):
                yield p

    def _subtree_postorder(self, p):
        for c in self.children(p):
            for other in self._subtree_postorder(c):
                yield other
        yield p

class BinaryTree(Tree):
    def left(self, p):
        raise NotImplementedError('must be implemented by subclass')

    def right(self, p):
        raise NotImplementedError('must be implemented by subclass')

    def sibling(self, p):
        parent = self.parent(p)
        if parent is None:
            return None
        else:
            if p == self.left(parent):
                return self.right(parent)
            else:
                return self.left(parent)

    def children(self, p):
        if self.left(p) is not None:
            yield self.left(p)
        if self.right(p) is not None:
            yield self.right(p)

    def inorder(self):
        if not self.is_empty():
            for p in self._subtree_inorder(self.root()):
                yield p

    def _subtree_inorder(self, p):
        if self.left(p) is not None:
            for other in self._subtree_inorder(self.left(p)):
                yield other
        yield p
        if self.right(p) is not None:
            for other in self._subtree_inorder(self.right(p)):
                yield other

    def positions(self):
        return self.inorder()

class LinkedBinaryTree(BinaryTree):
    class _Node:
        __slots__ = '_element', '_parent', '_left', '_right'

        def __init__(self, element, parent=None, left=None, right=None):
            self._element = element
            self._parent = parent
            self._left = left
            self._right = right

    class Position(BinaryTree.Position):
        def __init__(self, container, node):
            self._container = container
            self._node = node

        def element(self):
            return self._node._element

        def __eq__(self, other):
            return type(other) is type(self) and other._node is self._node

    def _validate(self, p):
        if not isinstance(p, self.Position):
            raise TypeError('p must be proper Position type')
        if p._container is not self:
            raise ValueError('p does not belong to this container')
        if p._node._parent is p._node:  # convention for deprecated nodes
            raise ValueError('p is no longer valid')
        return p._node

    def _make_position(self, node):
        return self.Position(self, node) if node is not None else None

    # -------------------------- konstruktor drzewa --------------------------
    def __init__(self):
        self._root = None
        self._size = 0

    def __len__(self):
        return self._size

    def root(self):
        return self._make_position(self._root)

    def parent(self, p):
        node = self._validate(p)
        return self._make_position(node._parent)

    def left(self, p):
        node = self._validate(p)
        return self._make_position(node._left)

    def right(self, p):
        node = self._validate(p)
        return self._make_position(node._right)

    def num_children(self, p):
        node = self._validate(p)
        count = 0
        if node._left is not None:
            count += 1
        if node._right is not None:
            count += 1
        return count

    def _add_root(self, e):
        if self._root is not None:
            raise ValueError('Root exists')
        self._size = 1
        self._root = self._Node(e)
        return self._make_position(self._root)

    def _add_left(self, p, e):
        node = self._validate(p)
        if node._left is not None:
            raise ValueError('Left child exists')
        self._size += 1
        node._left = self._Node(e, node)
        return self._make_position(node._left)

    def _add_right(self, p, e):
        node = self._validate(p)
        if node._right is not None:
            raise ValueError('Right child exists')
        self._size += 1
        node._right = self._Node(e, node)
        return self._make_position(node._right)
    def _replace(self, p, e):
        node = self._validate(p)
        old = node._element
        node._element = e
        return old

    def _delete(self, p):
        node = self._validate(p)
        if self.num_children(p) == 2:
            raise ValueError('Position has two children')
        child = node._left if node._left else node._right  # might be None
        if child is not None:
            child._parent = node._parent  # child's grandparent becomes parent
        if node is self._root:
            self._root = child  # child becomes root
        else:
            parent = node._parent
            if node is parent._left:
                parent._left = child
            else:
                parent._right = child
        self._size -= 1
        node._parent = node  # convention for deprecated node
        return node._element

    def _attach(self, p, t1, t2):
        node = self._validate(p)
        if not self.is_leaf(p):
            raise ValueError('position must be leaf')

        if t1 is not None:
            if not isinstance(t1, type(self)):
                t1 = self._convert_tree(t1)
            self._size += len(t1)
            if not t1.is_empty():
                t1._root._parent = node
                node._left = t1._root
                t1._root = None
                t1._size = 0

        if t2 is not None:
            if not isinstance(t2, type(self)):
                t2 = self._convert_tree(t2)
            self._size += len(t2)
            if not t2.is_empty():
                t2._root._parent = node
                node._right = t2._root
                t2._root = None
                t2._size = 0


    def _convert_tree(self, other_tree):
        """Konwersja drzewa do bieżącego typu drzewa."""
        new_tree = None
        for p in other_tree.positions():
            # Przejdź przez pozycje w innym drzewie i skopiuj je do nowego drzewa
            if other_tree.is_root(p):
                new_tree = type(self)(p.element())
            else:
                parent_pos = new_tree.positions()[other_tree.depth(p)-1]
                parent_node = self._validate(parent_pos)
                if other_tree.left(other_tree.parent(p)) == p:
                    new_tree._add_left(parent_node, p.element())
                else:
                    new_tree._add_right(parent_node, p.element())
        return new_tree


    def _clone_node(self, other_node, tree_class):
        """Klonuje pojedynczy węzeł do bieżącego typu drzewa."""
        if other_node is None:
            return None
        return tree_class(other_node.element())


class ExpressionTree(LinkedBinaryTree):
    def __init__(self, token, left=None, right=None):
        super().__init__()
        if not isinstance(token, str):
            raise TypeError('Token must be a string')

        # Dodaj korzeń drzewa
        self._add_root(token)

        # Jeśli left i right są podane, dołącz je jako poddrzewa
        if left is not None or right is not None:
            # Konwertuj left i right na ExpressionTree, jeśli są stringami
            if left is not None and not isinstance(left, ExpressionTree):
                left = ExpressionTree(left)
            if right is not None and not isinstance(right, ExpressionTree):
                right = ExpressionTree(right)

            self._attach(self.root(), left, right)

    def __str__(self):
        pieces = []
        self._parenthesize_recur(self.root(), pieces)
        return ''.join(pieces)

    def _parenthesize_recur(self, p, result):
        if self.is_leaf(p):
            result.append(str(p.element()))
        else:
            result.append('(')
            self._parenthesize_recur(self.left(p), result)
            result.append(p.element())
            self._parenthesize_recur(self.right(p), result)
            result.append(')')

class ExtendedExpressionTree(ExpressionTree):
    def __init__(self, token, left=None, right=None):
        super().__init__(token, left, right)
        self._extended_operators = {'sin', 'cos', 'exp', 'ln'}

    def evaluate_recur(self, p):
        if p.element() in self._extended_operators:
            if p.element() == 'sin':
                return math.sin(self.evaluate_recur(self.left(p)))
            elif p.element() == 'cos':
                return math.cos(self.evaluate_recur(self.left(p)))
            elif p.element() == 'exp':
                return math.exp(self.evaluate_recur(self.left(p)))
            elif p.element() == 'ln':
                return math.log(self.evaluate_recur(self.left(p)))
        else:
            return super().evaluate_recur(p)

def tokenize(raw):
    SYMBOLS = set('+-*/^() ')
    FUNCTIONS = {'sin', 'cos', 'exp', 'log'}
    tokens = []
    n = len(raw)
    i = 0
    while i < n:
        if raw[i] in SYMBOLS:
            if raw[i] != ' ':
                tokens.append(raw[i])
            i += 1
        else:
            if raw[i:i+3] in FUNCTIONS:
                j = raw.find('(', i)
                if j != -1:
                    end = raw.find(')', j)
                    if end != -1:
                        tokens.append(raw[i:end+1])
                        i = end + 1
                        continue
            j = i
            while j < n and raw[j] not in SYMBOLS:
                j += 1
            tokens.append(raw[i:j])
            i = j
    return tokens



def build_expression_tree(tokens):
    S = []
    for t in tokens:
        if t in '+-*/':
            S.append(t)  # Dodaj operator do stosu
        elif t not in '()':
            # Jeśli to nie operator i nie nawias, utwórz drzewo z pojedynczym węzłem
            S.append(ExpressionTree(t))
        elif t == ')':
            right = S.pop()  # Zdejmij prawe poddrzewo
            op = S.pop()     # Zdejmij operator
            left = S.pop()   # Zdejmij lewe poddrzewo

            # Sprawdź, czy operator jest ciągiem znaków
            if not isinstance(op, str):
                print("Stos:", S)
                print("Oczekiwano operatora, ale otrzymano:", op)
                raise TypeError("Operator must be a string")

            # Utwórz nowe drzewo z lewym i prawym poddrzewem
            S.append(ExpressionTree(op, left, right))
    return S.pop()





def _derivative_recur(tree, node, var, tree_class):
    if tree.is_leaf(node):
        if node.element() == var:
            return tree_class('1')
        else:
            return tree_class('0')

    op = node.element()
    left = tree.left(node) if tree.left(node) else None
    right = tree.right(node) if tree.right(node) else None

    if op == '+':
        left_derivative = _derivative_recur(tree, left, var, tree_class) if left else None
        right_derivative = _derivative_recur(tree, right, var, tree_class) if right else None
        return tree_class('+', left_derivative, right_derivative)

    elif op == '-':
        left_derivative = _derivative_recur(tree, left, var, tree_class) if left else None
        right_derivative = _derivative_recur(tree, right, var, tree_class) if right else None
        return tree_class('-', left_derivative, right_derivative)

    elif op == '*':
        left_derivative = _derivative_recur(tree, left, var, tree_class) if left else None
        right_derivative = _derivative_recur(tree, right, var, tree_class) if right else None
        return tree_class('+',
                          tree_class('*', left_derivative, tree._clone_node(right, tree_class)),
                          tree_class('*', tree._clone_node(left, tree_class), right_derivative))

    elif op == '/':
        left_derivative = _derivative_recur(tree, left, var, tree_class) if left else None
        right_derivative = _derivative_recur(tree, right, var, tree_class) if right else None
        num = tree_class('-',
                         tree_class('*', left_derivative, tree._clone_node(right, tree_class)),
                         tree_class('*', tree._clone_node(left, tree_class), right_derivative))
        den = tree_class('^', tree._clone_node(right, tree_class), '2')
        return tree_class('/', num, den)

    elif op == '^':
        if right and tree.is_leaf(right) and right.element().isdigit():
            new_exponent = str(int(right.element()) - 1)
            left_derivative = _derivative_recur(tree, left, var, tree_class)
            return tree_class('*',
                              tree_class('*', right, left_derivative),
                              tree_class('^', tree._clone_node(left, tree_class), new_exponent))

    elif op in {'sin', 'cos', 'exp', 'ln'} and isinstance(tree, ExtendedExpressionTree):
        left_derivative = _derivative_recur(tree, left, var, tree_class)
        if op == 'sin':
            return tree_class('*', tree_class('cos', tree._clone_node(left, tree_class)), left_derivative)
        elif op == 'cos':
            return tree_class('*', tree_class('-', tree_class('0'), tree_class('sin', tree._clone_node(left, tree_class))), left_derivative)
        elif op == 'exp':
            return tree_class('*', tree_class('exp', tree._clone_node(left, tree_class)), left_derivative)
        elif op == 'ln':
            return tree_class('*', tree_class('/', tree_class('1'), tree._clone_node(left, tree_class)), left_derivative)

    else:
        return None  # Dla nierozpoznanych przypadków

    return None




def derivative_of_tree(tree, var='x'):
    root = tree.root()
    tree_class = type(tree)
    derivative = _derivative_recur(tree, root, var, tree_class)

    # Sprawdź, czy drzewo pochodnej nie jest puste
    if derivative.is_empty():
        return derivative
    else:
        # Tworzymy nowe drzewo z elementami, a nie z pozycjami
        left_element = derivative.left(derivative.root()).element() if derivative.left(derivative.root()) else None
        right_element = derivative.right(derivative.root()).element() if derivative.right(derivative.root()) else None
        return tree_class(derivative.root().element(),
                          ExpressionTree(left_element) if left_element is not None else None,
                          ExpressionTree(right_element) if right_element is not None else None)


def tree_to_string(tree):
    def _to_string(node):
        if tree.is_leaf(node):
            return node.element()
        left = _to_string(tree.left(node)) if tree.left(node) else ""
        right = _to_string(tree.right(node)) if tree.right(node) else ""
        return f"({left}{node.element()}{right})" if left or right else node.element()

    return _to_string(tree.root())


expression = "((x/2)-y)"
tokens = tokenize(expression)
expr_tree = build_expression_tree(tokens)
derivative_tree = derivative_of_tree(expr_tree)
derivative_expression = tree_to_string(derivative_tree)
print("Expression:", expression)
print("Pochodna:", derivative_expression)