java - 使用递归将多项式加在一起

我需要使用递归方法将两个多项式加在一起。
这是针对过期的作业（我想类似的事情也会在测试中）。
主班：

public class Polynomial {

    private Node poly;


    public Polynomial(){
    poly = new Node();
    }

    private Polynomial(Node node){
    poly = node;
    }
    public void addTerm(int coef, int exp){
    Term term = new Term(coef, exp);
    Node node = new Node(term, null);

    Node iterator = poly;

    //if the list is empty just add the node
    if (poly.next == null){
        System.out.println("poly.next is null. adding node to first pos.");
        poly.next = node;
        return;
    }

    //if list isn't empty find the appropriate spot for it
    while (iterator.next != null){
        System.out.println("iterator.next != null...");
        if (exp < iterator.next.data.exp){
        System.out.println("\texp < iterator.next.data.exp");
        node.next = iterator.next;
        iterator.next = node;
        return;
        }
        if (exp == iterator.next.data.exp){
        System.out.println("\texp == iterator.next.data.exp");
        iterator.next.data.coef += coef;
        return;
        }
        iterator = iterator.next;
    }

    //if we get to this point then the list isn't empty
    //and it doesn't fit inside the list, hence it must
    //be added to the end of the list
    System.out.println("list wasn't empty, didn't fit inside");
    iterator.next = node;
    return;
    }

    @Override
    public String toString(){
    Node iterator = poly;
    String out = "";

    if (poly.next == null){
        return out;
    }
    while(iterator.next != null){
        out += iterator.next.data.coef;
        out += "*x^";
        out += iterator.next.data.exp;
        out += " + ";
        iterator = iterator.next;
    }
    return out.substring(0, out.lastIndexOf('+'));
    }



    public Polynomial addPolynomial (Polynomial that){
    Polynomial ret = new Polynomial();

    Polynomial iterator = this;

    return addPolynomial(that, ret, iterator);
    }

    public Polynomial addPolynomial(Polynomial that, Polynomial ret, Polynomial iterator){
    if (iterator.poly.next == null){
        return new Polynomial(that.poly);
    }

    if (that.poly.next == null){
        return new Polynomial(iterator.poly);
    }

    if (iterator.poly.next.data.exp < that.poly.next.data.exp){
        ret.addTerm(iterator.poly.next.data.coef, iterator.poly.next.data.exp);
        iterator.poly = iterator.poly.next;
        return iterator.addPolynomial(that);
    }

    if (iterator.poly.next.data.exp == that.poly.next.data.exp){
        ret.addTerm(iterator.poly.next.data.coef + that.poly.next.data.coef, iterator.poly.next.data.exp);
        iterator.poly = iterator.poly.next;
        that.poly = that.poly.next;
        return iterator.addPolynomial(that);
    }

    if (iterator.poly.next.data.exp > that.poly.next.data.exp){
        ret.addTerm(that.poly.next.data.coef, that.poly.next.data.exp);
        that.poly = that.poly.next;
        return iterator.addPolynomial(that);
    }
    return ret;
    }

    /*
     * Term
     */
    private class Term implements Comparable{
    int coef;
    int exp;

    public int getCoef() {
        return coef;
    }

    public void setCoef(int coef) {
        this.coef = coef;
    }

    public int getExp() {
        return exp;
    }

    public void setExp(int exp) {
        this.exp = exp;
    }

    public Term(int coef, int exp) {
        this.coef = coef;
        this.exp = exp;
    }
    public int compareTo(Object rhs){
        Term that = (Term)rhs;
        return this.exp - that.exp;
    }
    }//end Term


    /*
     * Node
     */
    private class Node{
    Term data;
    Node next;

    public Term getData() {
        return data;
    }

