def _find_opts(expr):

        if expr.is_Atom or expr.is_Order:
            return

        if iterable(expr):
            list(map(_find_opts, expr))
            return

        if expr in seen_subexp:
            return expr
        seen_subexp.add(expr)

        list(map(_find_opts, expr.args))

        if _coeff_isneg(expr):
            neg_expr = -expr
            if not neg_expr.is_Atom:
                opt_subs[expr] = Mul(S.NegativeOne, neg_expr, evaluate=False)
                seen_subexp.add(neg_expr)
                expr = neg_expr

        if expr.is_Mul:
            muls.add(expr)

        elif expr.is_Add:
            adds.add(expr)

        elif expr.is_Pow:
            if _coeff_isneg(expr.exp):
                opt_subs[expr] = Pow(Pow(expr.base, -expr.exp), S.NegativeOne,
                                     evaluate=False)

    def _find_opts(expr):

        if not isinstance(expr, Basic):
            return

        if expr.is_Atom or expr.is_Order:
            return

        if iterable(expr):
            list(map(_find_opts, expr))
            return

        if expr in seen_subexp:
            return expr
        seen_subexp.add(expr)

        list(map(_find_opts, expr.args))

        if _coeff_isneg(expr):
            neg_expr = -expr
            if not neg_expr.is_Atom:
                opt_subs[expr] = Mul(S.NegativeOne, neg_expr, evaluate=False)
                seen_subexp.add(neg_expr)
                expr = neg_expr

        if isinstance(expr, (Mul, MatMul)):
            muls.add(expr)

        elif isinstance(expr, (Add, MatAdd)):
            adds.add(expr)

        elif isinstance(expr, (Pow, MatPow)):
            if _coeff_isneg(expr.exp):
                opt_subs[expr] = Pow(Pow(expr.base, -expr.exp), S.NegativeOne,
                                     evaluate=False)

 def as_numer_denom(self):
     if not self.is_commutative:
         return self, S.One
     base, exp = self.as_base_exp()
     n, d = base.as_numer_denom()
     if d is not S.One:
         if d.is_negative and n.is_negative:
             n, d = -n, -d
         if exp.is_Integer:
             if exp.is_negative:
                 n, d = d, n
                 exp = -exp
             return Pow(n, exp), Pow(d, exp)
         elif exp.is_Rational or d.is_positive:
             dneg = d.is_negative
             if dneg is not None:
                 if dneg is True:
                     n = -n
                     d = -d
                 elif dneg is False:
                     n, d = d, n
                     exp = -exp
                 if _coeff_isneg(exp):
                     n, d = d, n
                     exp = -exp
                 return Pow(n, exp), Pow(d, exp)
             # else we won't split up base but we check for neg expo below
     if _coeff_isneg(exp):
         return S.One, base**-exp
     # unprocessed float or NumberSymbol exponent
     # and Mul exp w/o negative sign
     return self, S.One

    def eval(cls, arg):
        from sympy import acos
        arg = sympify(arg)

        if arg.is_Number:
            if arg is S.NaN:
                return S.NaN
            elif arg is S.Infinity:
                return S.Infinity
            elif arg is S.NegativeInfinity:
                return S.Infinity
            elif arg is S.Zero:
                return S.Pi*S.ImaginaryUnit / 2
            elif arg is S.One:
                return S.Zero
            elif arg is S.NegativeOne:
                return S.Pi*S.ImaginaryUnit

        if arg.is_number:
            cst_table = {
                S.ImaginaryUnit: log(S.ImaginaryUnit*(1 + sqrt(2))),
                -S.ImaginaryUnit: log(-S.ImaginaryUnit*(1 + sqrt(2))),
                S.Half: S.Pi/3,
                -S.Half: 2*S.Pi/3,
                sqrt(2)/2: S.Pi/4,
                -sqrt(2)/2: 3*S.Pi/4,
                1/sqrt(2): S.Pi/4,
                -1/sqrt(2): 3*S.Pi/4,
                sqrt(3)/2: S.Pi/6,
                -sqrt(3)/2: 5*S.Pi/6,
                (sqrt(3) - 1)/sqrt(2**3): 5*S.Pi/12,
                -(sqrt(3) - 1)/sqrt(2**3): 7*S.Pi/12,
                sqrt(2 + sqrt(2))/2: S.Pi/8,
                -sqrt(2 + sqrt(2))/2: 7*S.Pi/8,
                sqrt(2 - sqrt(2))/2: 3*S.Pi/8,
                -sqrt(2 - sqrt(2))/2: 5*S.Pi/8,
                (1 + sqrt(3))/(2*sqrt(2)): S.Pi/12,
                -(1 + sqrt(3))/(2*sqrt(2)): 11*S.Pi/12,
                (sqrt(5) + 1)/4: S.Pi/5,
                -(sqrt(5) + 1)/4: 4*S.Pi/5
            }

            if arg in cst_table:
                if arg.is_real:
                    return cst_table[arg]*S.ImaginaryUnit
                return cst_table[arg]

        if arg is S.ComplexInfinity:
            return S.Infinity

        i_coeff = arg.as_coefficient(S.ImaginaryUnit)

        if i_coeff is not None:
            if _coeff_isneg(i_coeff):
                return S.ImaginaryUnit * acos(i_coeff)
            return S.ImaginaryUnit * acos(-i_coeff)
        else:
            if _coeff_isneg(arg):
                return -cls(-arg)

    def eval(cls, arg):
        from sympy import cot
        arg = sympify(arg)

        if arg.is_Number:
            if arg is S.NaN:
                return S.NaN
            elif arg is S.Infinity:
                return S.One
            elif arg is S.NegativeInfinity:
                return S.NegativeOne
            elif arg is S.Zero:
                return S.ComplexInfinity
            elif arg.is_negative:
                return -cls(-arg)
        else:
            if arg is S.ComplexInfinity:
                return S.NaN

            i_coeff = arg.as_coefficient(S.ImaginaryUnit)

            if i_coeff is not None:
                if _coeff_isneg(i_coeff):
                    return S.ImaginaryUnit * cot(-i_coeff)
                return -S.ImaginaryUnit * cot(i_coeff)
            else:
                if _coeff_isneg(arg):
                    return -cls(-arg)

            if arg.is_Add:
                x, m = _peeloff_ipi(arg)
                if m:
                    cothm = coth(m)
                    if cothm is S.ComplexInfinity:
                        return coth(x)
                    else: # cothm == 0
                        return tanh(x)

            if arg.func == asinh:
                x = arg.args[0]
                return sqrt(1 + x**2)/x

            if arg.func == acosh:
                x = arg.args[0]
                return x/(sqrt(x - 1) * sqrt(x + 1))

            if arg.func == atanh:
                return 1/arg.args[0]

            if arg.func == acoth:
                return arg.args[0]

