Introduction
This project illustrates one way to implement addition and subtraction of polynomials in C#.
Background
As you remember from your first algebra class, in 3.14x3, 3.14 is the coefficient, x is the variable, and 3 is the exponent. This is called a term, and a polynomial is a sum of 1 or more terms. Adding and subtracting polynomials is quite simple. For example, to add 4x3 + 3x2 + 5x and 3x3 - 2x2 + 3x, you line up the like terms, and add the coefficients:
4x3 + 3x2 + 5x
3x3 - 2x2 + 3x
--------------
7x3 + 1x2 + 8x
Things can get tricky when the terms have multiple variables, for example, x3y2z4. Since this is mathematically identical to z4y2x3, if we represent the polynomial as a List
in C#, we will have to implement some type of sorting to keep all of our terms consistent. This is where Lambda Expressions are helpful. Lambda Expressions are a powerful feature of C# and are documented in numerous places on the web and in CodeProject so I will not attempt to explain them. Jon Skeet for one, does a great job of explaining Lambda Expressions.
Using the Code
The class Variable
stores a variable like x3 where Name
is 'x' and Exp
is 3. Note that we are using C#'s Auto Implemented Properties.
public class Variable
{
public char Name { get; set; }
public int Exp { get; set; }
}
The class Term
is used to store a term like 3.0x2y3 where 3.0 is the coefficient, and Vars
is a Generic List of two Variables, one where Name
is 'x' and Exp
is 2, and one where Name
is 'y' and Exp
is 3.
public class Term
{
public double Coefficient { get; set; }
public List<Variable> Vars { get; set; }
}
The class that stores the polynomial, Poly
, is simply a Generic List of Terms:
public class Poly
{
private List<Term> Terms { get; set; }
}
I admit the constructing of the polynomial in code is rather inelegant, and I plan on adding a parser to the next version to simplify the task. This then, is how we would build the two-term polynomial 3.5x3y2z4 - 2.7x2y3:
Poly polynomial1 = new Poly();
Term t10 = new Term(+3.5, new List<Variable>
{ new Variable('x', 3), new Variable('y', 2), new Variable('z', 4) });
Term t11 = new Term(-2.7, new List<Variable>
{ new Variable('x', 2), new Variable('y', 3) });
polynomial1.AddTerm(t10);
polynomial1.AddTerm(t11);
Console.WriteLine("{0}", polynomial1.ToString());
Note that ToString()
is overloaded and displays the polynomial like this:
+ 3.50x^3y^2z^4 - 2.70x^2y^3
When the two polynomials have terms that are identical, the coefficients are added as mentioned previously. This is done in the public Poly Sum(Poly addend)
method by going through each term of the polynomial and adding the coefficients. (In this version, I converted the lists to arrays to simplify this task.) However, suppose we wish to add two polynomials that have terms (ignoring the coefficients for the moment) that are mathematically identical, but for which the variables are in a different order, for example 10.0x3y2z4 and 20.0z4y2x3. The strategy I chose is to sort the variables alphabetically using this Lambda Expression in the AddTerm()
method:
term2.Vars.Sort((t1, t2) => t1.Name.CompareTo(t2.Name));
Now the polynomials will have the variables in the same order: 10.0x3y2z4 and 20.0z3y2z4. Also in AddTerm()
, I build a string
called sortString
that simply contains the variables and exponents without the coefficient to make it easy to compare two terms to see if they can be added. In this example, the sortString
is "x3y2z4". When we add two polynomials, as we march through the list of terms, and if the sortString
's are the same, that means we add the coefficients. Since it is customary to write a polynomial with the term with the highest coefficient of the first variable first, I use this Lambda Expression to sort all the terms:
Terms.Sort((t1, t2) => t2.SortString.CompareTo(t1.SortString));
The Sum()
method in the Poly
class assumes both polynomials have the same terms and differ only in their coefficient. The issue is what to do when there a term that is present in one polynomial but missing from the other. The strategy I chose is to add the missing term to the polynomial that is missing it with a coefficient of zero (I call this a "dummy" term"). This is implemented in the method Normalize(Poly p1, Poly p2)
in the Poly
class.
Points of Interest
The Term
class implements the IEquatable
interface. The Equals
method compares sortString
to determine if two terms are equivalent. I have included links in the source code that describe this interface.
History
- November 30th, 2014: Version 1