    public void setData(Term data) {
        this.data = data;
        this.next = null;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node() {
        this.data = null;
        this.next = null;
    }

    public Node(Term data, Node next) {
        this.data = data;
        this.next = next;
    }
    }//end Node




}

测试类别：

public class Polynomials {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Polynomial p1 = new Polynomial();
        Polynomial p2 = new Polynomial();
        Polynomial p0 = new Polynomial();
        p1.addTerm(1, 2);
        p1.addTerm(1, 4);
        p1.addTerm(1, 6);
    p2.addTerm(1, 1);
    p2.addTerm(1, 3);
    p2.addTerm(1, 5);
    System.out.println("p1 = " + p1.toString());
    System.out.println("p2 = " + p2.toString());

    System.out.println("Adding p1 to p2...");
    p0 = p1.addPolynomial(p2);
    System.out.println(p0.toString());
    }
}

最佳答案

您是否考虑过这种方式？

public class Polynomial {
public static void main(String[] args) {
    Polynomial p1 = new Polynomial();
    Polynomial p2 = new Polynomial();
    Polynomial p0 = new Polynomial();
    p1.addTerm(1, 2);
    p1.addTerm(1, 4);
    p1.addTerm(1, 6);
    p2.addTerm(1, 1);
    p2.addTerm(2, 3);
    p2.addTerm(2, 2);
    p2.addTerm(1, 5);
    System.out.println("p1 = " + p1.toString());
    System.out.println("p2 = " + p2.toString());

    System.out.println("Adding p1 to p2...");
    p0 = p1.addPolynomial(p2);
    System.out.println(p0.toString());

    for(int i = 0;i < 100;i++) {
        p1 = new Polynomial();
        p2 = new Polynomial();
        for(int j = 0;j < 4;j++) {
            p1.addTerm((int) (10 * Math.random()) - 5,
                    (int) (4 * Math.random()));
            p2.addTerm((int) (10 * Math.random()) - 5,
                    (int) (4 * Math.random()));
        }
        p0 = p1.addPolynomial(p2);
        System.out.println(p1 + "\n" + p2 + "\n" + p0 + "\n");
    }
}



enum Comp {
    LT, EQ, GT
}


static Comp cmp(int a, int b) {
    return (a < b) ? Comp.LT : (a == b) ? Comp.EQ : Comp.GT;
}

private Term poly;


public Polynomial() {
    poly = null;
}


public void addTerm(int coef, int exp) {
    if (coef == 0) return;
    Term term = new Term(coef, exp,null);
    if (poly == null) {
        poly = term;
    } else {
        poly = poly.add(term);
    }
}


@Override
public String toString() {
    if (poly == null) return "0";

    StringBuilder buf = new StringBuilder();
    poly.writeTo(buf);
    return buf.toString();
}


public Polynomial addPolynomial(Polynomial that) {
    Polynomial ret = new Polynomial();
    if (poly != null) {
        ret.poly = new Term(poly);
        if (that.poly != null) {
            ret.poly = ret.poly.add(new Term(that.poly));
        }
    } else if (that.poly != null) {
        ret.poly = new Term(that.poly);
    }
    return ret;
}


private class Term {
    final int coef;

    final int exp;

    final Term next;


    Term(int coef, int exp, Term next) {
        this.coef = coef;
        this.exp = exp;
        this.next = next;
    }


    Term(Term copy) {
        this.coef = copy.coef;
        this.exp = copy.exp;
        if (copy.next == null) {
            this.next = null;
        } else {
            this.next = new Term(copy.next);
        }
    }


    Term add(Term other) {
        if (other == null) return this;

        switch (cmp(this.exp, other.exp)) {
        case LT: {
            Term n = other.add(this);
            return n;
        }
        case GT: {
            if (next == null) {
                return new Term(coef,exp,other);
            }

            return new Term(coef,exp,next.add(other));
        }
        default: {
            Term n = (next==null) ? other.next : next.add(other.next);
            int nc = coef+other.coef;
            return (nc!=0) ? new Term(nc,exp,n) : n;
        }
        }
    }


    public void writeTo(StringBuilder app) {
        if (coef != 1 || exp == 0) app.append(coef);
        if (exp == 1) {
            app.append("x");
        } else if (exp != 0) {
            app.append("x^").append(exp);
        }
        if (next != null) {
            app.append('+');
            next.writeTo(app);
        }
    }
}
}