print(` Version of Oct 10, 2004`):
print(`This is to find the avoid pair generating functions, A Maple package`):
print(`automatically find the generating function for a given`):
print(`set and avoided pairs.`):
print(`Written by Xiangdong Wen and Doron Zeilberger.`):
lprint(``):
print(`For general help, and a list of the available functions,`):
print(` type ezra();. For specific help type ezra(procedure_name) `):
lprint(``):

ezra:=proc()
if args=NULL then
print(`NONCOMM,`):
print(`A Maple package include two parts, one(AvoidPairs) to find the generating function avoid special pairs, `):
print(`another(NonCommGJ) find the generating function using non communitive Goulden Jackson method`):
print(`This package contains Procedures: `):
print(` NonCommGJ,AvoidPairs,MySolve,MyExpand,MyExplicitForm,`):
print(` GetEquAP,GetVarAP,GetEquGJ,GetVarGJ`):
print(` For specific help type ezra(procedure_name) `):
fi:
   
if nops([args])=1 and op(1,[args])=`GetEquAP` then
print(`GetEquAP(s,p,A,x) is a function finding equations`):
print(`in the set s and avoiding pairs p`):
print(` Example:GetEquAP([1,2,3],[[1,1],[2,2],[3,3],[1,3]],A,x)`):
fi:

if nops([args])=1 and op(1,[args])=`GetVarAP` then
print(`GetVarAP(s,A) is a function finding equations`):
print(`in the set s `):
print(` Example:GetVarAP([1,2,3],A)`):
fi:

if nops([args])=1 and op(1,[args])=`GetEquGJ` then
print(`GetEquGJ(s,p,A,x) is a function finding equations`):
print(`in the set s and avoiding pairs p`):
print(` Example:GetEquGJ([[1,2,3],[2,3,1],[3,1,2]],C,s)`):
fi:

if nops([args])=1 and op(1,[args])=`GetVarGJ` then
print(`GetVarGJ(s,A) is a function finding equations`):
print(`in the set s `):
print(` Example:GetVarGJ([[1,2,3],[2,3,1],[3,1,2]],A)`):
fi:


if nops([args])=1 and op(1,[args])=`AvoidPairs` then
print(`AvoidPairs(s,p,A,x) is a function finding the generating function`):
print(`in the set s and avoiding pairs p`):
print(` Example:AvoidPairs([1,2,3],[[1,1],[2,2],[3,3],[1,3]],A,x)`):
fi:

if nops([args])=1 and op(1,[args])=`NonCommGJ` then
print(`NonCommGJ(n,MISTAKES,s) is a function finding the generating function`):
print(`with n alphabetas and avoiding MISTAKES`):
print(` Example:NonCommGJ(3,[[1,2,3],[2,3,1]],s)`):
fi:

if nops([args])=1 and op(1,[args])=`MySolve` then
print(`MySolve is a non communicative solve function`):
print(`MySolve(equ,var)`):
print(` example1 : MySolve([a . x = b],[x])`):
print(` example2 : MySolve([a[1] . x[1]  + b[1] . x[2] - c[1],  a[2] . x[1]  + b[2] . x[2] - c[2]],[x[1],x[2]])`):

fi:


if nops([args])=1 and op(1,[args])=`MyExpand` then
print(`MyExpand is a non communicative expand function`):
print(`MyExpand(expr)`):
print(` example1 : MyExpand((a+b) . (c+d))`):
print(` example2 : MyExpand((a+b)^3)`):

fi:
if nops([args])=1 and op(1,[args])=`MyExplicitForm` then
print(`MyExplicitForm(expr)  try to returns the explicit form of the expr`):
print(` example1 : MyExplicitForm(1/(a-(1/(1+a))))`):

fi:
end:






with(LinearAlgebra):
############################################################
NonCommGJ:=proc(n,MISTAKES,s)
local equ,var,lu,i,v:
equ:=GetEquGJ(MISTAKES,C,s):
var:=GetVarGJ(MISTAKES,C):
var:=MySolve(equ,var):
lu:=1:
for i from 1 to n do
lu:=lu-s[[i]]:
od:

