SumProductPower.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SumProductPowerVarArgs
{
    // types in a list:
    //     int
    //     Symbol
    //     Sum
    //     Product
    //     Function
    
    public abstract class MathObject
    {
        public static bool operator ==(MathObject a, MathObject b)
        {
            if (a is Integer && b is Integer)
                return (Integer)a == (Integer)b;

            if (a is Integer) return false;
            if (b is Integer) return false;

            if (a is Fraction && b is Fraction)
                return (Fraction)a == (Fraction)b;

            if (a is Fraction) return false;
            if (b is Fraction) return false;

            if (a is Product && b is Product)
                return (Product)a == (Product)b;

            if (a is Product) return false;
            if (b is Product) return false;

            if (a is Sum && b is Sum)
                return (Sum)a == (Sum)b;

            if (a is Symbol && b is Symbol)
                return (Symbol)a == (Symbol)b;

            if (a is Power && b is Power)
                return (Power)a == (Power)b;

            if (a is Power) return false;
            if (b is Power) return false;

            throw new Exception();
        }

        public static bool operator !=(MathObject a, MathObject b)
        { return !(a == b); }

        public static MathObject operator +(MathObject a, MathObject b)
        {
            return new Sum(a, b).Simplify();
        }

        public static MathObject operator +(MathObject a, int b)
        {
            //if (a is Symbol) return ((Symbol)a) + new Integer(b);

            //if (a is Sum) return ((Sum)a) + new Integer(b);

            //if (a is Product) return ((Product)a) + new Integer(b);

            return a + new Integer(b);

            throw new Exception();
        }

        public static MathObject operator +(int a, MathObject b)
        { return b + a; }

        public static MathObject operator /(MathObject a, int b)
        { return new Quotient(a, new Integer(b)).Simplify(); }
    }

    public abstract class Number : MathObject
    {
    }

    public class Integer : Number 
    { 
        public int val;

        public Integer(int n) { val = n; }

        public override string ToString()
        {
            return "Integer(" + val.ToString() + ")";
        }

        public static bool operator ==(Integer a, Integer b)
        { return a.val == b.val; }

        public static bool operator !=(Integer a, Integer b)
        { return !(a == b); }
    }

    public class Double : Number { public double val; }

    public class Fraction : Number
    {
        public Integer numerator;
        public Integer denominator;

        public Fraction(Integer a, Integer b)
        { numerator = a; denominator = b; }
        //////////////////////////////////////////////////////////////////////
        public static bool operator ==(Fraction a, Fraction b)
        {
            return
                a.numerator.val == b.numerator.val
                &&
                a.denominator.val == b.denominator.val;
        }

        public static bool operator !=(Fraction a, Fraction b)
        { return !(a == b); } 
        //////////////////////////////////////////////////////////////////////
    }

    public static class Rational
    {
        static int Div(int a, int b)
        { int rem; return Math.DivRem(a, b, out rem); }

        static int Rem(int a, int b)
        { int rem; Math.DivRem(a, b, out rem); return rem; }

        static int Gcd(int a, int b)
        {
            int r;
            while (b != 0)
            {
                r = Rem(a, b);
                a = b;
                b = r;
            }
            return Math.Abs(a);
        }

        public static MathObject SimplifyRationalNumber(MathObject u)
        {
            if (u is Integer) return u;

            if (u is Fraction)
            {
                var u_ = (Fraction)u;
                var n = u_.numerator.val;
                var d = u_.denominator.val;

                if (Rem(n, d) == 0) return new Integer(Div(n, d));

                var g = Gcd(n, d);

                if (d > 0) return new Fraction(new Integer(Div(n, g)), new Integer(Div(d, g)));

                if (d < 0) return new Fraction(new Integer(Div(-n, g)), new Integer(Div(-d, g)));
            }

            throw new Exception();
        }

        public static Integer Numerator(MathObject u)
        {
            // (a / b) / (c / d)
            // (a / b) * (d / c)
            // (a * d) / (b * c)

            if (u is Integer) return (Integer)u;

            // if (u is Fraction) return Numerator(((Fraction)u).numerator);

            if (u is Fraction)
                return
                    new Integer(
                        Numerator(((Fraction)u).numerator).val
                        *
                        Denominator(((Fraction)u).denominator).val);

            throw new Exception();
        }

        public static Integer Denominator(MathObject u)
        {
            // (a / b) / (c / d)
            // (a / b) * (d / c)
            // (a * d) / (b * c)

            if (u is Integer) return new Integer(1);

            // if (u is Fraction) return Denominator(((Fraction)u).denominator);

            if (u is Fraction)
                return
                    new Integer(
                        Denominator(((Fraction)u).numerator).val
                        *
                        Numerator(((Fraction)u).denominator).val);

            throw new Exception();
        }

        public static Fraction EvaluateSum(MathObject v, MathObject w)
        {
            // a / b + c / d
            // a d / b d + c b / b d
            // (a d + c b) / (b d)
            return
                new Fraction(
                    new Integer(Numerator(v).val * Denominator(w).val + Numerator(w).val * Denominator(v).val),
                    new Integer(Denominator(v).val * Denominator(w).val));
        }

        public static Fraction EvaluateDifference(MathObject v, MathObject w)
        {
            return
                new Fraction(
                    new Integer(Numerator(v).val * Denominator(w).val - Numerator(w).val * Denominator(v).val),
                    new Integer(Denominator(v).val * Denominator(w).val));
        }

        public static Fraction EvaluateProduct(MathObject v, MathObject w)
        {
            return
                new Fraction(
                    new Integer(Numerator(v).val * Numerator(w).val),
                    new Integer(Denominator(v).val * Denominator(w).val));
        }

        public static MathObject EvaluateQuotient(MathObject v, MathObject w)
        {
            if (Numerator(w).val == 0) return new Undefined();

            return
                new Fraction(
                    new Integer(Numerator(v).val * Denominator(w).val),
                    new Integer(Numerator(w).val * Denominator(v).val));
        }

        public static MathObject EvaluatePower(MathObject v, int n)
        {
            if (Numerator(v).val != 0)
            {
                if (n > 0) return EvaluateProduct(EvaluatePower(v, n - 1), v);
                if (n == 0) return new Integer(1);
                if (n == -1)
                    return new Fraction(new Integer(Denominator(v).val), new Integer(Numerator(v).val));
                if (n < -1)
                {
                    var s = new Fraction(new Integer(Denominator(v).val), new Integer(Numerator(v).val));
                    return EvaluatePower(s, -n);
                }
            }

            if (n >= 1) return new Integer(0);
            if (n <= 0) return new Undefined();

            throw new Exception();
        }

        public static MathObject SimplifyRNERec(MathObject u)
        {
            if (u is Integer) return u;

            if (u is Fraction)
                if (Denominator((Fraction)u).val == 0) return new Undefined();
                else return u;

            if (u is Sum && ((Sum)u).elts.Count == 1)
            { return SimplifyRNERec(((Sum)u).elts[0]); }

            if (u is Difference && ((Difference)u).elts.Count == 1)
            {
                var v = SimplifyRNERec(((Difference)u).elts[0]);

                if (v == new Undefined()) return v;

                return EvaluateProduct(new Integer(-1), v);
            }

            if (u is Sum && ((Sum)u).elts.Count == 2)
            {
                var v = SimplifyRNERec(((Sum)u).elts[0]);
                var w = SimplifyRNERec(((Sum)u).elts[1]);

                if (v == new Undefined() || w == new Undefined())
                    return new Undefined();

                return EvaluateSum(v, w);
            }

            if (u is Product && ((Product)u).elts.Count == 2)
            {
                var v = SimplifyRNERec(((Product)u).elts[0]);
                var w = SimplifyRNERec(((Product)u).elts[1]);

                if (v == new Undefined() || w == new Undefined())
                    return new Undefined();

                return EvaluateProduct(v, w);
            }

            if (u is Difference && ((Difference)u).elts.Count == 2)
            {
                var v = SimplifyRNERec(((Difference)u).elts[0]);
                var w = SimplifyRNERec(((Difference)u).elts[1]);

                if (v == new Undefined() || w == new Undefined())
                    return new Undefined();

                return EvaluateDifference(v, w);
            }

            if (u is Fraction)
            {
                var v = SimplifyRNERec(((Fraction)u).numerator);
                var w = SimplifyRNERec(((Fraction)u).denominator);

                if (v == new Undefined() || w == new Undefined())
                    return new Undefined();

                return EvaluateQuotient(v, w);
            }

            if (u is Power)
            {
                var v = SimplifyRNERec(((Power)u).bas);

                if (v == new Undefined()) return v;

                return EvaluatePower(v, ((Integer)((Power)u).exp).val);
            }

            throw new Exception();
        }

        public static MathObject SimplifyRNE(MathObject u)
        {
            var v = SimplifyRNERec(u);
            if (v is Undefined) return v;
            return SimplifyRationalNumber(v);
        }
    }

    public class Undefined : MathObject { }

    public static class MiscUtils
    {
        public static bool equal(Object a, Object b)
        {
            // if (a is int && b is int) return (int)a == (int) b;

            if (a is Integer && b is Integer) return ((Integer)a).val == ((Integer)b).val;

            if (a is Symbol && b is Symbol) return (Symbol)a == (Symbol)b;

            if (a is Sum && b is Sum) return (Sum)a == (Sum)b;

            if (a is Product && b is Product) return (Product)a == (Product)b;

            if (a is Function && b is Function) return (Function)a == (Function)b;

            return false;
        }

        public static string PrettyString(Object obj, int precedence = 0)
        {
            var str = new StringBuilder();

            if (obj is Integer) return ((Integer)obj).val.ToString();

            if (obj is Symbol) return ((Symbol)obj).name;

            if (obj is Power)
            {
                if (30 < precedence) str.Append("(");

                var obj_ = (Power)obj;

                str.Append(PrettyString(obj_.bas, 30));
                str.Append(" ^ ");
                str.Append(PrettyString(obj_.exp, 30));

                if (30 < precedence) str.Append(")");

                return str.ToString();
            }
            
            if (obj is Product)
            {
                if (20 < precedence) str.Append("(");
                
                var obj_ = (Product)obj;

                for (var i = 0; i < obj_.elts.Count - 1; i++)
                {
                    str.Append(PrettyString(obj_.elts[i], 20));
                    str.Append(" ");
                }

                str.Append(PrettyString(obj_.elts[obj_.elts.Count - 1], 10));

                if (20 < precedence) str.Append(")");

                return str.ToString();
            }

            if (obj is Sum)
            {
                if (10 < precedence) str.Append("(");

                var obj_ = (Sum)obj;

                for (var i = 0; i < obj_.elts.Count - 1; i++)
                {
                    str.Append(PrettyString(obj_.elts[i], 10));
                    str.Append(" + ");
                }

                str.Append(PrettyString(obj_.elts[obj_.elts.Count - 1], 10));

                if (10 < precedence) str.Append(")");

                return str.ToString();
            }

            throw new Exception();
        }
    }

    public class Symbol : MathObject
    { 
        public String name;

        public Symbol(String str) { name = str; }

        public override string ToString()
        {
            return "Symbol(" + name + ")";
        }

        //////////////////////////////////////////////////////////////////////
        public override int GetHashCode() { return name.GetHashCode(); }

        public override bool Equals(Object obj)
        { return name == (obj as Symbol).name; }

        public static bool operator ==(Symbol a, Symbol b)
        { return a.name == b.name; }

        public static bool operator !=(Symbol a, Symbol b)
        { return !(a == b); }        
        //////////////////////////////////////////////////////////////////////
        public static MathObject operator +(Symbol a, Symbol b)
        { return new Sum(a, b).Simplify(); }

        public static MathObject operator +(Symbol a, MathObject b)
        { return new Sum(a, b).Simplify(); }

        public static MathObject operator +(MathObject a, Symbol b)
        { return new Sum(a, b).Simplify(); }

        public static MathObject operator +(Symbol a, int b)
        { return new Sum(a, new Integer(b)).Simplify(); }

        public static MathObject operator +(int a, Symbol b)
        { return new Sum(new Integer(a), b).Simplify(); }
        //////////////////////////////////////////////////////////////////////
        public static MathObject operator *(int a, Symbol b)
        { return new Product(new Integer(a), b).Simplify(); }

        public static MathObject operator *(Symbol a, Symbol b)
        { return new Product(a, b).Simplify(); }

        public static MathObject operator *(MathObject a, Symbol b)
        {
            return new Product(a, b).Simplify();
        }
        //////////////////////////////////////////////////////////////////////
        public static MathObject operator -(int a, Symbol b)
        { return new Difference(new Integer(a), b).Simplify(); }
        //////////////////////////////////////////////////////////////////////
        public static MathObject operator /(Symbol a, Symbol b)
        { return new Quotient(a, b).Simplify(); }
    }

    public class Function : MathObject
    {
        public String name;

        public List<MathObject> args;
    }
        
    public static class ListUtils
    {
        public static bool IsEmpty(this List<MathObject> obj)
        { return obj.Count == 0; }

        public static List<MathObject> Cons(this List<MathObject> obj, MathObject elt)
        {
            var res = new List<MathObject>(obj);
            res.Insert(0, elt);
            return res;
        }

        public static List<MathObject> Cdr(this List<MathObject> obj)
        { return obj.GetRange(1, obj.Count - 1); }

        public static bool equal(List<MathObject> a, List<MathObject> b)
        {
            if (a.Count == 0 && b.Count == 0) return true;
            
            if (a.Count == 0) return false;

            if (b.Count == 0) return false;
            
            if (a[0] is Integer && b[0] is Integer)
                if (((Integer)a[0]).val == ((Integer)b[0]).val) return equal(a.Cdr(), b.Cdr());
                else return false;
            
            if (a[0] is Symbol && b[0] is Symbol)
                if ((Symbol)a[0] == (Symbol)b[0]) return equal(a.Cdr(), b.Cdr());
                else return false;
          
            if (a[0] == b[0]) return equal(a.Cdr(), b.Cdr());

            return false;
        }
    }

    public static class OrderRelation
    {
        public static MathObject Base(MathObject u)
        {
            if (u is Power) return ((Power)u).bas;

            // if (u is int) return false;

            return u;
        }

        public static MathObject Exponent(MathObject u)
        {
            if (u is Power) return ((Power)u).exp;

            // if (u is int) return false;

            return new Integer(1);
        }

        public static MathObject Term(MathObject u)
        {
            // if (u is int) return false;

            if (u is Product && ((Product)u).elts[0] is Integer)
                return new Product() { elts = ((Product)u).elts.Cdr() };

            if (u is Product) return u;

            return new Product() { elts = new List<MathObject>() { u } };
        }

        public static MathObject Const(MathObject u)
        {
            // if (u is int) return false;

            if (u is Product)
            {
                var res = (Product) u;

                return res.elts[0] is Integer ? 
                    new Integer(((Integer)res.elts[0]).val) :
                    new Integer(1);
            }

            return new Integer(1);
        }

        public static bool O3(List<MathObject> uElts, List<MathObject> vElts)
        {
            if (uElts.IsEmpty()) return true;
            if (vElts.IsEmpty()) return false;

            var u = uElts.First();
            var v = vElts.First();

            return (!(u == v)) ?
                Compare(u, v) :
                O3(uElts.Cdr(), vElts.Cdr());
        }

        public static bool Compare(MathObject u, MathObject v)
        {
            if (u is Integer)
                return Compare(new Fraction((Integer)u, new Integer(1)), v);

            if (v is Integer)
                return Compare(u, new Fraction((Integer)v, new Integer(1)));

            // if (u is Integer && v is Integer) return ((Integer) u).val < ((Integer) v).val;

            if (u is Fraction && v is Fraction)
            {
                var u_ = (Fraction)u;
                var v_ = (Fraction)v;

                // a / b   <   c / d
                //
                // (a d) / (b d)   <   (c b) / (b d)

                return
                    (u_.numerator.val * v_.denominator.val)
                    <
                    (v_.numerator.val * u_.denominator.val);
            }

            if (u is Symbol && v is Symbol)
                return
                    String.Compare(
                        ((Symbol)u).name,
                        ((Symbol)v).name) < 0;

            if (u is Product && v is Product)
            {
                // var a = new List<MathObject>(((Product)u).elts.Cdr());
                var a = new List<MathObject>(((Product)u).elts);
                a.Reverse();

                // var b = new List<MathObject>(((Product)v).elts.Cdr());
                var b = new List<MathObject>(((Product)v).elts);
                b.Reverse();

                return O3(a, b);
            }

            if (u is Sum && v is Sum)
            {
                // var a = new List<MathObject>(((Sum)u).elts.Cdr());
                var a = new List<MathObject>(((Sum)u).elts);
                a.Reverse();

                // var b = new List<MathObject>(((Sum)v).elts.Cdr());
                var b = new List<MathObject>(((Sum)v).elts);
                b.Reverse();

                return O3(a, b);
            }

            if (u is Power && v is Power)
            {
                var u_ = (Power)u;
                var v_ = (Power)v;

                return (u_.bas == v_.bas) ?
                    Compare(u_.exp, v_.exp) : 
                    Compare(u_.bas, v_.bas);
            }

            if (u is Function && v is Function)
            {
                var u_ = (Function)u;
                var v_ = (Function)v;

                return u_.name == v_.name ?
                    O3(u_.args, v_.args) :
                    String.Compare(u_.name, v_.name) < 0;
            }

            // if (u is Integer && !(v is Integer)) return true;

            if ((u is Integer || u is Fraction)
                &&
                !(v is Integer || v is Fraction))
                return true;

            if (u is Product &&
                (v is Power || v is Sum || v is Function || v is Symbol))
                return Compare(u, new Product(v));

            if (u is Power && (v is Sum || v is Function || v is Symbol))
                return Compare(u, new Power(v, new Integer(1)));
            
            if (u is Sum && (v is Function || v is Symbol))
                return Compare(u, new Sum(v));

            if (u is Function && v is Symbol)
            {
                var u_ = (Function)u;
                var v_ = (Symbol)v;

                return u_.name == v_.name ?
                    false :
                    Compare(new Symbol(u_.name), v);
            }

            return !Compare(v, u);
        }
    }

    public static class Operators
    {
        //public static Object operator +(Object a, Object b)
        //{
        //    return new Sum(a, b).Simplify();
        //}
    }

    class Power : MathObject
    {
        public MathObject bas;
        public MathObject exp;

        public Power(MathObject a, MathObject b) { bas = a; exp = b; }

        public override string ToString()
        { return "Power(" + bas + ", " + exp + ")"; }

        public static bool operator ==(Power a, Power b)
        { return a.bas == b.bas && a.exp == b.exp; }

        public static bool operator !=(Power a, Power b)
        { return !(a == b); }

        public MathObject Simplify()
        {
            var v = bas;
            var w = exp;

            if (v is Integer && ((Integer)v).val == 0) return new Integer(0);
            if (v is Integer && ((Integer)v).val == 1) return new Integer(1);
            if (w is Integer && ((Integer)w).val == 0) return new Integer(1);
            if (w is Integer && ((Integer)w).val == 1) return v;

            // Logic from MPL/Scheme:
            //
            //if (v is Integer && w is Integer)
            //    return
            //        new Integer(
            //            (int)Math.Pow(((Integer)v).val, ((Integer)w).val));
            
            // C# doesn't have built-in rationals. So:
            // 1 / 3 -> 3 ^ -1 -> 0.333... -> (int)... -> 0
                        
            //if (v is Integer && w is Integer && ((Integer)w).val > 1)
            //    return
            //        new Integer(
            //            (int)Math.Pow(((Integer)v).val, ((Integer)w).val));

            var n = w;

            if (v is Integer || v is Fraction)
                return Rational.SimplifyRNE(new Power(v, n));
            
            if (v is Power && w is Integer)
                return
                    new Power(
                        ((Power)v).bas,
                        new Product(((Power)v).exp, w)).Simplify();

            if (v is Product && w is Integer)
            {
                var list = new List<MathObject>();

                ((Product)v).elts.ForEach(elt => list.Add(new Power(elt, w)));

                return new Product() { elts = list }.Simplify();
            }

            return new Power(v, w);
        }
    }

    class Product : MathObject
    {
        public List<MathObject> elts;

        public Product(params MathObject[] ls)
        { elts = new List<MathObject>(ls); }

        public override string ToString()
        {
            var str = new StringBuilder();

            str.Append("Product(");

            for (var i = 0; i < elts.Count - 1; i++)
            {
                str.Append(elts[i]);
                str.Append(", ");
            }

            str.Append(elts[elts.Count - 1]);
            str.Append(")");

            return str.ToString();
        }

        //public string PrettyPrint(int precedence = 0)
        //{
        //    var str = new StringBuilder();

        //    for (var i = 0; i < elts.Count - 1; i++)
        //    {
        //        str.Append(elts[i]);
        //        str.Append(" ");
        //    }

        //}

        //////////////////////////////////////////////////////////////////////
        public override int GetHashCode() { return elts.GetHashCode(); }

        public override bool Equals(object obj)
        { return ListUtils.equal(elts, ((Product)obj).elts); }

        public static bool operator ==(Product a, Product b)
        { return ListUtils.equal(a.elts, b.elts); }

        public static bool operator !=(Product a, Product b)
        { return !(a.elts == b.elts); }
        //////////////////////////////////////////////////////////////////////

        static List<MathObject> MergeProducts(List<MathObject> pElts, List<MathObject> qElts)
        {
            if (pElts.Count == 0) return qElts;
            if (qElts.Count == 0) return pElts;

            var p = pElts[0];
            var ps = pElts.Cdr();

            var q = qElts[0];
            var qs = qElts.Cdr();

            var res = RecursiveSimplify(new List<MathObject>() { p, q });

            if (res.Count == 0) return MergeProducts(ps, qs);

            if (res.Count == 1) return MergeProducts(ps, qs).Cons(res[0]);

            if (ListUtils.equal(res, new List<MathObject>() { p, q }))
                return MergeProducts(ps, qElts).Cons(p);

            if (ListUtils.equal(res, new List<MathObject>() { q, p }))
                return MergeProducts(pElts, qs).Cons(q);

            throw new Exception();
        }

        public static List<MathObject> RecursiveSimplify(List<MathObject> elts)
        {
            if (elts.Count == 2)
            {
                if (elts[0] is Product && elts[1] is Product)
                    return MergeProducts(
                        ((Product)elts[0]).elts,
                        ((Product)elts[1]).elts);

                if (elts[0] is Product)
                    return MergeProducts(
                        ((Product)elts[0]).elts,
                        new List<MathObject>() { elts[1] });

                if (elts[1] is Product)
                    return MergeProducts(
                        new List<MathObject>() { elts[0] },
                        ((Product)elts[1]).elts);

                if ((elts[0] is Integer || elts[0] is Fraction)
                    &&
                    (elts[1] is Integer || elts[1] is Fraction))
                {
                    var P =
                        Rational.SimplifyRNE(new Product(elts[0], elts[1]));

                    if (P is Integer && ((Integer)P).val == 1)
                        return new List<MathObject>() { };

                    return new List<MathObject>() { P };
                }

                //if (elts[0] is Integer && elts[1] is Integer)
                //{
                //    var res = ((Integer)elts[0]).val * ((Integer)elts[1]).val;

                //    return res == 1 ?
                //        new List<MathObject>() :
                //        new List<MathObject>() { new Integer(res) };
                //}

                if (elts[0] is Integer && ((Integer)elts[0]).val == 1)
                    return new List<MathObject>() { elts[1] };

                if (elts[1] is Integer && ((Integer)elts[1]).val == 1)
                    return new List<MathObject>() { elts[0] };

                var p = elts[0];
                var q = elts[1];

                if (MiscUtils.equal(OrderRelation.Base(p), OrderRelation.Base(q)))
                {
                    var res =
                        new Power(
                            OrderRelation.Base(p),
                            new Sum(
                                OrderRelation.Exponent(p),
                                OrderRelation.Exponent(q)).Simplify()
                            ).Simplify();

                    if (res is Integer && ((Integer)res).val == 1)
                        return new List<MathObject>() { };
                    else
                        return new List<MathObject>() { res };
                }

                if (OrderRelation.Compare(q, p))
                    return new List<MathObject>() { q, p };

                return new List<MathObject>() { p, q };
            }

            if (elts[0] is Product)
                return
                    MergeProducts(
                        ((Product)elts[0]).elts,
                        RecursiveSimplify(elts.Cdr()));

            return MergeProducts(
                new List<MathObject>() { elts[0] },
                RecursiveSimplify(elts.Cdr()));

            throw new Exception();
        }

        public MathObject Simplify()
        {
            if (elts.Count == 1) return elts[0];

            Func<MathObject, bool> IsZero = obj =>
                {
                    if (obj is Integer) return ((Integer)obj).val == 0;
                    return false;
                };

            if (elts.Any(IsZero)) return new Integer(0);

            var res = RecursiveSimplify(elts);

            if (res.IsEmpty()) return new Integer(1);

            if (res.Count == 1) return res[0];

            return new Product() { elts = res };
        }
    }
    
    class Sum : MathObject
    {
        public List<MathObject> elts;

        public Sum(params MathObject[] ls)
        { elts = new List<MathObject>(ls); }

        //////////////////////////////////////////////////////////////////////
        public override int GetHashCode()
        { return elts.GetHashCode(); }

        public override bool Equals(object obj)
        { return ListUtils.equal(elts, ((Sum)obj).elts); }
        
        public static bool operator ==(Sum a, Sum b)
        { return ListUtils.equal(a.elts, b.elts); }

        public static bool operator !=(Sum a, Sum b)
        { return !(a.elts == b.elts); }
        //////////////////////////////////////////////////////////////////////

        static List<MathObject> MergeSums(List<MathObject> pElts, List<MathObject> qElts)
        {
            if (pElts.Count == 0) return qElts;
            if (qElts.Count == 0) return pElts;

            var p = pElts[0];
            var ps = pElts.Cdr();

            var q = qElts[0];
            var qs = qElts.Cdr();

            var res = RecursiveSimplify(new List<MathObject>() { p, q });

            if (res.Count == 0) return MergeSums(ps, qs);

            if (res.Count == 1) return MergeSums(ps, qs).Cons(res[0]);
            
            if (ListUtils.equal(res, new List<MathObject>() { p, q }))
                return MergeSums(ps, qElts).Cons(p);

            if (ListUtils.equal(res, new List<MathObject>() { q, p }))
                return MergeSums(pElts, qs).Cons(q);

            throw new Exception();
        }

        static List<MathObject> RecursiveSimplify(List<MathObject> elts)
        {
            if (elts.Count == 2)
            {
                if (elts[0] is Sum && elts[1] is Sum)
                    return MergeSums(
                        ((Sum)elts[0]).elts,
                        ((Sum)elts[1]).elts);

                if (elts[0] is Sum)
                    return MergeSums(
                        ((Sum)elts[0]).elts,
                        new List<MathObject>() { elts[1] });
                
                if (elts[1] is Sum)
                    return MergeSums(
                        new List<MathObject>() { elts[0] },
                        ((Sum)elts[1]).elts);

                if ((elts[0] is Integer || elts[0] is Fraction)
                    &&
                    (elts[1] is Integer || elts[1] is Fraction))
                {
                    var P =
                        Rational.SimplifyRNE(new Sum(elts[0], elts[1]));

                    if (P is Integer && ((Integer)P).val == 1)
                        return new List<MathObject>() { };

                    return new List<MathObject>() { P };
                }

                if (elts[0] is Integer && elts[1] is Integer)
                {
                    var res = ((Integer)elts[0]).val + ((Integer)elts[1]).val;

                    return res == 0 ?
                        new List<MathObject>() :
                        new List<MathObject>() { new Integer(res) };
                }

                if (elts[0] is Integer && ((Integer)elts[0]).val == 0)
                    return new List<MathObject>() { elts[1] };

                if (elts[1] is Integer && ((Integer)elts[1]).val == 0)
                    return new List<MathObject>() { elts[0] };

                var p = elts[0];
                var q = elts[1];

                if (MiscUtils.equal(OrderRelation.Term(p), OrderRelation.Term(q)))
                {
                    var res =
                        new Product(
                            OrderRelation.Term(p),
                            new Sum(
                                OrderRelation.Const(p),
                                OrderRelation.Const(q)).Simplify()
                            ).Simplify();

                    if (res is Integer && ((Integer)res).val == 0)
                        return new List<MathObject>() {};
                    else
                        return new List<MathObject>() { res };
                }

                if (OrderRelation.Compare(q, p))
                    return new List<MathObject>() { q, p };

                return new List<MathObject>() { p, q };
            }

            if (elts[0] is Sum)
                return
                    MergeSums(
                        ((Sum)elts[0]).elts, RecursiveSimplify(elts.Cdr()));

            return MergeSums(
                new List<MathObject>() { elts[0] }, RecursiveSimplify(elts.Cdr()));
        }

        public MathObject Simplify()
        {
            if (elts.Count == 1) return elts[0];

            var res = RecursiveSimplify(elts);

            if (res.Count == 0) return new Integer(0);
            if (res.Count == 1) return res[0];

            return new Sum() { elts = res };
        }

        //////////////////////////////////////////////////////////////////////
        public override string ToString()
        {
            var str = new StringBuilder();

            str.Append("Sum(");

            for (var i = 0; i < elts.Count - 1; i++)
            {
                str.Append(elts[i]);
                str.Append(", ");
            }

            str.Append(elts[elts.Count - 1]);
            str.Append(")");

            return str.ToString();
        }

        public static MathObject operator +(Sum a, MathObject b)
        { return new Sum(a, b).Simplify(); }
    }

    class Difference : MathObject
    {
        public List<MathObject> elts;

        public Difference(params MathObject[] ls)
        { elts = new List<MathObject>(ls); }

        public MathObject Simplify()
        {
            if (elts.Count == 1)
                return new Product(new Integer(-1), elts[0]).Simplify();

            if (elts.Count == 2)
                return
                    new Sum(
                        elts[0],
                        new Product(new Integer(-1), elts[1]).Simplify()
                        ).Simplify();

            throw new Exception();
        }
    }

    class Quotient : MathObject
    {
        public List<MathObject> elts;

        public Quotient(params MathObject[] ls)
        { elts = new List<MathObject>(ls); }

        public MathObject Simplify()
        {
            return
                new Product(
                    elts[0],
                    new Power(elts[1], new Integer(-1)).Simplify()
                ).Simplify();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            {
                var x = new Symbol("x");
                var y = new Symbol("y");
                var z = new Symbol("z");

                Console.WriteLine((x + x) == (2 * x));

                Console.WriteLine((x + x + x) == (3 * x));

                Console.WriteLine((5 + x + 2) == (7 + x));

                Console.WriteLine((3 + x + 5 + x) == (8 + 2 * x));

                Console.WriteLine((4 * x + 3 * x) == (7 * x));

                Console.WriteLine((x + y + z + x + y + z) == (2 * x + 2 * y + 2 * z));

                Console.WriteLine(MiscUtils.PrettyString(
                    10 - x
                ));

                Console.WriteLine(
                    x * y / 3
                );

                Console.WriteLine(x / y);

                Console.WriteLine(x / 3);

                // Console.WriteLine(6 * x * y / 3);

                Console.WriteLine(6 * x * y / 3);

                Console.WriteLine(new Fraction(new Integer(1), new Integer(3)));

                //var res = new Quotient(x, new Integer(3));
                //res.Simplify();

                //Console.WriteLine(Math.Pow(3, -1));

                //Console.WriteLine(1 / 3);


            }
            Console.ReadLine();
        }
    }
}