Polynomial.Net

• Download source - 42.55 KB

Introduction

Polynomials: A polynomial is a mathematical expression involving a sum of powers in one or more variables multiplied by coefficients.

Background

As it’s clear in the definition of Polynomial, we have some main concepts in modelling a polynomial to a .NET class:

1. Term
2. TermCollection
3. Polynomial class

Term demonstrates a part of polynomial which includes the variable, Power and Coefficients.
A collection of Terms will create a polynomial expression.
In Modelling a Polynomial by .NET Technology, we must consider the concepts above. So we start with Polynomial class. In this article, we call Polynomial in abstract word (Poly).
Poly class has a Primary Member named TermCollection. TermCollection inherits from CollectionBase class and it’s a collection of Term class.
Term class has two Properties (Power, Coefficient) and two constructors. One of the Term constructors parses the Power and Coefficient from a String Expression. String Expression may be something like these Strings: “x”, “-x^2”, “3x^2”, “-3”…

Poly class has a constructor like Term class to parse Terms from a String Expression. These methods will be explained in this article.

Using the Code

To clarify the Poly class in simple words, I just try to explain the nested classes from bottom to top. At the last level of nested classes which we are using in our Poly class, there is Term class.

Term

Term class in the first constructor takes two parameters and passes them to the Power and Coefficient properties. This constructor will use in case of creating a simple instance of Term in code not in Class client.

/// <summary>
/// Simple Constructor which Create a new Instance of Term Class
/// With 2 parameters
///  
/// </summary>
/// <param name="power"></param>
/// <param name="coefficient"></param>
public Term(int power,int coefficient)
{
    this.Power = power;
    this.Coefficient = coefficient;
}

The second Constructor takes a string expression and parses the Power and coefficient directly from the string. To parse the properties from string parameter, these cases will occur:

/// <summary>
/// Constructor Overload which Create a new Instance of Term Class
/// With a simple string and try to read the Power and Coefficient
/// by identifying the input string
/// </summary>
/// <param name="TermExpression"></param>
public Term(string TermExpression)
{
    if (TermExpression.Length > 0)
    {
        if (TermExpression.IndexOf("x^") > -1)
        {
            string CoefficientString = 
		TermExpression.Substring(0, TermExpression.IndexOf("x^"));
            int IndexofX = TermExpression.IndexOf("x^");
            string PowerString = TermExpression.Substring
		(IndexofX + 2, (TermExpression.Length -1) - (IndexofX + 1));
            if (CoefficientString == "-")
                this.Coefficient = -1;
            else if (CoefficientString == "+" | CoefficientString == "")
                this.Coefficient = 1;
            else
                this.Coefficient = int.Parse(CoefficientString);
            
            this.Power = int.Parse(PowerString);
        }
        else if (TermExpression.IndexOf("x") > -1)
        {
            this.Power = 1;
            string CoefficientString = TermExpression.Substring
			(0, TermExpression.IndexOf("x"));
            if (CoefficientString == "-")
                this.Coefficient = -1;
            else if (CoefficientString == "+" | CoefficientString == "")
                this.Coefficient = 1;
            else
                this.Coefficient = int.Parse(CoefficientString);
        }
        else
        {
            this.Power = 0;
            this.Coefficient = int.Parse(TermExpression);
        }
    }
    else
    {
        this.Power = 0;
        this.Coefficient = 0;
    }
}

At last overriding .ToString() method of Term class will write the string format of Term at output.

public override string ToString()
{
    string Result = string.Empty;
    if (Coefficient != 0)
    {
        if (this.Coefficient > 0)
            Result += "+";
        else
            Result += "-";
            
        if (this.Power == 0)
            Result += (this.Coefficient < 0 ? this.Coefficient * -1 : 
		this.Coefficient).ToString();
        else if (this.Power == 1)
            if (this.Coefficient > 1 | this.Coefficient < -1)
                Result += string.Format("{0}x",(this.Coefficient <0 ? 
		this.Coefficient * -1 : this.Coefficient).ToString());
            else
                Result += "x";
        else
            if (this.Coefficient > 1 | this.Coefficient < -1)
                Result += string.Format("{0}x^{1}", 
		(this.Coefficient < 0 ? this.Coefficient * -1 : 
		this.Coefficient).ToString(), this.Power.ToString());
            else
                Result += string.Format("x^{0}",this.Power.ToString());
    }
    return Result;
}