for i from 1 to nops(MISTAKES) do
v:=op(i,MISTAKES):
lu:=lu - subs({op(var)},C[v]):
od:
(1/lu):
end:
###########################################################
GetEquGJ:=proc(B,C,s)
local u,v,p,tempequ,ans,i,j,k:
ans:=[]:
for i from 1 to nops(B) do 
   u:=op(i,B):
    p:=1:
    for j from 1 to nops(u) do
        p:=p . s[[op(j,u)]]:
    od: 
    tempequ:=C[u]+p: 
    for j from 1 to nops(B) do
       v:=op(j,B):
       tempequ:=tempequ + NonCommOverlap(u,v,s) . C[v]:
    od:
    ans:=[op(ans),tempequ]:
od:

ans:
end:
##############################################################
GetVarGJ:=proc(B,C)
local i,ans:
ans:=[]:
for i from 1 to nops(B) do
ans:=[op(ans),C[op(i,B)]]:
od:
ans:
end:

################################################################
NonCommOverlap:=proc(u,v,s)
local i,j,lu,gug,k:
lu:=0:
for i from 2 to nops(u) do
    for j from i to nops(u) while (j-i+1<=nops(v) and op(j,u)=op(j-i+1,v))
    do
      :
    od:   
 
    if j-i=nops(v) and u<>v then
        ERROR(v,`is a subword of`,u,`illegal input`):
    fi:

   if j=nops(u)+1 and (i>1 or j>2) then
      gug:=1:
 
      for k from 1 to i-1 do
      gug:=gug . s[[op(k,u)]]:
      od:

      lu:=lu+gug:
 
    fi: 
od:
lu:
end:

#############################################################
GetEquAP:=proc(s,pairs,A,x)
local i,j,result,equ:
result:=[];

for i from 1 to nops(s) do

equ:=x[[s[i]]]:

for j from 1 to nops(s) do
equ:=equ+x[[s[i]]] . A[[s[j]]]:
od:

for j from 1 to nops(pairs) do
if op(1,op(j,pairs))= s[i] then
equ:=equ-x[[s[i]]] . A[[op(2,op(j,pairs))]]:
fi:
od:

result:= [op(result), equ-A[[s[i]]]]:

od:

result:
end:
#############################################
GetVarAP:=proc(s,A)
local i,j,result:

result:=[]:
for i from 1 to nops (s) do
result:=[op(result),A[[s[i]]]]
od:
result:
end: 






##################################################################################################################################
HaveElement:=proc(expression,elem)local i:
   if nops(expression) = 1 then
      if expression = elem then return(true):
      else return(false):
      fi:
   fi:
 for i from 1 to nops(expression) do
   if HaveElement(op(i,expression),elem) then return(true): fi:
 od:
 return(false):
 end:
###################################################################################################################################
MyExpand:=proc(expr)
local i,j,ans,leftpart,rightpart,coeffleft,coeffright,temp;

if op(0,expr) = `+` then
  ans:=0:
  for i from 1 to nops(expr) do
    ans:=ans+MyExpand(op(i,expr)):
  od:
  return(ans):
fi: 


if op(0,expr) = `.` then
  for i from 1 to nops(expr) do 
    if op(0,op(i,expr))=`+` then 
      leftpart:=1:
      for j from 1 to i-1 do
         leftpart:= leftpart . op(j,expr): 
      od:

      rightpart:=1: 
      for j from nops(expr) to i+1 by -1 do
        rightpart:= op(j,expr) . rightpart:
      od:
          
      ans:=0;
      for j from 1 to nops(op(i,expr)) do
      ans := ans +MyCoeff(leftpart) *MyCoeff( op(j,op(i,expr))) *MyCoeff (rightpart)*MyExpand(MyNoCoeff(leftpart) . MyNoCoeff( op(j,op(i,expr))) .MyNoCoeff (rightpart)) :
      od: 
      return(ans):
    fi:
  od:
  ans:=1:
  for i from 1 to nops(expr) do
  ans:=ans . MyExpand(op(i,expr)):
  od:
  return (ans):
