logo标签列表

Java多项式相加

javalinked-list
4
我正在使用String Tokenizer和Linked List，而且这个任务需要用到Linked List。有一个外部文件，里面有许多多项式（每行一个）。使用String Tokenizer和Linked List，我运行一个while循环，在每次循环中捕获两行并将它们添加到Linked List。在数字已经加载到Linked List之后，目标是从它们的Linked List中将这些多项式相加，并创建一个包含该多项式的新Linked List。
例如，文件中的前两行是这样的:
2x^4 -5x^3 +9x^2 -10
3x^4 -6x^3 +10x^2 -11
=
5x^4 -11x^3 +19x^2 -21
这是我的代码:
public class PolynomialAddition
{
    static File dataInpt;
    static Scanner inFile;

    public static void main(String[] args) throws IOException
    {
      dataInpt=new File("C:\\llpoly.txt");
      inFile=new Scanner(dataInpt);
      StringTokenizer myTokens;
      String line,polyTerm;
      Node firstL=new Node();
      Node secondL=new Node();
      line=inFile.nextLine();
      myTokens=new StringTokenizer(line);
      polyTerm=myTokens.nextToken();
      firstL.value=polyTerm.substring(0,polyTerm.indexOf("x"));
      firstL.value2=polyTerm.substring(polyTerm.indexOf("^")+1);

    }
}

这是我的节点类：

public class Node
{
  public Object value;
  public Object value2;
  public Node next;

  public Node()
  {
    value=null;
    value2=null;
    next=null;
  }
  public Node (Object value, Object value2, Node next)
  {
    this.value=value;
    this.value2=value2;
    this.next=next;
  }
}

问题出在这里，有些行不完整，而它们需要添加到的那一行是完整的，比如-12x^8 +5x^2 -3和8x^3 +2x。

答案应该是-12x^8 +8x^3 +5x^2 +2x -3。

我该怎么解决这个问题呢？

6个回答
4

好的，在聊天中经过长时间的努力，这就是我们想出来的。我意识到这只是在某种程度上回答问题。

即便如此，以清晰的Java 1.4代码实现可以很大程度上帮助您理解。

特别注意将结果以表格形式打印出来，将不同操作数的术语对齐在它们各自指数的列中。

代码

有两个文件：

Node.java

class Node {
    int factor;
    int exponent;
    Node next;

    public Node() {
        factor = 0;
        exponent = 0;
        next = null;
    }

    public Node(int factor, int exponent, Node next) {
        this.factor = factor;
        this.exponent = exponent;
        this.next = next;
    }

    public String toString() {
        return String.format("%+4dx^%d    ", new Integer[] { new Integer(factor), new Integer(exponent) }); 
    }
 }

PolynomialAddition.java

import java.io.*;
import java.util.*;

public class PolynomialAddition {
    static File dataInpt;
    static Scanner inFile;

    public static void main(String[] args) throws IOException {
        dataInpt = new File("/tmp/input.txt");
        inFile = new Scanner(dataInpt);

        while (inFile.hasNextLine()) {
            Node first = readPolynomial();
//          printList(first);

            Node second = readPolynomial();
//          printList(second);

            Node addition = addPolynomials(first, second);
//          printList(addition);

            printTabulated(first, second, addition);

            System.out.println("\n");
        }
    }

    private static Node addPolynomials(Node first, Node second) {
        Node head = null, current = null;
        while (null!=first || null!=second)
        {
            boolean pickfirst = false;
            boolean haveBoth = (null!=first && null!=second);

            Node node;
            if (haveBoth && first.exponent == second.exponent)
            {
                node = new Node(first.factor + second.factor, first.exponent, null);
                first = first.next;
                second = second.next;
            } else
            {
                pickfirst = first!=null && 
                    ((second == null) || first.exponent > second.exponent);

                if (pickfirst)
                {
                    node = new Node(first.factor, first.exponent, null);
                    first = first.next;
                } else
                {
                    node = new Node(second.factor, second.exponent, null);
                    second = second.next;
                }
            }

            if (current == null)
            {
                head = node;
                current = head;
            } else
            {
                current.next = node;
                current = node;
            }
        }

        return head;
    }