Now we can store Terms of a polynomial expression in an array or ArrayList or etc… Maybe a custom Collection class is the best choice.

TermCollection

TermCollection is a Collection class that inherits from Collectionbase. Some methods are overridden from Collectionbase but to handle taking terms we must check the Power of Term in Add method of TermCollection. A polynomial by this format is not suitable: “3x^2+2x^2+x^2” (this expression in fact is “6x^2”).

So to prevent these mistakes, we have to write a method to check the Power of input values in Add method of TermCollection class.

/// <summary>
/// Check if there is any Term by the given Power.
/// </summary>
/// <param name="p"></param>
/// <returns></returns>
public bool HasTermByPower(int p)
{
    foreach (Term t in List)
    {
        if (t.Power == p)
            return true;
    }
    return false;
}

AddToEqualPower() method will Add the Coefficient of Input Term to the Current Term by the equal Power.

/// <summary>
/// This will Add the Term to the Same Power Term if it's already exists in the Collection.
/// This mean we Plus the New Terms to the Currnet Polynomial
/// </summary>
/// <param name="value"></param>
public void AddToEqualPower(Term value)
{
    foreach (Term t in List)
    {
        if (t.Power == value.Power)
        t.Coefficient += value.Coefficient;
    }
}

At last, we must call the previous methods in the Add method of TermCollection class:

/// <summary>
/// Modified Add Method: 
/// First check the Coefficient Value. 
/// this Method checks if there is any Term by the Same Input Power.
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Add(Term value)
{
    if (value.Coefficient != 0)
    {
        if (this.HasTermByPower(value.Power))
        {
            this.AddToEqualPower(value);
            return -1;
        }
        else
            return (List.Add(value));
    }
    else
        return -1;
}

Notice: A Term by the zero Coefficiant is not a valid Term so we should prevent adding these Terms to the TermCollection.

TermCollection has some additional methods like Sort to Sorting the Terms Order by Power. Later in Poly class, we will navigate the TermCollection to write the Complete Polynomial Expression using the .ToString() method of Term class. So, sorting the Terms will help us in displaying Terms to the regular style.

/// <summary>
/// Array Sort Type
/// Values: ASC , DESC
/// </summary>
public enum SortType
{
    ASC = 0,
    DES = 1
}

/// <summary>
/// Sor Method: Sort Items of Collection in ASC or DESC Order.
/// </summary>
/// <param name="Order">SortOrder values : ASC or DESC</param>
public void Sort(SortType Order)
{
    TermCollection result = new TermCollection();
    if (Order == SortType.ASC)
    {
        while (this.Length > 0)
        {
            Term MinTerm = this[0];
            foreach (Term t in List)
            {
                if (t.Power < MinTerm.Power)
                {
                    MinTerm = t;
                }
            }
            result.Add(MinTerm);
            this.Remove(MinTerm);
        }
    }
    else
    {
        while (this.Length > 0)
        {
            Term MaxTerm = this[0];
            foreach (Term t in List)
            {
                if (t.Power > MaxTerm.Power)
                {
                    MaxTerm = t;
                }
            }
            result.Add(MaxTerm);
            this.Remove(MaxTerm);
        }
    }       
    this.Clear();
    foreach (Term t in result)
    {
        this.Add(t);
    }
}

Poly

Poly class has a Property named Terms which is a TermCollection class. This property will store the terms of Polynomial.

The first constructor of Poly class takes a TermCollection parameter to create a simple instance of Poly. This constructor just used in Code not Class Client.

The second constructor takes a String expression that contains the Polynomial Expression. First of all, this constructor validates the Expression by this static method:

/// <summary>
/// Static method which Validate the input Expression
/// </summary>
/// <param name="Expression"></param>
/// <returns></returns>
public static bool ValidateExpression(string Expression)
{
    if (Expression.Length == 0)
        return false;
        
    Expression = Expression.Trim();
    Expression = Expression.Replace(" ", "");
    while (Expression.IndexOf("--") > -1 | Expression.IndexOf("++") > -1 | 
	Expression.IndexOf("^^") > -1 | Expression.IndexOf("xx") > -1)
    {
        Expression = Expression.Replace("--", "-");
        Expression = Expression.Replace("++", "+");
        Expression = Expression.Replace("^^", "^");
        Expression = Expression.Replace("xx", "x");
    }
    string ValidChars = "+-x1234567890^";
    bool result = true;
    foreach (char c in Expression)
    {
        if (ValidChars.IndexOf(c) == -1)
            result = false;
    }
    return result;
        }

Any Term in Polynomial Expression will end up with a + or - Character. (3x^2 + 2x - 5) Reading these terms is possible by navigating the Chars of the Polynomial Expression. .ReadPolyExpression() method will do this:

/// <summary>
/// Read Method will Identify any Term in the Expression and Create a new Instance of 
/// Term Class and add it to the TermCollection
/// </summary>
/// <param name="PolyExpression">input string of Polynomial Expression</param>
private void ReadPolyExpression(string PolyExpression)
{
    if(ValidateExpression(PolyExpression))
    {
        string NextChar = string.Empty;
        string NextTerm = string.Empty;
        for (int i = 0 ; i < PolyExpression.Length; i++)
        {
            NextChar = PolyExpression.Substring(i, 1);
            if ((NextChar == "-" | NextChar == "+") & i > 0)
            {
                Term TermItem = new Term(NextTerm);
                this.Terms.Add(TermItem);
                NextTerm = string.Empty;
            }
            NextTerm += NextChar;
        }
        Term Item = new Term(NextTerm);
        this.Terms.Add(Item);
        
        this.Terms.Sort(TermCollection.SortType.ASC);
    }
    else
    {
        throw new Exception("Invalid Polynomial Expression");
    }
}

Now we have the complete class of Polynomials, but still something is needed. By creating a new type (specially a mathematic one), we must take a look to the Operators of this New Type. If you use simple Operator + to plus to instance of Poly class, nothing will happen. The best solution is Operator Overloading in this New Type.

Operator Overloading

What does it mean? When you try to use something like this:

int a = 3 + 4;

In fact, you call this method:

int.+(int FirstArgument, int SecondArgument) 

like:

int.+(3,4); 

This method will return an int variable by the value of 7. Now we want to create our + method of our New Type (Poly class). We must override the Plus (+) operator in our class:

/// <summary>
/// Plus Operator: 
/// Add Method of TermsCollection will Check the Power of each Term And if it's already 
/// exists in the Collection Just Plus the Coefficient of the Term 
/// and This Mean Plus Operation.
/// So We Simply Add the Terms of Second Poly to the First one.
/// </summary>
/// <param name="p1"></param>
/// <param name="p2"></param>
/// <returns></returns>
public static Poly operator +(Poly p1, Poly p2)
{
    Poly result = new Poly(p1.ToString());
    foreach (Term t in p2.Terms)
        result.Terms.Add(t);
    return result;
}

Notice: When we're going to Plus two Poly Instances, we are trying to plus the Coefficient of Equal Powers. this means we have "3x^2+4" + "2x^2-2" is "5x^2+2". We did it in the Add Method of TermCollection, so to overload the + Operator, we just Add the Terms of Second Poly Instance to the First one.

Next Operator is - . Minus (-) Operator is Plusing the First Poly instance by the Negetive value of the Second Poly Instance. So at first, we make the second Poly into the Negetive value and then Plus it by the first one.

/// <summary>
/// Minus Operations: Like Plus Operation but at first 
/// we just Make the Second Poly to the Negetive Value.
/// </summary>
/// <param name="p1"></param>
/// <param name="p2"></param>
/// <returns></returns>
public static Poly operator -(Poly p1, Poly p2)
{
    Poly result = new Poly(p1.ToString());
    Poly NegetiveP2 = new Poly(p2.ToString());
    foreach (Term t in NegetiveP2.Terms)
        t.Coefficient *= -1;
        
    return result + NegetiveP2;
}