fi:

if op(0,expr) = `*` then
   if type(op(1,expr),complex) then 
       rightpart:=1:
       for i from 2 to nops(expr) do
       rightpart:=rightpart * op(i,expr):
       od:
       return (op(1,expr) * MyExpand(rightpart)):
   fi:
fi:


if op(0,expr) = `^` then
  if nops(op(1,expr))=1 then 
  return (expr):
  fi:
  if op(2,expr)=-1 then
      temp:=op(1,expr):
      ans:=1:
      if op(0,temp)=`.` then
      for i from nops(temp) to 1 by -1 do 
      ans:=ans . (1/MyExpand(op(i,temp))):
     od:
      return(ans):
      fi:
  fi:
  if op(2,expr)< 0 then
  return (expr):
  fi:
  if type(op(2,expr),even) then
    return (MyExpand(MySquare(op(1,expr))^(op(2,expr)/2))):
  fi:  
  if type(op(2,expr),odd) then
    return (MyExpand((MySquare(op(1,expr))^((op(2,expr)-1)/2)). op(1,expr))):
  fi:
fi:
return(expr);

end:
###########################################################################

AvoidPairs:=proc(s,p,A,x)
local i, equ,var,ans,res,tempvar,tempequ:
equ:=GetEquAP(s,p,A,x):
var:=GetVarAP(s,A):
ans:=MySolve(equ,var);
res:=[]:

for i from 1 to nops(ans) do
tempvar:=op(1,op(i,ans)):
tempequ:=op(2,op(i,ans)):

res:=[op(res), tempvar=MyExplicitForm(MyCombineCoeff(MyCombine(tempequ)))]:  ##MyPositiveExponentForm##
od:


res:
end:

##########################################################

MyCombineOneVar:=proc(equ,var)
local i,j,k,HaveVar, NoVar;
equ:=MyExpand(equ):
HaveVar:=0:
NoVar:=0:
for i from 1 to nops(equ) do
if HaveElement(op(i, equ),var) then
HaveVar:=HaveVar+op(i,equ):
else NoVar:=NoVar+op(i,equ):
fi:
od:

end:
##############################################################
MyWithoutLastTerm:=proc(expression)
local i,ans:
if nops(expression) = 1 then return(1): fi:

if op(0,expression)=`.` then
  ans:=1: 
  for i from 1 to nops(expression)-1 do
     ans:=ans . op(i,expression):
  od:
  return(ans):
fi:

if op(0,expression)=`*` then
  ans:=1: 
  for i from 1 to nops(expression)-1 do
     ans:=ans * op(i,expression):
  od:
  return(ans * MyWithoutLastTerm(op(nops(expression),expression))):
fi:
end:

########################################################################
MySquare:=proc(expr)
local i,j,ans:
ans:=0;
if op(0,expr) =`+` then
  for i from 1 to nops(expr) do
    for j from 1 to nops(expr) do
    ans:=ans+ op(i, expr) . op(j, expr):
    od:
  od:
  return(ans):
fi:

expr^2:
end:

############################################################################
MySolve:=proc(equ, var)
local havevar,novar,i,j,tempequ,tempvar,havevarequ,novarequ,ans:
if nops(equ) <> nops(var) then 
   return(`error! number of equtions is not equal to number of variables`):
fi:

if nops(var) > 1 then
  tempvar:=op(1,var):
else 
  tempvar:=op(var):
fi:

if nops(var) = 1 then
 tempequ:=MyExpand(op(1,equ)):
  if op(0,tempequ)=`*` then return([op(var)=0]):   
  fi:
   if op(0,tempequ)=`.` then return([op(var)=0]):   
  fi:
  havevar:=0:
  novar:=0: 

  for i from 1 to nops(tempequ) do
    if HaveElement(op(i,tempequ),tempvar) then
      havevar:=havevar+MyWithoutLastTerm(op(i,tempequ)):
    else novar:=novar+op(i,tempequ):
    fi:
  od:
  return([tempvar=-(1/havevar) . novar]):