    private static void printTabulated(Node first, Node second, Node addition) {
        String line1="", line2="", barline="", line3="";
        while (addition != null)
        {
            String 
                 part1 = "           ", 
                 part2 = "           ", 
                 part3 = "           ";

            if (null!=first && first.exponent == addition.exponent) 
            {
                part1 = first.toString();
                first = first.next;
            } 
            if (null!=second && second.exponent == addition.exponent) 
            {
                part2 = second.toString();
                second = second.next;
            }
            part3 = addition.toString();
            addition = addition.next;

            line1 += part1;
            line2 += part2;
            barline += "-----------";
            line3 += part3;
        }

        System.out.println(line1);
        System.out.println(line2);
        System.out.println(barline);
        System.out.println(line3);
    }

    private static Node readPolynomial() {
        String line = inFile.nextLine();
        StringTokenizer myTokens = new StringTokenizer(line);

        Node head = null, previous = null;
        while (myTokens.hasMoreTokens()) {
            Node current = new Node();
            String term = myTokens.nextToken();

            if (term.startsWith("+"))
                term = term.substring(1);

            current.factor = Integer.parseInt(
                    term.substring(0, term.indexOf("x")));
            current.exponent = Integer.parseInt(
                    term.substring(term.indexOf("^") + 1));

            if (previous == null)
            {
                head = current;
                previous = head;
            } else
            {
                previous.next = current;
                previous = current;
            }
        }
        return head;
    }

    private static void printList(Node head) {
        for (Node ptr = head; ptr != null; ptr = ptr.next)
            System.out.print(ptr);
        System.out.println();
    }
}

示例数据：

输入：

2x^4 -5x^3 +9x^2 -10x^0 
 3x^4 -6x^3 +10x^2 -11x^0 
 -2x^1 +4x^0 
 2x^1 -4x^0 
 8x^5 +6x^4 +5x^2 -3x^0 
 -12x^8 +2x^7 +14x^5 
 1x^5 +7x^2 +8x^1 
 -5x^4 -7x^3 -4x^2 -3x^0 
 10x^5 -3x^3 +4x^2 -234x^1 -12x^0 
 -5x^5 -2x^3 +10x^0

输出：

  +2x^4      -5x^3      +9x^2     -10x^0    
  +3x^4      -6x^3     +10x^2     -11x^0    
--------------------------------------------
  +5x^4     -11x^3     +19x^2     -21x^0    


  -2x^1      +4x^0    
  +2x^1      -4x^0    
----------------------
  +0x^1      +0x^0    


                        +8x^5      +6x^4      +5x^2      -3x^0    
 -12x^8      +2x^7     +14x^5                                     
------------------------------------------------------------------
 -12x^8      +2x^7     +22x^5      +6x^4      +5x^2      -3x^0    


  +1x^5                            +7x^2      +8x^1               
             -5x^4      -7x^3      -4x^2                 -3x^0    
------------------------------------------------------------------
  +1x^5      -5x^4      -7x^3      +3x^2      +8x^1      -3x^0    


 +10x^5      -3x^3      +4x^2    -234x^1     -12x^0    
  -5x^5      -2x^3                           +10x^0    
-------------------------------------------------------
  +5x^5      -5x^3      +4x^2    -234x^1      -2x^0

