# -*- coding: UTF-8 -*-

'''
Created on 2017年6月8日

@author: YangTongfeng

二元运算符 特殊方法
+ __add__,__radd__
- __sub__,__rsub__
* __mul__,__rmul__
/ __div__,__rdiv__,__truediv__,__rtruediv__
// __floordiv__,__rfloordiv__
% __mod__,__rmod__
** __pow__,__rpow__
<< __lshift__,__rlshift__
>> __rshift__,__rrshift__
& __and__,__rand__
^ __xor__,__rxor__
| __or__,__ror__
+= __iaddr__
-= __isub__
*= __imul__
/= __idiv__,__itruediv__
//= __ifloordiv__
%= __imod__
**= __ipow__
<<= __ilshift__
>>= __irshift__
&= __iand__
^= __ixor__
|= __ior__
== __eq__
!=,<> __ne__
> __get__
< __lt__
>= __ge__
<= __le__

'''
#表达式树的节点类
class E:
 global_index = 0;
 def __init__(self):
 self.index = E.global_index;
 E.global_index = E.global_index+1;
 self.left=None;#指向左子树的指针(左子树)
 self.right=None;#指向右子树的指针(右子树)
 self.parent = None;#指向父节点(暂不可用)
 self.type = 'n';
 self.f = 0;
 pass
 def isOp(self,op):#判断是不是一个Op符号节点
 return self.type == 'op' and self.f == op;

 def isZero(self):#判断是不是一个'0'节点
 return self.type == 'float' and abs(self.f) < 1e-5;
 def isOne(self):#判断是不是一个'1'节点
 return self.type == 'float' and abs(self.f -1 ) < 1e-5;
 def isNum(self):#判断是不是一个数字节点
 return self.type == 'float';
 def float(self,a): #将该节点设置为常数节点并将常数放入
 self.f = a;
 self.left = self.right = None;
 self.type = 'float';
 return self;
 def sym(self,name): #将该节点设置为符号节点(如:x,y)
 self.type = 'sym';
 self.f = name;
 return self;
 def withOp(self,op,left,right):#将该节点设置为运算符节点
 self.f = op;
 self.type = 'op';

 if type(left) == int or type(left) == float:
 left = E().float(left);

 if type(right) == int or type(right) == float:
 right = E().float(right);

 if left != None:
 self.left = left.clone();
 self.left.parent = self;
 else:
 self.left =None;
 if right != None:
 self.right = right.clone();
 self.right.parent = self;
 else:
 self.right = None;
 return self;
 def clone(self): #深度复制
 x = E();
 x.type = self.type;
 x.f = self.f;
 if self.left == None:
 x.left = None;
 else:
 x.left = self.left.clone();

 if self.right == None:
 x.right = None;
 else:
 x.right = self.right.clone();
 return x;

 def __radd__(self,x):#形如(3+E)这样的操作
 #print '__radd__ ',x
 r = E().withOp('+', x,self);
 return r;
 def __rsub__(self,x):#形如(3-E)这样的操作
 #print '__rsub__ ',x
 r = E().withOp('-', x,self);
 return r;
 def __rmul__(self,x):
 r = E().withOp('*', x,self);
 return r;
 def __rdiv__(self,x):
 r = E().withOp('/', x,self);
 return r;
 def __neg__(self): 
 r = E().withOp('*', E().float(-1),self);
 return r;
 def __add__(self,x):
 #print 'add ',x
 r = E().withOp('+', self, x);
 return r;
 def __sub__(self,x):
 r = E().withOp('-', self, x);
 return r;
 def __mul__(self,x):
 r = E().withOp('*', self, x);
 return r;
 def __div__(self,x):
 r = E().withOp('/', self, x);
 return r;
 def __pow__(self,x):
 r = E().withOp('^', self, x);
 return r;

 def isConstOf(self,x): # 求导时,对于x是否是一个常数
 if self.type == 'float':
 return True;
 if self.type == 'sym' :
 return self.f == x.f;

 return (self.left == None or self.left.isConstOf(x)) and (self.right == None or self.right.isConstOf(x));

 def op_diff(self,x):#对运算符节点进行求导
 # do something with None left or right
 if self.left == None:
 d_left =None;
 else:
 d_left = self.left.diff(x);
 if self.right == None:
 d_right = None;
 else:
 d_right = self.right.diff(x);

 if self.f == '+':
 return d_left+d_right;
 if self.f == '-':
 return d_left-d_right;
 if self.f == '*':
 return d_left*self.right+self.left*d_right;
 if self.f == '/':
 return (d_left*self.right-self.left*d_right)/(self.right*self.right);
 if self.f == '^':
 left_c = d_left == E().float(0);
 right_c = d_right == E().float(0);

 if left_c and right_c :
 return E().float(0);
 elif right_c: # f(x)^a ()' = a*f(x)^(a-1)*f'(x);
 return self.right*self.left**(self.right-1)*d_left;
 elif left_c: #指数 a^g(x) ()' = a^g(x)*loga*g'(x)
 return self.left**self.right * self.left.log() * d_right;
 else:
 #print 'unsupport f(x)^g(x) style!! now ' ;
 return (self.left**self.right)*( d_right*self.left + self.right/self.left*d_left );
 #exit(1);
 pass
 def diff(self,x): # 对x求偏导数
 if self.type == 'float':
 return E().float(0);
 elif self.type == 'sym':
 if x.f == self.f: # 是同一个变量
 return E().float(1);
 else:
 return E().float(0); #不是同一个变量。
 elif self.type == 'op':
 return self.op_diff(x);


 pass
 def eq(self,x,y):
 if x == None :
 return y == None;
 else :
 return x == y;
 def __eq__(self,x):
 if x == None:
 return False;
 if x.type != self.type:
 return False;
 if x.type == 'float':
 return abs(x.f - self.f)<1e-5;
 if x.type == 'sym':
 return x.f == self.f;
 if x.type == 'op':
 if x.f != self.f :
 return False;
 return self.eq(self.left,x.left) and self.eq(self.right,x.right);
 def printme(self):
 self.setParent();
 self._printme();
 print '';
 def printnodes(self):
 #前序打印所有节点
 print '[' ,self.index , self.type ,",",self.f ,;
 if self.parent != None:
 print 'parent = ',self.parent.index, ;
 print '';
 if self.left != None :
 self.left.printnodes();
 if self.right != None :
 self.right.printnodes();
 
 def _op_toi(self,op):
 if op == '+' or op == '-':
 return 10;
 if op == '*' or op == '/':
 return 20;
 if op == '^':
 return 30;
 return 40;
 def _compare_op(self,a,b): #比较两个符号,谁的优先级高
 #print 'compare ',a,b,self._op_toi(a) - self._op_toi(b);
 return self._op_toi(a) - self._op_toi(b);
 def _printme(self):
 if self.type == 'float':
 print self.f ,;
 elif self.type == 'op':
 useBrack = True;
 if self.parent == None:
 useBrack = False;
 elif self._compare_op(self.f, self.parent.f)>= 0:
 useBrack = False;


 if useBrack:
 print '(',;
 #如果是 -1*x ,直接输出 -x;
 if self.left !=None and self.left == E().float(-1) and self.isOp('*'):
 print '-',;
 else:
 if self.left !=None:
 self.left._printme();
 print self.f ,;
 if self.right != None:
 self.right._printme();
 if useBrack:
 print ')',;
 elif self.type == 'sym':
 print self.f ,;
 pass

 
 def child_pattern(self,x):#获取节点模板
 if x == None:
 return 'none';
 if x.left == None:
 lc= "N";
 elif x.left.isOne():
 lc = '1';
 elif x.left.isZero():
 lc = '0';
 elif x.left.type == 'float':
 lc = 'F';
 else:
 lc ='A';

 if x.right == None:
 rc= "N";
 elif x.right.isOne():
 rc = '1';
 elif x.right.isZero():
 rc = '0';
 elif x.right.type == 'float':
 rc = 'F';
 else :
 rc ='A';



 pt= str(lc)+str(x.f) + str(rc);
 #print "PT=",pt," -------------";
 #x.printme();

 return pt;


 def evalue(self,op,a,b):#计算a op b 的值
 if op == '+':
 r= a.f+b.f;
 if op == '-':
 r= a.f-b.f;
 if op == '*':
 r= a.f*b.f;
 if op == '/':
 r= a.f/b.f;
 return r;

 def _node_op(self,r,op,v):
 # 在以r为根的树中,查找一个满足从根r到该节点整条路径上节点都与op相同的float节点,并将v中的数据应用op进去。
 if r == None :
 return False;
 if r.type == 'float' : # 如果当前节点就是一个float节点,把v的值乘在这里。
 r.f = r.evalue(op,r,v);
 return True;

 if r.type != 'op' or r.f != op: #当前节点不满足op相等条件
 return False;

 if self._node_op(r.left, op, v):
 return True;

 if self._node_op(r.right, op, v):
 return True;

 return False;

 pass
 def _node_join(self,r,x,y):
 #合并两个节点 2+(2+x) => 4+x;
 #r 如果不能合并应返回的值
 #x 判断x是否是一个数字,如果是,则看能否和y中节点合并
 if x==None or y == None or x.type != 'float' :
 return r;

 succ = self._node_op(y, r.f, x); #如果成功将x乘进了y,则删除x,把y作为父。
 if succ:
 return y;
 return r;
 #在y中查找
# if y.type == 'op' and y.type == r.type and y.f == r.f:
# if y.left != None and y.left.type=='float':
# y.left.f = self.evalue(y.f, x, y.left);
# 
# return y;
# if y.right != None and y.right.type=='float':
# y.right.f = self.evalue(y.f, x, y.right);
# return y;
# 
# return r;

 def _opt_node(self,x):#优化操作符节点的函数
 #左子树 0,1检测
 r = x;
 if x == None :
 return x;

 pt = self.child_pattern(x);
 if pt == 'F-1':
 pt = pt; # for debug(已解决)

 if pt == '0*A' or pt == '0/A' or pt== 'A*0':#优化操作符左右含'0'的乘除算式
 r = E().float(0);
 if pt == '0+A' or pt == '0+1':#优化'0'的左结合操作
 r = x.right;
 if pt == 'A+0' or pt == '1+0':#优化'0'的右结合操作
 r = x.left;
 if pt == 'A*1' :#优化'1'的右结合操作
 r = x.left;
 if pt == '1*A' :#优化'1'的左结合操作
 r = x.right;

 #左子树常数化简
 pt = self.child_pattern(x);
 pt = pt.replace('0', 'F').replace('1','F');
 #print '#####', pt;

 if pt == 'F+F':
 r = E().float(x.left.f+x.right.f);
 if pt == 'F-F':
 r = E().float(x.left.f-x.right.f);
 if pt == 'F*F':
 r = E().float(x.left.f*x.right.f);
 if pt == 'F/F':
 r = E().float(x.left.f/x.right.f);
 return r;
 def optm(self): # 优化式子
 # 后续遍历,从下往上优化
 if self.left!= None:
 self.left = self.left.optm();
 if self.right!=None:
 self.right = self.right.optm();

 self.left = self._opt_node(self.left);
 self.right = self._opt_node(self.right);

 r = self._opt_node(self);

 # 0-x -> -1*x
 if self.isOp('-'):
 if self.left!=None and self.left == E().float(0):
 self.f = '*';
 self.left = E().float(-1);


 #优化常数项(多个常数项相乘,如2*3*x ->6*x)
 r = self._node_join(r,r.left,r.right);
 r = self._node_join(r,r.right,r.left);

 if r.left != None and r.left == r.right:
 if r.isOp('*'):
 r.f = '^';
 r.right = E().float(2);


 #优化乘方
 if r.isOp('^') and r.right != None and r.right.isOne():
 return r.left;
 #r=self._optm_yuefen(r);

 return r;
 pass

 #求以e为底的对数
 def log(self):
 if self.type == 'sym' and self.f == 'e':
 return E().float(1);
 r = E().withOp('log', None, self);
 return r;

 #设置所有parent指针

 def setParent(self):
 if self.left !=None :
 self.left.parent = self;
 self.left.setParent();
 if self.right != None:
 self.right.parent = self;
 self.right.setParent();
 # TODO
 # 添加一个方法,优化约分问题。 在树中递归查找‘/'节点,在此节点的向左子树中查找因子,对于所有的因子,都到右字数中查找是否有这样的因子。
 # 查找因子的方法, 在左子树中找因子,就是通过遍历的方法找到所有 操作符为* ,且从此节点开始到 '/'节点之前的所有节点都是 *
 # http://img.blog.csdn.net/20170609101712489?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVGFpSmkxOTg1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
 

pass