fi:

havevarequ:=[]:
novarequ:=[]:

for i from 1 to nops(equ) do  
  tempequ:=MyExpand(op(i,equ)):
  havevar:=0:
  novar:=0:  
  for j from 1 to nops(tempequ) do
    if HaveElement(op(j,tempequ),tempvar) then
      havevar:=havevar + MyWithoutLastTerm(op(j,tempequ)):
    else novar:=novar+op(j,tempequ):
    fi:
  od:
  if havevar=0 then novarequ:=[op(novarequ),tempequ]:
  else havevarequ:=[op(havevarequ),MyExpand((1/havevar) . novar)]:
  fi:
od:

for i from 2 to nops(havevarequ) do
novarequ:=[op(novarequ), op(i,havevarequ)-op(1,havevarequ)]:
od:


tempequ:=op(1,havevarequ);
ans:=MySolve(novarequ,[op(2..nops(var),var)]);

ans:=[op(ans),subs(ans,tempvar=-tempequ)]:
ans:
end:

#######################################################
MyCoeff:=proc(expr)

if op(0,expr)  <> `*` then return(1): fi:
if  type(op(1,expr),complex) then 
    return (op(1,expr)):
fi:
return(1):
end:
#######################################################
MyNoCoeff:=proc(expr)
local ans,i:


if op(0,expr)  <> `*` then return(expr): fi:
if  type(op(1,expr),complex) then
   ans:=1:
   for i from 2 to nops(expr) do 
   ans:=ans * op(i,expr):
   od:
   return(ans):
fi:
return(expr):
end:
###############################################################
MyCombine:=proc(expr)
local i,j,tempexpr,ans,withf,withoutf :

if op(0,expr) = `+` then

withf:=0:
withoutf:=0;

tempexpr:=MyFirstTermInProduct(op(1,expr)):   
  
  for i from 1 to nops(expr) do
       if MyFirstTermInProduct(op(i,expr))=tempexpr then
          withf:= withf + MyNoFirstTermInProduct(op(i,expr)):
       else
          withoutf:=withoutf+op(i,expr):
       fi:
  od:


  return( tempexpr . MyCombine(withf) + MyCombine(withoutf)):

fi: 

if op(0, expr)=`*` then
   ans:=1:
   for i from 1 to nops(expr) do
      ans:= ans * MyCombine(op(i,expr)):
   od:
   return(ans):
fi:
if op(0, expr)=`.` then
   ans:=1:
   for i from 1 to nops(expr) do
      ans:= ans . MyCombine(op(i,expr)):
   od:
   return(ans):
fi:

if op(0, expr)=`^` then
   
   return(MyCombine(op(1,expr))^op(2,expr)):
fi:

return(expr):
end:

###################################################################################
MyCombineCoeff:=proc(expr)
local i,j,tempexpr,ans,withf,withoutf :

if op(0,expr) = `+` then

  tempexpr:=1:

  for i from 1 to nops(expr) do
  if nops(op(i,expr))=1 and type(op(i,expr),complex) and op(i,expr)<0 then tempexpr:=-1: fi:
  od:

  withf:=0:
  
  for i from 1 to nops(expr) do
          withf:= withf + MyCombineCoeff(tempexpr* (op(i,expr))):
  od:


  return( tempexpr * withf ):

fi: 

if op(0, expr)=`*` then
   ans:=1:
   for i from 1 to nops(expr) do
      ans:= ans * MyCombineCoeff(op(i,expr)):
   od:
   return(ans):
fi:


if op(0, expr)=`.` then
   ans:=1:
   for i from 1 to nops(expr) do
     tempexpr:=1:
     if  op(0,(op(i,expr))) = `+` then
    
      for j from 1 to nops(op(i,expr)) do
      if type(op(j,op(i,expr)),complex) and op(j,op(i,expr))<0 then tempexpr:=-1: fi:
      od:

      fi:
      ans:= tempexpr*ans . MyCombineCoeff(tempexpr*op(i,expr)):
   od:
   return(ans):