尽管你非常努力，但我不能在道德上为一份作业问题的完整工作答案点赞。 :( 也许如果它用另一种语言编写... - Mooing Duck
@MooingDuck 已经得到了一些补偿（解释在聊天室中），这也揭示了一个由于不必要的聪明而导致的错误。（显然，现在已经修复）感谢您的帮助。 - sehe
3
我建议完全放弃链表方法。或者如果你必须使用它，将其作为以下方法的输入。
预先分配一个带有一些上限大小的数组，然后使用数组的索引作为x的指数，并在相应的索引/指数处存储项的系数。所以当你解析2x ^ 3时，你会说polysum [3] + = 2（假设该数组已初始化为0）。如果你对两个多项式都使用同一个polysum数组进行这样的操作，则会得到一个包含两个多项式之和系数的数组。
然后，您需要创建相应的输出，即数学上等价于：polysum [0] + polysum [1] * x + polysum [2] * x ^ 2等等。
如果您可能需要处理完全任意的指数，并且预分配数组是不可行的，请使用哈希映射，其中键是指数，值是系数。
编辑：如果您确实必须使用链接列表来解决此问题，请对两个列表进行排序，然后并行迭代列表。在类似Python的伪代码中：
poly1_node = poly1_first_node
poly2_node = poly2_first_node
result_node = result_first_node
while poly1_node != Null and poly2_node != Null:
    if poly1_node.value2 == poly2_node.value2:
        result_node.value2 = poly1_node.value2
        result_node.value = poly1_node.value + poly2_node.value
        poly2_node = poly2_node.next
        poly2_node = poly2_node.next
    if poly1_node.value2 < poly2_node.value2:
        result_node.value2 = poly1_node.value2
        result_node.value = poly1_node.value
        poly1_node = poly1_node.next
    if poly2_node.value2 < poly1_node.value2:
        result_node.value2 = poly2_node.value2
        result_node.value = poly2_node.value
        poly2_node = poly2_node.next
    result_node.next = new Node()
    result_node = result_node.next
while poly1_node != Null:
    result_node.value2 = poly1_node.value2
    result_node.value = poly1_node.value
    poly1_node = poly1_node.next
    result_node.next = new Node()
    result_node = result_node.next
while poly2_node != Null:
    result_node.value2 = poly2_node.value2
    result_node.value = poly2_node.value
    poly2_node = poly2_node.next
    result_node.next = new Node()
    result_node = result_node.next

如果您知道输入始终是排序的，那么可以跳过排序。否则，排序将会很复杂。

虽然我很感谢你的回答，但它并没有回答我的问题。 - DemCodeLines
@user1079641：为什么它没有回答问题？在我看来，它看起来很好。 - Mooing Duck
我必须使用链表，但我是个学生...这段代码有点高级，超出了我的理解范围...除非你愿意来和我一起进入聊天室并向我解释代码，否则我无法接受这个。 - DemCodeLines
2

我建议使用数组或ArrayList，将数组索引作为多项式指数，数组值作为多项式系数。

例如，3+4*x+5*x^4可以表示为数组列表中的3 4 0 0 5。

如果创建一个名为Polynomial的类并定义其操作，而不是使用Node作为类，则效果会更好。

1

3x^3 - x^1与3x^3 + 0x^2 - x^1 + 0是一样的。在读入值时尝试按此方式进行填充。

如果它们不匹配，我无法将它们添加进去...两者都需要被打印出来。 - DemCodeLines
1

这里假设多项式是按指数降序排列的： （如果不是，请告诉我！）

在读取行中的元素时，请检查当前元素的指数是否比前一个元素少1。如果是，则没有问题。如果不是，则采用以下方法：

令a为当前元素的指数，b为前一个元素的指数。

然后使用以下代码示例来解决此问题：

for(int i = b - 1; i > a; i--)
{
    //Insert an element of the form: 0*x^i.
}
这是我脑海中的想法，我使用一个链表来捕捉行中每个数字（系数和指数），使用String Tokenizer，但我不确定如何创建两个不同的链表，以适用于两个不同的行，最终将它们相加。 - DemCodeLines
为什么要创建两个列表？按照我描述的方式，只需创建一个即可！ - Zéychin
0

我同意使用数组的方法，但如果我们使用哈希表，能否在空间复杂度方面进行更多优化呢？

因此，每个多项式方程将成为一个哈希表，其中键将是x的指数，值将是x的系数。

现在，您可以简单地遍历一个哈希表的键并将其添加到另一个哈希表中。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接