Полиномиальное сложение Java

Question

Я использую String Tokenizer и связанные списки, и для этого назначения требуются связанные списки.Есть внешний файл, в котором есть много строк полиномов (по одной на строку).Используя String Tokenizer и Linked List, я запускаю цикл while, который захватывает две строки на каждом проходе и добавляет их в связанные списки.После того, как числа были загружены в связанные списки, цель состоит в том, чтобы добавить эти многочлены вместе из их связанного списка и создать новый связанный список, который содержит этот многочлен.

Например, первые две строки в файле это:

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

Что я могу сделать, чтобы решить эту проблему?

Answer 1

Хорошо, после долгой работы в чате, это то, что «мы» придумали.Я понимаю, что это просто размывает ответ, до некоторой степени.

Несмотря на это, надежная реализация в чистом стиле кода 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    

Answer 2

Я бы полностью отбросил подход со связанными списками.Или, если вам нужно использовать его, используйте его в качестве входных данных для следующего подхода.

Предварительно выделите массив с некоторой верхней границей размера, затем используйте индексы массива в качестве показателя степени xи в соответствующем индексе / показателе степени вы храните коэффициент термина.Поэтому, когда вы анализируете 2x^3, вы говорите polysum[3] += 2 (при условии, что массив был инициализирован с 0).Если вы сделаете это для обоих полиномов с одним и тем же массивом полисумов, вы получите массив, содержащий коэффициенты суммы двух полиномов.

Затем вы должны создать соответствующий выход, эквивалентный математическиговоря: polysum[0] + polysum[1] * x + polysum[2] * x^2 и т. д.

Если вам, возможно, придется обрабатывать совершенно произвольные показатели, а предварительное выделение массива невозможно, используйте HashMap, где ключ - это показатель степени, а значение - коэффициент.

Редактировать: Если вы действительно должны решить эту проблему, используя связанный список, отсортируйте два списка, а затем выполните итерации по спискам параллельно.В 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

Если вы знаете, что ввод всегда сортируется, вы можете пропустить сортировку.В противном случае сортировка будет нетривиальной.

Answer 3

Я бы порекомендовал массив или массив, используя индекс массива в качестве полиномиальной экспоненты, а значение массива в качестве коэффициентов полиномов.

Например, 3+ 4 * х + 5 * х ^ 4 было бы 3 4 0 0 5 для arraylist.

Было бы лучше, если бы вы создали класс с именем Polynomial и определили его действия. Вместо использования Node в качестве класса.

Answer 4

Это делает предположение, что полиномы записаны в убывающей экспоненте форме: (Дайте мне знать, если это не так!)

Когда вы читаете элементы в строке, убедитесь, что показатель степенитекущего элемента ровно на один меньше, чем предыдущий элемент.Если они есть, то проблем нет.Если это не так, используйте этот подход:

Пусть a будет показателем текущего элемента, а b будет показателем предыдущего элемента.

Затем используйте этот пример кода, чтобы исправить это:

for(int i = b - 1; i > a; i--)
{
    //Insert an element of the form: 0*x^i.
}

Answer 5

3x ^ 3 - x ^ 1 - это то же самое, что и 3x ^ 3 + 0x ^ 2 - x ^ 1 + 0. Попробуйте заполнить каждое значение таким образом, как вы его читаете.

Answer 6

Я согласен с подходом, использующим массив, но мы не можем оптимизировать с точки зрения сложности пространства, если мы используем hashmap.

Так что каждое полиномиальное уравнение будет хеш-картой, где ключ будет показателем степени x и значениябудет являться коэффициентом x.

Теперь вы можете просто перебирать ключи одной хеш-карты и добавлять ее в другую хеш-карту.