def _set_function(f, self):
    expr = f.expr
    if not isinstance(expr, Expr):
        return

    if len(f.variables) > 1:
        return

    n = f.variables[0]

    # f(x) + c and f(-x) + c cover the same integers
    # so choose the form that has the fewest negatives
    c = f(0)
    fx = f(n) - c
    f_x = f(-n) - c
    neg_count = lambda e: sum(_coeff_isneg(_) for _ in Add.make_args(e))
    if neg_count(f_x) < neg_count(fx):
        expr = f_x + c

    a = Wild('a', exclude=[n])
    b = Wild('b', exclude=[n])
    match = expr.match(a*n + b)
    if match and match[a]:
        # canonical shift
        expr = match[a]*n + match[b] % match[a]

    if expr != f.expr:
        return ImageSet(Lambda(n, expr), S.Integers)

 def as_numer_denom(self):
     if not self.is_commutative:
         return self, S.One
     base, exp = self.as_base_exp()
     n, d = base.as_numer_denom()
     # this should be the same as ExpBase.as_numer_denom wrt
     # exponent handling
     neg_exp = exp.is_negative
     if not neg_exp and not (-exp).is_negative:
         neg_exp = _coeff_isneg(exp)
     int_exp = exp.is_integer
     # the denominator cannot be separated from the numerator if
     # its sign is unknown unless the exponent is an integer, e.g.
     # sqrt(a/b) != sqrt(a)/sqrt(b) when a=1 and b=-1. But if the
     # denominator is negative the numerator and denominator can
     # be negated and the denominator (now positive) separated.
     if not (d.is_real or int_exp):
         n = base
         d = S.One
     dnonpos = d.is_nonpositive
     if dnonpos:
         n, d = -n, -d
     elif dnonpos is None and not int_exp:
         n = base
         d = S.One
     if neg_exp:
         n, d = d, n
         exp = -exp
     return self.func(n, exp), self.func(d, exp)

    def _print_Mul(self, expr):

        if _coeff_isneg(expr):
            x = self.dom.createElement('apply')
            x.appendChild(self.dom.createElement('minus'))
            x.appendChild(self._print_Mul(-expr))
            return x

        from sympy.simplify import fraction
        numer, denom = fraction(expr)

        if denom is not S.One:
            x = self.dom.createElement('apply')
            x.appendChild(self.dom.createElement('divide'))
            x.appendChild(self._print(numer))
            x.appendChild(self._print(denom))
            return x

        coeff, terms = expr.as_coeff_mul()
        if coeff is S.One and len(terms) == 1:
            # XXX since the negative coefficient has been handled, I don't
            # think a coeff of 1 can remain
            return self._print(terms[0])

        if self.order != 'old':
            terms = Mul._from_args(terms).as_ordered_factors()

        x = self.dom.createElement('apply')
        x.appendChild(self.dom.createElement('times'))
        if(coeff != 1):
            x.appendChild(self._print(coeff))
        for term in terms:
            x.appendChild(self._print(term))
        return x

    def eval(cls, arg):
        arg = sympify(arg)

        if arg.is_Number:
            if arg is S.NaN:
                return S.NaN
            elif arg is S.Infinity:
                return S.Zero
            elif arg is S.NegativeInfinity:
                return S.Zero
            elif arg is S.Zero:
                return S.Pi*S.ImaginaryUnit / 2
            elif arg is S.One:
                return S.Infinity
            elif arg is S.NegativeOne:
                return S.NegativeInfinity
            elif arg.is_negative:
                return -cls(-arg)
        else:
            if arg is S.ComplexInfinity:
                return 0

            i_coeff = arg.as_coefficient(S.ImaginaryUnit)

            if i_coeff is not None:
                return -S.ImaginaryUnit * C.acot(i_coeff)
            else:
                if _coeff_isneg(arg):
                    return -cls(-arg)

 def _print_Add(self, expr, order=None):
     args = self._as_ordered_terms(expr, order=order)
     lastProcessed = self._print(args[0])
     plusNodes = []
     for arg in args[1:]:
         if _coeff_isneg(arg):
             # use minus
             x = self.dom.createElement('apply')
             x.appendChild(self.dom.createElement('minus'))
             x.appendChild(lastProcessed)
             x.appendChild(self._print(-arg))
             # invert expression since this is now minused
             lastProcessed = x
             if(arg == args[-1]):
                 plusNodes.append(lastProcessed)
         else:
             plusNodes.append(lastProcessed)
             lastProcessed = self._print(arg)
             if(arg == args[-1]):
                 plusNodes.append(self._print(arg))
     if len(plusNodes) == 1:
         return lastProcessed
     x = self.dom.createElement('apply')
     x.appendChild(self.dom.createElement('plus'))
     while len(plusNodes) > 0:
         x.appendChild(plusNodes.pop(0))
     return x

    def _print_Add(self, expr, order=None):
        if self.order == 'none':
            terms = list(expr.args)
        else:
            terms = self._as_ordered_terms(expr, order=order)
        pforms, indices = [], []

        def pretty_negative(pform, index):
            """Prepend a minus sign to a pretty form. """
            if index == 0:
                if pform.height() > 1:
                    pform_neg = '- '
                else:
                    pform_neg = '-'
            else:
                pform_neg = ' - '

            pform = stringPict.next(pform_neg, pform)
            return prettyForm(binding=prettyForm.NEG, *pform)

        for i, term in enumerate(terms):
            if term.is_Mul and _coeff_isneg(term):
                pform = self._print(-term)
                pforms.append(pretty_negative(pform, i))
            elif term.is_Rational and term.q > 1:
                pforms.append(None)
                indices.append(i)
            elif term.is_Number and term < 0:
                pform = self._print(-term)
                pforms.append(pretty_negative(pform, i))
            else:
                pforms.append(self._print(term))

        if indices:
            large = True

            for pform in pforms:
                if pform is not None and pform.height() > 1:
                    break
            else:
                large = False

            for i in indices:
                term, negative = terms[i], False

                if term < 0:
                    term, negative = -term, True

                if large:
                    pform = prettyForm(str(term.p))/prettyForm(str(term.q))
                else:
                    pform = self._print(term)

                if negative:
                    pform = pretty_negative(pform, i)

                pforms[i] = pform

        return prettyForm.__add__(*pforms)

    def eval(cls, arg):
        from sympy import tan

        arg = sympify(arg)

        if arg.is_Number:
            if arg is S.NaN:
                return S.NaN
            elif arg is S.Infinity:
                return S.One
            elif arg is S.NegativeInfinity:
                return S.NegativeOne
            elif arg is S.Zero:
                return S.Zero
            elif arg.is_negative:
                return -cls(-arg)
        else:
            if arg is S.ComplexInfinity:
                return S.NaN

            i_coeff = arg.as_coefficient(S.ImaginaryUnit)

            if i_coeff is not None:
                if _coeff_isneg(i_coeff):
                    return -S.ImaginaryUnit * tan(-i_coeff)
                return S.ImaginaryUnit * tan(i_coeff)
            else:
                if _coeff_isneg(arg):
                    return -cls(-arg)

            if arg.func == asinh:
                x = arg.args[0]
                return x / sqrt(1 + x ** 2)

            if arg.func == acosh:
                x = arg.args[0]
                return sqrt(x - 1) * sqrt(x + 1) / x

            if arg.func == atanh:
                return arg.args[0]

            if arg.func == acoth:
                return 1 / arg.args[0]

    def _print_Add(self, expr):
        tex = str(self._print(expr.args[0]))

        for term in expr.args[1:]:
            if _coeff_isneg(term):
                tex += r" %s" % self._print(term)
            else:
                tex += r" + %s" % self._print(term)

        return tex

    def _print_Add(self, expr, order=None):
        if self.order == "none":
            terms = list(expr.args)
        else:
            terms = self._as_ordered_terms(expr, order=order)
        tex = self._print(terms[0])

        for term in terms[1:]:
            if not _coeff_isneg(term):
                tex += " +"

            tex += " " + self._print(term)

        return tex

    def _print_Mul(self, expr):

        prec = precedence(expr)

        if _coeff_isneg(expr):
            expr = -expr
            sign = "-"
        else:
            sign = ""

        a = [] # items in the numerator
        b = [] # items that are in the denominator (if any)

        if self.order not in ('old', 'none'):
            args = expr.as_ordered_factors()
        else:
            # use make_args in case expr was something like -x -> x
            args = Mul.make_args(expr)

        # Gather args for numerator/denominator
        for item in args:
            if item.is_commutative and item.is_Pow and item.exp.is_Rational and item.exp.is_negative:
                if item.exp != -1:
                    b.append(Pow(item.base, -item.exp, evaluate=False))
                else:
                    b.append(Pow(item.base, -item.exp))
            elif item.is_Rational and item is not S.Infinity:
                if item.p != 1:
                    a.append(Rational(item.p))
                if item.q != 1:
                    b.append(Rational(item.q))
            else:
                a.append(item)

        a = a or [S.One]

        a_str = map(lambda x:self.parenthesize(x, prec), a)
        b_str = map(lambda x:self.parenthesize(x, prec), b)

        if len(b) == 0:
            return sign + '*'.join(a_str)
        elif len(b) == 1:
            if len(a) == 1 and not (a[0].is_Atom or a[0].is_Add):
                return sign + "%s/"%a_str[0] + '*'.join(b_str)
            else:
                return sign + '*'.join(a_str) + "/%s"%b_str[0]
        else:
            return sign + '*'.join(a_str) + "/(%s)"%'*'.join(b_str)

    def _print_Mul(self, expr):

        def multiply(expr, mrow):
            from sympy.simplify import fraction
            numer, denom = fraction(expr)
            if denom is not S.One:
                frac = self.dom.createElement('mfrac')
                if self._settings["fold_short_frac"] and len(str(expr)) < 7:
                    frac.setAttribute('bevelled', 'true')
                xnum = self._print(numer)
                xden = self._print(denom)
                frac.appendChild(xnum)
                frac.appendChild(xden)
                mrow.appendChild(frac)
                return mrow

            coeff, terms = expr.as_coeff_mul()
            if coeff is S.One and len(terms) == 1:
                mrow.appendChild(self._print(terms[0]))
                return mrow
            if self.order != 'old':
                terms = Mul._from_args(terms).as_ordered_factors()

            if coeff != 1:
                x = self._print(coeff)
                y = self.dom.createElement('mo')
                y.appendChild(self.dom.createTextNode(self.mathml_tag(expr)))
                mrow.appendChild(x)
                mrow.appendChild(y)
            for term in terms:
                x = self._print(term)
                mrow.appendChild(x)
                if not term == terms[-1]:
                    y = self.dom.createElement('mo')
                    y.appendChild(self.dom.createTextNode(self.mathml_tag(expr)))
                    mrow.appendChild(y)
            return mrow
        mrow = self.dom.createElement('mrow')
        if _coeff_isneg(expr):
            x = self.dom.createElement('mo')
            x.appendChild(self.dom.createTextNode('-'))
            mrow.appendChild(x)
            mrow = multiply(-expr, mrow)
        else:
            mrow = multiply(expr, mrow)

        return mrow

def clear_coefficients(expr, rhs=S.Zero):
    """Return `p, r` where `p` is the expression obtained when Rational
    additive and multiplicative coefficients of `expr` have been stripped
    away in a naive fashion (i.e. without simplification). The operations
    needed to remove the coefficients will be applied to `rhs` and returned
    as `r`.

    Examples
    ========

    >>> from sympy.simplify.simplify import clear_coefficients
    >>> from sympy.abc import x, y
    >>> from sympy import Dummy
    >>> expr = 4*y*(6*x + 3)
    >>> clear_coefficients(expr - 2)
    (y*(2*x + 1), 1/6)

    When solving 2 or more expressions like `expr = a`,
    `expr = b`, etc..., it is advantageous to provide a Dummy symbol
    for `rhs` and  simply replace it with `a`, `b`, etc... in `r`.

    >>> rhs = Dummy('rhs')
    >>> clear_coefficients(expr, rhs)
    (y*(2*x + 1), _rhs/12)
    >>> _[1].subs(rhs, 2)
    1/6
    """
    was = None
    free = expr.free_symbols
    if expr.is_Rational:
        return (S.Zero, rhs - expr)
    while expr and was != expr:
        was = expr
        m, expr = (
            expr.as_content_primitive()
            if free else
            factor_terms(expr).as_coeff_Mul(rational=True))
        rhs /= m
        c, expr = expr.as_coeff_Add(rational=True)
        rhs -= c
    expr = signsimp(expr, evaluate = False)
    if _coeff_isneg(expr):
        expr = -expr
        rhs = -rhs
    return expr, rhs

    def __new__(cls, b, e, evaluate=None):
        if evaluate is None:
            evaluate = global_evaluate[0]
        from sympy.functions.elementary.exponential import exp_polar

        b = _sympify(b)
        e = _sympify(e)
        if evaluate:
            if e is S.Zero:
                return S.One
            elif e is S.One:
                return b
            elif e.is_integer and _coeff_isneg(b):
                if e.is_even:
                    b = -b
                elif e.is_odd:
                    return -Pow(-b, e)
            if b is S.One:
                if e in (S.NaN, S.Infinity, -S.Infinity):
                    return S.NaN
                return S.One
            elif S.NaN in (b, e):  # XXX S.NaN**x -> S.NaN under assumption that x != 0
                return S.NaN
            else:
                # recognize base as E
                if not e.is_Atom and b is not S.Exp1 and b.func is not exp_polar:
                    from sympy import numer, denom, log, sign, im, factor_terms
                    c, ex = factor_terms(e, sign=False).as_coeff_Mul()
                    den = denom(ex)
                    if den.func is log and den.args[0] == b:
                        return S.Exp1**(c*numer(ex))
                    elif den.is_Add:
                        s = sign(im(b))
                        if s.is_Number and s and den == \
                                log(-factor_terms(b, sign=False)) + s*S.ImaginaryUnit*S.Pi:
                            return S.Exp1**(c*numer(ex))

                obj = b._eval_power(e)
                if obj is not None:
                    return obj
        obj = Expr.__new__(cls, b, e)
        obj.is_commutative = (b.is_commutative and e.is_commutative)
        return obj

    def _print_Add(self, expr, order=None):
        if(self._settings['use_operators']):
            return CodePrinter._print_Add(self, expr, order=order)

        terms = expr.as_ordered_terms()

        def partition(p,l):
            return reduce(lambda x, y: (x[0]+[y], x[1]) if p(y) else (x[0], x[1]+[y]), l,  ([], []))
        def add(a,b):
            return self._print_Function_with_args('add', (a, b))
            # return self.known_functions['add']+'(%s, %s)' % (a,b)
        neg, pos = partition(lambda arg: _coeff_isneg(arg), terms)
        s = pos = reduce(lambda a,b: add(a,b), map(lambda t: self._print(t),pos))
        if(len(neg) > 0):
            # sum the absolute values of the negative terms
            neg = reduce(lambda a,b: add(a,b), map(lambda n: self._print(-n),neg))
            # then subtract them from the positive terms
            s = self._print_Function_with_args('sub', (pos,neg))
            # s = self.known_functions['sub']+'(%s, %s)' % (pos,neg)
        return s

    def as_numer_denom(self):
        """
        Returns this with a positive exponent as a 2-tuple (a fraction).

        Examples
        ========

        >>> from sympy.functions import exp
        >>> from sympy.abc import x
        >>> exp(-x).as_numer_denom()
        (1, exp(x))
        >>> exp(x).as_numer_denom()
        (exp(x), 1)
        """
        # this should be the same as Pow.as_numer_denom wrt
        # exponent handling
        exp = self.exp
        neg_exp = exp.is_negative
        if not neg_exp and not (-exp).is_negative:
            neg_exp = _coeff_isneg(exp)
        if neg_exp:
            return S.One, self.func(-exp)
        return self, S.One