Next Operator is Multiple (*):

/// <summary>
/// Multiple Operation: For each term in the First Poly 
/// We Multiple it in the Each Term of Second Poly
/// </summary>
/// <param name="p1"></param>
/// <param name="p2"></param>
/// <returns></returns>
public static Poly operator *(Poly p1, Poly p2)
{
    TermCollection result = new TermCollection();
    int counter = 0;
    foreach (Term t1 in p1.Terms)
    {
        foreach (Term t2 in p2.Terms)
        {
            result.Add(new Term(t1.Power + t2.Power,t1.Coefficient * t2.Coefficient));
            counter++;
        }
    }
    return new Poly(result);
}

The next one is Divide (/):

/// <summary>
/// 
/// </summary>
/// <param name="p1"></param>
/// <param name="p2"></param>
/// <returns></returns>
public static Poly operator /(Poly p1, Poly p2)
{
    p1.Terms.Sort(TermCollection.SortType.DES);
    p2.Terms.Sort(TermCollection.SortType.DES);
    TermCollection resultTerms = new TermCollection();
    if (p1.Terms[0].Power < p2.Terms[0].Power)
        throw new Exception("Invalid Division: P1.MaxPower is Lower than P2.MaxPower");
    while(p1.Terms[0].Power > p2.Terms[0].Power)
    {
        Term NextResult = new Term(p1.Terms[0].Power - 
	p2.Terms[0].Power, p1.Terms[0].Coefficient / p2.Terms[0].Coefficient);
        resultTerms.Add(NextResult);
        Poly TempPoly = NextResult;
        
        Poly NewPoly = TempPoly * p2;
        p1 = p1 - NewPoly;
    }
    return new Poly(resultTerms);
}

Next two operators: ++ and -- are a kind of Plus (+) operators:

/// <summary>
/// this will Create a new Poly by the Value of 1 and Plus it to the First Poly.
/// </summary>
/// <param name="p1"></param>
/// <returns></returns>
public static Poly operator ++(Poly p1)
{
    Poly p2 = new Poly("1");
    p1 = p1 + p2;
    return p1;
}

/// <summary>
/// this will Create a new Poly by the Value of -1 and Plus it to the First Poly.
/// </summary>
/// <param name="p1"></param>
/// <returns></returns>
public static Poly operator --(Poly p1)
{
    Poly p2 = new Poly("-1");
    p1 = p1 + p2;
    return p1;
}

Overloading Equal Operator (=) - Implicit Conversion:

Overloading (=) means you are trying to convert another type to the Poly Type. This means Implicit Converstion. If you didn't overload the (=) something like this is a syntax Error:

Poly myPoly = "4x^2+5x";

By Overloading (=) Operator, you can handle any type conversion in implicit mode:

/// <summary>
/// Implicit Conversion : this will Convert the single Term to the Poly. 
/// First it Creates a new Instance of TermCollection and Add The Term to it. 
/// Second Creates a new Poly by the TermCollection and Return it.
/// </summary>
/// <param name="t"></param>
/// <returns></returns>
public static implicit operator Poly(Term t)
{
    TermCollection Terms = new TermCollection();
    Terms.Add(t);
    return new Poly(Terms);
}

/// <summary>
/// Implicit Conversion: this will Create new Instance of Poly by the String Constructor
/// And return it.
/// </summary>
/// <param name="expression"></param>
/// <returns></returns>
public static implicit operator Poly(string expression)
{
    return new Poly(expression);
}

/// <summary>
/// Implicit Conversion: this will Create new Instance of Poly by the String Constructor
/// And return it.
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public static implicit operator Poly(int value)
{
    return new Poly(value.ToString());
}

At last a .Calculate() method will calculate the Polynomial by the value of X.

Points of Interest

Operator overloading is the most useful feature of the .NET technology. I didn't know that I can Overload the Operators and Handling Implicit Conversion is very interesting.

History

Polynomial.NET first version:

Poly Class
Term Class
TermCollection Class

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)