fi:

if op(0, expr)=`^` then
   return(MyCombineCoeff(op(1,expr))^op(2,expr)):
fi:

return(expr):
end:
#############################################################################
MyFirstTermInProduct:=proc(expr)
local i,ans:
if nops(expr)= 1 then return (expr): fi:

if op(0,expr)= `.` then return op(1,expr): fi:

if op(0,expr)=`*` then 
  for i from 1 to nops(expr) do
     if op(0,op(i,expr))=`.` then
     return op(1,op(i,expr)):
     fi:
  od:
  if  type(op(1,expr),complex) then
     ans:=1:
     for i from 2 to nops(expr) do
      ans:=ans* op(i,expr):
     od:
     return(ans):
  fi:
fi:


return(expr):
end:
#####################################################################
MyNoFirstTermInProduct:=proc(expr)
local i,j,ans:
if nops(expr)=1 then return(1): fi:
if op(0,expr)=`.` then 
  ans:=1:
  for i from 2 to nops(expr) do
    ans:=ans . op(i,expr):
  od:
  return(ans):
fi:
ans:=1:

if op(0,expr)=`*` then
 
  for i from 1 to nops(expr) do
     if op(0,op(i,expr))=`.` then
     ans:=ans*op(2,op(i,expr)):
     for j from 3 to nops(op(i,expr)) do
     ans:= ans . op(j,op(i,expr)):
     od:
     for j from i+1 to nops(expr) do
     ans:= (ans) * op(j,expr):
     od:
     return(ans):
     else ans:=ans*op(i,expr):
     fi:  
  od:

  if type(op(1,expr),complex) then
    return(op(1,expr)):
  fi:


fi:
return (1):
end:

#############################################################
MyIsGoodForm:=proc(expr)
local i,temp;

if nops(expr)=1 then
    if type(expr, complex) and expr<0 then
       return(false):
    fi:
    return(true):
fi:

if op(0,expr)=`+` then
    temp:=MyCoeff(op(1,expr)):
    for i from 1 to nops(expr) do
        if not MyIsGoodForm(temp*op(i,expr)) then
            return(false):
        fi:
   od:
   return(true):
fi:

if op(0,expr)=`*` then
    temp:=MyCoeff(expr):
     if temp>0 then
        for i from 1 to nops(expr) do
           if (not MyIsGoodForm(temp*op(i,expr))) then
               return(false):
           fi:
        od:
        return(true):
    fi:
    if nops(expr)=2 then
        if op(0,op(2,expr)) <>`^` then return(false):fi:
        return(MyIsGoodForm(op(1,op(2,expr))+1) ) :
    fi:
    return (false):
fi:  

if op(0,expr)=`^` then
  if op(2,expr) >0 then
    return MyIsGoodForm(op(1,expr)):
  fi:
  if  op(2,expr)<0 then 
     return MyIsGoodForm(1-op(1,expr)):
  fi:
   return(true):
fi:  

return(true):
end:

##############################################
MyNormal:=proc(expr)
local ans,i,j,k,left,right,middle,denom,t,term:
if nops(expr) =1 then return(expr): fi:

if op(0,expr)=`+` then
   ans:=0;
   for i from 1 to nops(expr) do
     ans:=ans + MyNormal(op(i,expr)): 
   od:
   return(ans):
fi:
if op(0,expr)=`*` then
   ans:=1;
   for i from 1 to nops(expr) do
     ans:=ans * MyNormal(op(i,expr)): 
   od:
   return(ans):
fi:

if op(0,expr)=`.` then
   ans:=1;
   for i from 1 to nops(expr) do
     ans:=ans . MyNormal(op(i,expr)): 
   od:
   return(ans):
fi:

if op(0,expr)=`^` then
   if op(2,expr) > 0  or not HaveFractions(op(1,expr)) then 
     return(MyNormal(op(1,expr))^op(2,expr)):
   fi:



   denom:=op(1,expr):

   if op(0,denom)=`.` then
         left:=1:
         for i from 1 to nops(denom) do  
         if  op(0,op(i,denom))=`^` and op(2,op(i,denom))<0 then
               left:= (op(1,op(i,denom))^(-op(2,op(i,denom)))) . left :
         else
               break; 
         fi:
         od:

         right:=1:
         for j from nops(denom)  to i+1 by -1 do  
         if  op(0,op(j,denom))=`^` and op(2,op(j,denom))<0 then
               right:= right . (op(1,op(j,denom))^(-op(2,op(j,denom)))):  
         else
               break; 
         fi:
         od:
 
         middle:=1:
         for k from i to j do
             middle:= middle . op(k, denom):
         od:  
         return(   (MyNormal(right)   .( 1/MyNormal(middle)) . MyNormal(left))^(-op(2,expr)) ):
   fi:
   
   t:=NumFractions(denom):
   if op(1,t) = 1 then
     t:=op(1,op(2,t)):
     term:=op(t,denom):

     if op(0,term)=`.` then
         left:=1:
         for i from 1 to nops(term) do  
         if  op(0,op(i,term))=`^` and op(2,op(i,term))<0 then
               left:= (op(1,op(i,term))^(-op(2,op(i,term)))) . left :
         else
               break; 
         fi:
         od:

         right:=1:
         for j from nops(term)  to i+1 by -1 do  
         if  op(0,op(j,term))=`^` and op(2,op(j,term))<0 then
               right:= right . (op(1,op(j,term))^(-op(2,op(j,term)))): 
         else
               break; 
         fi:
         od:
 
         middle:=1:
         for k from i to j do
             middle:= middle . op(k, term):
         od:
           
         return(   (MyNormal(right)   .( MyNormal(1/(middle+( left . (denom-term) . right )))) . MyNormal(left))^(-op(2,expr)) ):
     fi:

     if op(0,term)=`^` and op(2,term)<0 then
       left:=op(1,term)^(-op(2,term)):
       right:=1:
       middle:=1:
       return(   (MyNormal(right)   .( MyNormal(1/(middle+( left . (denom-term) . right )))) . MyNormal(left))^(-op(2,expr))   ):
     fi:
     
     if op(0,term)=`*` then
       left:=1/op(1,term):
       if left = 1 then left:=1/op(2,term): 
       fi:
       right:=1:
       middle:=1:
       return(   (MyNormal(right)   .( MyNormal(1/(MyExpand( left . (denom) . right )))) . MyNormal(left))^(-op(2,expr))   ):
          
     fi:
   fi:
fi:

expr:
end:

######################################################################################################
NumFractions:=proc(expr)
local i,Num,term,j,ans:

if op(0, expr)=`.`  then return([1,[0]]): fi:


if op(0,expr) <> `+` then return([0,[]]): fi:

Num:=0:
ans:=[]:
for i from 1 to nops(expr) do
  term:=op(i,expr):
  if op(0,term)=`.` then
    for j from 1 to nops(term) do
      if op(0,op(j,term))=`^` and op(2,op(j,term))<0 then Num:= Num+1: ans:=[op(ans), i]:break: fi:
    od:
  fi:
  if op(0,term)=`*` then
    term:=op(2,term):
    if op(0,term)=`.` then
      for j from 1 to nops(term) do
        if op(0,op(j,term))=`^` and op(2,op(j,term))<0 then Num:= Num+1:ans:=[op(ans), i]:break: fi:
      od:
    fi: 
  fi:
  if op(0,term)=`^` then
      if op(2,term)<0 then Num:=Num+1: ans:=[op(ans),i]:fi:
  fi:
od:

return([Num,ans]):
end:


############################################################################################
HaveFractions:=proc(expr)
local i:
if nops(expr)=1 then return(false): fi:
if op(0,expr)=`^` and op(2,expr)<0 then return(true): fi:
for i from 1 to nops(expr) do
    if HaveFractions(op(i,expr)) then return(true): fi:
od:

false:
end:
######################################################################################################
########MyExplicitForm returns the explicit form of expr
########
MyExplicitForm:=proc(expr)
local i,j,ans,tempbase,goodform,locateplace,temp,badform,leftpart,rightpart,left,right:

if nops(expr) =1 then return(expr): fi:

if op(0,expr)=`+` then
   ans:=0;
   for i from 1 to nops(expr) do
     ans:=ans + MyExplicitForm(op(i,expr)): 
   od:
   return(ans):
fi:

if op(0,expr)=`*` then
   ans:=1;
   for i from 1 to nops(expr) do
     ans:=ans * MyExplicitForm(op(i,expr)): 
   od:
   return(ans):
fi:

if op(0,expr)=`.` then
   ans:=1;
   for i from 1 to nops(expr) do
     ans:=ans . MyExplicitForm(op(i,expr)): 
   od:
   return(ans):
fi:

if op(0,expr)=`^` then
   if op(2,expr) <> -1 then 
     return(MyExplicitForm(op(1,expr))^op(2,expr)):
   fi:
  
   tempbase:=op(1,expr):
  
   goodform:=MyIsGoodExpr(tempbase):
 
   if goodform then
     return(MyExplicitForm(op(1,expr))^op(2,expr)):
   fi:

   badform:=true:   
   leftpart:=1:
   rightpart:=1:
   temp:=tempbase:
   


   while badform do 
       badform:=false:
       left:=1:
       right:=1:  
       left:=MyLeftReciprocalTerm(temp):
     
       if left <> 1 then rightpart:= MyCoeff(left) * MyCoeff(rightpart) * MyNoCoeff(left) . MyNoCoeff(rightpart):

       if op(0,temp)=`+` then
          ans:=0;
          for i from 1 to nops(temp) do:
             ans:= ans +((MyCoeff(left) * MyCoeff (op(i,temp)) *
             MyExplicitForm(MyExpand( MyNoCoeff(left) . MyNoCoeff(op(i,temp)))))):
         od:
         temp:=ans:
         badform:= true:
         next:
     fi:
     temp:=(MyCoeff(left) * MyCoeff(temp) * MyExplicitForm(MyExpand(MyNoCoeff(left) . MyNoCoeff(temp)))):
     badform:=true:
     next:
     fi:










     #right:=MyRightReciprocalTerm(temp):   
     if right <> 1 then leftpart:= leftpart . right:
     temp:=MyExpand(temp . right):
     badform:= true:
     next:
     fi:
  
   od:

  return (leftpart . (MyExplicitForm( temp))^(-1) . rightpart):  
   

fi:
expr:
end:

#######################################################
#MyCouldChangeToOne
#determine wheather the first term in expr is a reciprocal of a polynomial.
########################################################
MyCouldChangeToOne:=proc(expr)
local i:
if nops(expr)=1 then 
  if type(expr, complex) then return(true):
  else return(false):
  fi:
fi:

if op(0,expr)=`.` then
   for i from 1 to nops(expr) do
      if not MyCouldChangeToOne(op(i,expr)) then 
         return(false):
      fi:
   od:
   return(true):
fi:

if op(0,expr)=`*` then
   for i from 1 to nops(expr) do
      if not MyCouldChangeToOne(op(i,expr)) then
         return(false):
      fi:
   od:
   return(true):
fi:

if op(0,expr)=`^` then
   if op(2,expr)>0 then return(false): fi:
   if MyIsGoodForm(op(1,expr)) then return(true):fi:
   return(false):
fi:
false:
end:
######################################################################
MyLeftReciprocal:=proc(expr)
local i,ans:
if op(0,expr) =`.` then
   ans:=1:
   for i from 1 to nops(expr) do
     ans:=MyLeftReciprocal(op(i,expr)) .ans:
   od:
   return (ans):
fi:

if op(0,expr) =`*` then
   ans:=1:
   for i from 1 to nops(expr) do
     ans:=ans * MyLeftReciprocal(op(i,expr)):
   od:
   return (ans):
fi:

