#!/usr/bin/env python

#DeriverTest

import re

LEFT = 1
RIGHT = 2

def is_between(v,mi,ma):
	mi = ord(mi)
	ma = ord(ma)
	v = ord(v)
	return mi <= v and ma >= v

def is_alpha(v):
	return is_between(v,'a','z')

def is_numeric(v):
	return is_between(v,'0','9')

class Operator2(object):
	priority = 0
	symbol = None
	priority_side = LEFT
	def __init__(self,left,right):
		self.left = left
		self.right = right

	def __repr__(self):
		return "(" + repr(self.left) + ") "+self.symbol+" (" + repr(self.right) + ")"

	def insert(self,id_dict,idv=None):
		return self.__class__(self.left.insert(id_dict,idv),self.right.insert(id_dict,idv))

	def __eq__(self,other):
		return self.__class__ == other.__class__ and self.left == other.left and self.right == other.right

	def is_constant(self,idv=None):
		return self.left.is_constant(idv) and self.right.is_constant(idv)

	def calc(self):
		a = self.left.calc().value
		b = self.right.calc().value

		return Numeric(self._calc(a,b))

	def _calc(self):
		raise "Error symbol %s not implemented" % self.symbol

class Addition(Operator2):
	priority = 3
	symbol = "+"

	def _calc(self,a,b):
		return a + b

class Subtraction(Operator2):
	priority = 3
	symbol = "-"

	def _calc(self,a,b):
		return a - b

class Multiplication(Operator2):
	priority = 2
	symbol = "*"

	def _calc(self,a,b):
		return a * b

class Division(Operator2):
	priority = 2
	symbol = "/"

	def _calc(self,a,b):
		return a/b

class Power(Operator2):
	priority = 1
	symbol = "^"

	def _calc(self,a,b):
		return a**b

class Numeric(object):
	def __init__(self,value):
		self.value = value

	def __repr__(self):
		return str(self.value)

	def __eq__(self,other):
		return self.__class__ == other.__class__ and self.value == other.value

	def insert(self,id_dict,idv=None):
		return self.__class__(self.value)

	def is_constant(self,idv=None):
		return True

	def calc(self):
		return self

class Var(object):
	def __init__(self,idv):
		self.idv = idv

	def insert(self,id_dict,idv=None):
		raise Exception("That shits not real")

	def is_constant(self,idv=None):
		if idv is None:
			return False
		return idv != self.idv

	def __repr__(self):
		return self.idv

	def calc(self):
		raise "Can't calculate a variable"

class Parser:
	operators2 = dict( (cls.symbol,cls) for cls in Operator2.__subclasses__() )
	@classmethod
	def parse(cls, term):
		if len(term) == 0:
			raise Exception("shit's empty")

		if len(term) == 1 and is_alpha(term):
			return Var(term)

		try:
			numeric_value = float(term)
			return Numeric(numeric_value) #return Numeric if term is numeric
		except ValueError:
			pass

		brackets_counter = 0
		operator_match = (-1,None)

		for index,char in enumerate(term):
			if char == "(":
				brackets_counter+=1
			elif char == ")":
				brackets_counter-=1
				if brackets_counter < 0:
					raise Exception("Bracket error")
			elif char in cls.operators2 and brackets_counter == 0:
				operator_found = cls.operators2[char]
				if operator_match[0] < 0 or operator_found.priority > operator_match[1].priority:
					operator_match = (index,operator_found)

		if operator_match[0] >= 0:
			return operator_match[1]( Parser.parse( term[:operator_match[0]] ), Parser.parse( term[operator_match[0]+1:] ) )

		if term[0] == "(" and term[-1] == ")":
			return Parser.parse(term[1:-1])

		raise Exception("WTF is this shit %s" % term)

class IdMark:
	def __init__(self,idv,constant=False):
		self.idv = idv
		self.constant = constant

	def insert(self,id_dict,idv):
		return id_dict[self.idv]

	def __repr__(self):
		if self.constant:
			return "IDC[%s]" % self.idv
		else:
			return "ID[%s]" % self.idv

class DeriveVarIdMark:
	def insert(self,id_dict,idv):
		return Var(idv)

	def __repr__(self):
		return "X[]"

class DerivationMark:
	def __init__(self,content):
		self.content = content

	def insert(self,id_dict,idv):
		return Deriver.derive(self.content.insert(id_dict,idv),idv)

