Adding Polynomials (Linked Lists)......Bug Help

Question

I have written a program that creates nodes that in this class are parts of polynomials and then the two polynomials get added together to become one polynomial (list of nodes). All my code compiles so the only problem I am having is that the nodes are not inserting into the polynomial via the insert method I have in polynomial.java and when running the program it does create nodes and displays them in the 2x^2 format but when it comes to add the polynomials together it displays o as the polynomials, so if anyone can figure out whats wrong and what I can do to fix it it would be much appreciated.

Here is the code:

import java.util.Scanner;

class Polynomial{

    public termNode head;

    public Polynomial()
    {
        head = null;
    }

    public boolean isEmpty()
    {
        return (head == null);
    }

    public void display()
    {
        if (head == null)
            System.out.print("0");
        else
            for(termNode cur = head; cur != null; cur = cur.getNext())
                {
                    System.out.println(cur);
                }
    }

    public void insert(termNode newNode)
    {
        termNode prev = null;
        termNode cur = head;
        while (cur!=null && (newNode.compareTo(cur)<0))
            {
                prev = null;
                cur = cur.getNext();
            }
        if (prev == null)
            {
                newNode.setNext(head);
                head = newNode;
            }
        else
            {
                newNode.setNext(cur);
                prev.setNext(newNode);
            }
}
 public void readPolynomial(Scanner kb)
    {
        boolean done = false;
        double coefficient;
        int exponent;
        termNode term;
        head = null; //UNLINK ANY PREVIOUS POLYNOMIAL
        System.out.println("Enter 0 and 0 to end.");
        System.out.print("coefficient: ");
        coefficient = kb.nextDouble();
        System.out.println(coefficient);
        System.out.print("exponent: ");
        exponent = kb.nextInt();
        System.out.println(exponent);
        done = (coefficient == 0 && exponent == 0);
        while(!done)
            {
                Polynomial poly = new Polynomial();
                term = new termNode(coefficient,exponent);
                System.out.println(term);
                poly.insert(term);

                System.out.println("Enter 0 and 0 to end.");
                System.out.print("coefficient: ");
                coefficient = kb.nextDouble();
                System.out.println(coefficient);
                System.out.print("exponent: ");
                exponent = kb.nextInt();
                System.out.println(exponent);
                done = (coefficient==0 && exponent==0);
            }
    }
public static Polynomial add(Polynomial p, Polynomial q)
    {
        Polynomial r = new Polynomial();
        double coefficient;
        int exponent;
        termNode first = p.head;
        termNode second = q.head;
        termNode sum = r.head;
        termNode term;
        while (first != null && second != null)
            {
                if (first.getExp() == second.getExp())
                    {
                        if (first.getCoeff() != 0 && second.getCoeff() != 0);
                        {
                            double addCoeff = first.getCoeff() + second.getCoeff();
                            term = new termNode(addCoeff,first.getExp());
                            sum.setNext(term);
                            first.getNext();
                            second.getNext();
                        }
                    }
                else if (first.getExp() < second.getExp())
                    {
                        sum.setNext(second);
                        term = new termNode(second.getCoeff(),second.getExp());
                        sum.setNext(term);
                        second.getNext();
                    }
                else
 {
                        sum.setNext(first);
                        term = new termNode(first.getNext());
                        sum.setNext(term);
                        first.getNext();
                    }
            }
        while (first != null)
            {
                sum.setNext(first);
            }
        while (second != null)
            {
                sum.setNext(second);
            }
        return r;
    }
}

Here is my Node class:

class termNode implements Comparable
{
    private int exp;
    private double coeff;
    private termNode next;

    public termNode(double coefficient, int exponent)
    {
        coeff = coefficient;
        exp = exponent;
        next = null;
    }

    public termNode(termNode inTermNode)
    {
        coeff = inTermNode.coeff;
        exp = inTermNode.exp;
    }

    public void setData(double coefficient, int exponent)
    {
        coefficient = coeff;
        exponent = exp;
    }

    public double getCoeff()
    {
        return coeff;
    }

    public int getExp()
    {
        return exp;
    }

    public void setNext(termNode link)
    {
        next = link;
    }

    public termNode getNext()
    {
        return next;
    }
 public String toString()
    {
        if (exp == 0)
            {
                return(coeff + " ");
            }
        else if (exp == 1)
            {
                return(coeff + "x");
            }
        else
            {
                return(coeff + "x^" + exp);
            }
    }
 public int compareTo(Object other)
    {
        if(exp ==((termNode) other).exp)
            return 0;
        else if(exp < ((termNode) other).exp)
            return -1;
        else
            return 1;
    }

}

And here is my Test class to run the program.

import java.util.Scanner;

class PolyTest{

    public static void main(String [] args)
    {
        Scanner kb = new Scanner(System.in);
        Polynomial r;
        Polynomial p = new Polynomial();
        System.out.println("Enter first polynomial.");
        p.readPolynomial(kb);
        Polynomial q = new Polynomial();
        System.out.println();
        System.out.println("Enter second polynomial.");
        q.readPolynomial(kb);
        r = Polynomial.add(p,q);
        System.out.println();
        System.out.print("The sum of ");
        p.display();
        System.out.print(" and ");
        q.display();
        System.out.print(" is ");
        r.display();
    }
}

polygenelubricants · Accepted Answer

A few suggestions:

Class names by convention starts with uppercase, e.g. TermNode
Use generics, i.e. TermNode implements Comparable
In fact, it's probably even better to have Node instead

Bugs I saw:

prev = null; in insert
- Should be prev = cur;
- Consider factoring this out to a helper find-like method
In readPolynomial, you're creating a new Polynomial every iteration, and doesn't do anything to this.
- You want to either insert terms into this, or keep one Polynomial that you return at the end of a static readPolynomial method
while (first != null) sum.setNext(first);
- What are you trying to accomplish here? This is an infinite loop!

More suggestions:

It may be easier/more readable/etc to do add in two passes:
- merge polynomials first, making sure terms are properly ordered
  - 3x+1 and 2x+2 merges to 3x+2x+1+2
- Then simplify by merging any consecutive pairs of terms that have the same exponent
  - 3x+2x simplifies to 5x
Once you get it working, consider optimizing it to add in one pass if necessary
In fact, the polynomial merging can be done easily in O(N^2) using insert
- Get it correct first, optimize to O(N) later
While debugging/developing, print out the polynomials often. Do it after you read it. Do it after insertion. Do it after the first pass of add. Do it after the second pass.

Adding Polynomials (Linked Lists)......Bug Help

Answers (2)

Related Questions