1/expr:
end:
#########################################################################
MyPositiveExponentForm:=proc(expr)
local i,j,ans,temp:
if op(0,expr)=`+` then
   ans:=0:
   for i from 1 to nops(expr) do
   ans:=ans+ MyPositiveExponentForm(op(i,expr)):
   od:
   return(ans):
fi:
if op(0,expr)=`*` then
   ans:=1:
   for i from 1 to nops(expr) do
   ans:=ans* MyPositiveExponentForm(op(i,expr)):
   od:
   return(ans):
fi:
if op(0,expr)=`.` then
   ans:=1:
   for i from 1 to nops(expr) do
   ans:=ans .  MyPositiveExponentForm(op(i,expr)):
   od:
   return(ans):
fi:

if op(0,expr)=`^` then
   if op(2,expr) <> (-1) then return (expr): fi:
   return(  Sum((MyPositiveExponentForm( 1- op(1,expr)))^(`k`),k=0..infinity)   ):
fi:
expr:
end:

##############################################################################
###MyIsGoodExpr  judge weather the the expr is a regular expr with all terms are positive.
 
MyIsGoodExpr:=proc(expr)
local i,j,tempexpr,firstcoeff:

if nops(expr)=1 then 
  if type(expr, negzero) then 
     return(false): 
  fi:
  return(true) 
fi:

if op(0,expr)=`+` then
for i from 1 to nops(expr) do
   if MyIsGoodExpr(op(i,expr))= false then
      return(false):
   fi:
od:
return(true):
fi:

if op(0,expr)=`*` then 
    for i from 1 to nops(expr) do
    if MyIsGoodExpr(op(i,expr))=false then return false: fi:
   od:
    return(true):
fi:

if op(0,expr)=`.` then 
    for i from 1 to nops(expr) do
    if MyIsGoodExpr(op(i,expr))=false then return false: fi:
   od:
    return(true):
fi:

if op(0,expr)=`^` then
    if op(2,expr) = -1 then 
       tempexpr:=op(1,expr):
       if nops(tempexpr)=1 then return false: fi:
       firstcoeff:=MyCoeff(op(1,tempexpr)):

       for i from 2 to nops(tempexpr) do
           if firstcoeff * MyCoeff(op(i,tempexpr)) < 0 then return true: fi:
       od: 
       return false:
   fi:
    return(true):
fi:

end:
###########################################################
MyLeftReciprocalTerm:=proc(expr)
local i,j,ans:
ans:=1:
if MyIsGoodExpr(expr) then return 1: fi:

if op(0,expr)=`+` then
for i from 1 to nops(expr) do
  ans:=MyLeftReciprocalTerm(op(i,expr)):
  if ans <> 1 then return ans: fi:
od:
fi:

if op(0,expr)=`.` then 
  return MyLeftReciprocalTerm(op(1,expr)):
fi:

if op(0,expr)=`^` then
   if op(2,expr) <> -1 then return 1: fi:
   if MyIsGoodExpr(op(1,expr)) then return op(1,expr):
   fi:
   return 1:
fi:

if op(0, expr)=`*` then
if type(op(1,expr),complex) then return MyLeftReciprocalTerm(op(2,expr)):fi:
return MyLeftReciprocalTerm(op(1,expr)):
fi:
1:
end:
###########################################
###########################################################
MyRightReciprocalTerm:=proc(expr)
local i,j,ans:
ans:=1:
if MyIsGoodExpr(expr) then return 1: fi:

if op(0,expr)=`+` then
for i from 1 to nops(expr) do
  ans:=MyRightReciprocalTerm(op(i,expr)):
  if ans <> 1 then return ans: fi:
od:
fi:

if op(0,expr)=`.` then 
  return MyRightReciprocalTerm(op(nops(expr),expr)):
fi:

if op(0,expr)=`^` then
   if op(2,expr) <> -1 then return 1: fi:
   if MyIsGoodExpr(op(1,expr)) then return op(1,expr):
   fi:
   return 1:
fi:

if op(0, expr)=`*` then
return MyRightReciprocalTerm(op(nops(expr),expr)):
fi:
1:
end:
###########################################