class DRule:
	def __init__(self,pattern,skeleton):
		self.pattern = pattern
		self.skeleton = skeleton

	def test(self,term,idv):
		queue = [(self.pattern,term)]
		id_dict = {}
		while len(queue) != 0:
			vpattern,vterm = queue[0]
			queue = queue[1:]

			if vpattern.__class__ == IdMark:
				if vpattern.constant and not vterm.is_constant(idv):
					return None
				elif vpattern.idv in id_dict:
					if id_dict[vpattern.idv] != vterm:
						return None
				else:
					id_dict[vpattern.idv] = vterm
			elif vpattern.__class__ == DeriveVarIdMark:
				if not (vterm.__class__ == Var and vterm.idv == idv):
					return None
			elif vpattern.__class__ == vterm.__class__:
				queue.append( (vpattern.left,vterm.left) )
				queue.append( (vpattern.right,vterm.right) )
			else:
				return None

		return id_dict

class Deriver:
	rules = [
		DRule( #dc/dx = 0 / c const
			IdMark("c",constant=True),
			Numeric(0)
		),
		DRule( #d/dx (a+b) = da/dx + db/dx
			Addition(IdMark("x"),IdMark("y")),
			Addition(DerivationMark(IdMark("x")),DerivationMark(IdMark("y")))
		),
		DRule( #d/dx (a-b) = da/dx - db/dx
			Subtraction(IdMark("a"),IdMark("b")),
			Subtraction(DerivationMark(IdMark("a")),DerivationMark(IdMark("b")))
		),
		DRule( #d/dx (c*a) = c * da/dx
			Multiplication(IdMark("c",constant=True),IdMark("x")),
			Multiplication(IdMark("c"), DerivationMark(IdMark("x")) )
		),
		DRule( #dx/dx = 1
			DeriveVarIdMark(),
			Numeric(1)
		),
		DRule( #d/dx (x^c) = c * x ^ (c-1)
			Power( DeriveVarIdMark(), IdMark("c",constant=True) ),
			Multiplication(
				IdMark("c"),
				Power(
					DeriveVarIdMark(),
					Subtraction(
						IdMark("c"),
						Numeric(1)
					)
				)
			)
		),
		DRule( #d/dx (a*b) = a * db/dx + b * da/dx
			Multiplication( IdMark("a"), IdMark("b") ),
			Addition(
				Multiplication(
					IdMark("a"),
					DerivationMark( IdMark("b") )
				),
				Multiplication(
					IdMark("b"),
					DerivationMark( IdMark("a") )
				)
			)
		),
		DRule( #d/dx (a/b) = (da/dx * b - a * db/dx)/b^2
			Division(
				IdMark("a"),
				IdMark("b")
			),
			Division(
				Subtraction(
					Multiplication(
						DerivationMark( IdMark("a") ),
						IdMark("b")
					),
					Multiplication(
						IdMark("a"),
						DerivationMark( IdMark("b") )
					)
				),
				Power(
					IdMark("b"),
					Numeric(2)
				)
			)
		)
	]

	@classmethod
	def derive(cls,term,idv):
		for rule in cls.rules:
			id_dict = rule.test(term,idv)
			if id_dict is not None:
				return rule.skeleton.insert(id_dict,idv)

		raise Exception("Couldn't derive %s" % term)

class SRule:
	def __init__(self,pattern,applier):
		self.pattern = pattern
		self.applier = applier

class Simplifier:
	@staticmethod
	def simplify(term):
		if term.is_constant():
			return term.calc()
		elif isinstance(term,Operator2):
			print ( term.__class__.__name__ )

			sleft = Simplifier.simplify(term.left)
			sright = Simplifier.simplify(term.right)
			term = term.__class__(sleft,sright)

			if term.left.is_constant():
				tleft = term.left.calc()
			else:
				tleft = term.left

			if term.right.is_constant():
				tright = Simplifier.simplify(term.right.calc())
			else:
				tright = term.right

			return term.__class__(tleft,tright)
		else:
			return term

sterm = input("Input term (deriving by x): ")

term = Parser.parse(sterm)
print ( "Deriving %s" % term )
dterm = Deriver.derive(term,"x")
print ( "DTerm: %s" % dterm )
sterm = Simplifier.simplify(dterm)
print ( "Result: %s" % sterm )