Skip to content

Instantly share code, notes, and snippets.

@fabrizioc1
Created February 23, 2012 04:23
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save fabrizioc1/1890181 to your computer and use it in GitHub Desktop.
Polynomial Data Structure
/*
* Question: Create a data structure to represent polynomial addition and substraction
* Run the code online: http://ideone.com/s5qjU
*/
import static org.junit.Assert.*;
import org.junit.Test;
import java.util.*;
public class PolynomialTest
{
public static class Term
implements Cloneable
{
int coefficient;
int power;
public Term(int coefficient, int power) {
this.coefficient = coefficient;
this.power = power;
}
public String toString() {
StringBuffer display = new StringBuffer();
if (power == 0) {
display.append(coefficient);
}
else if (power > 0) {
if (coefficient != 1) display.append(coefficient);
display.append('x');
if (power > 1) display.append('^').append(power);
}
return display.toString();
}
public Term add(Term other) {
if (this.power == other.power) this.coefficient += other.coefficient;
return this;
}
protected Object clone() {
Term term = new Term(this.coefficient,this.power);
return term;
}
public boolean equals(Object o) {
if (!(o instanceof Term)) return false;
Term other = (Term)o;
return this.coefficient == other.coefficient && this.power == other.power;
}
}
public static class Polynomial
{
Map<Integer,Term> terms;
public Polynomial() {
this.terms = new TreeMap<Integer,Term>();
}
public Polynomial(Collection<Term> list) {
this();
for (Term term : list) this.add((Term)term.clone());
}
public Polynomial add(Term other) {
Term term = terms.get(other.power);
terms.put(other.power,(term == null) ? other : term.add(other));
return this;
}
public Polynomial add(int coefficient, int power) {
add(new Term(coefficient,power));
return this;
}
public Polynomial add(Polynomial other) {
Polynomial poly = new Polynomial(getTerms());
for (Term term : other.getTerms()) poly.add(term);
return poly;
}
public void plus(Polynomial other) {
for (Term term : other.getTerms()) this.add(term);
}
public Polynomial multiply(Polynomial other) {
Polynomial poly = new Polynomial();
for (Term first : this.getTerms()) {
Polynomial current = new Polynomial();
for (Term second : other.getTerms()) {
Term product = new Term(first.coefficient*second.coefficient,first.power+second.power);
current.add(product);
}
poly.plus(current);
}
return poly;
}
public String toString() {
StringBuffer display = new StringBuffer();
int count = 0;
for (Term term : getTerms()) {
display.append(term.toString());
if (count<terms.size()-1) display.append('+');
count++;
}
return display.toString();
}
public Collection<Term> getTerms() {
return this.terms.values();
}
public boolean equals(Object o) {
if (!(o instanceof Polynomial)) return false;
Polynomial other = (Polynomial)o;
return this.terms.equals(other.terms);
}
}
// x^2 + 2x
// + 1x + 2
//----------------
// x^2 + 3x + 2
@Test public void testPolynomialAddition1()
{
System.out.println();
Polynomial first = new Polynomial().add(new Term(1,2)).add(new Term(2,1));
Polynomial second = new Polynomial().add(new Term(1,1)).add(new Term(2,0));
Polynomial expect = new Polynomial().add(new Term(1,2)).add(new Term(3,1)).add(new Term(2,0));
Polynomial output = first.add(second);
System.out.println("first = "+first);
System.out.println("second = "+second);
System.out.println("sum = "+output);
assertEquals(expect,output);
}
// x + 1
// + x + 2
//---------------
// 2x + 3
@Test public void testPolynomialAddition2()
{
System.out.println();
Polynomial first = new Polynomial().add(new Term(1,1)).add(new Term(1,0));
Polynomial second = new Polynomial().add(new Term(1,1)).add(new Term(2,0));
Polynomial expect = new Polynomial().add(new Term(2,1)).add(new Term(3,0));
Polynomial output = first.add(second);
System.out.println("first = "+first);
System.out.println("second = "+second);
System.out.println("sum = "+output);
assertEquals(expect,output);
}
// x + 1
// * x + 2
// -------------------------
// x*(x + 2) + 1*(x + 2)
// x^2 + 2x + x + 2
// x^2 + 3x + 2
@Test public void testPolynomialMultiply()
{
System.out.println();
Polynomial first = new Polynomial().add(new Term(1,1)).add(new Term(1,0));
Polynomial second = new Polynomial().add(new Term(1,1)).add(new Term(2,0));
Polynomial output = first.multiply(second);
Polynomial expect = new Polynomial().add(new Term(1,2)).add(new Term(3,1)).add(new Term(2,0));
System.out.println("first = "+first);
System.out.println("second = "+second);
System.out.println("product = "+output);
assertEquals(expect,output);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment