Java polynomial add-on

Question

I use String Tokenizer and Linked Lists, and linked lists are required for this job. There is an external file in which there are many lines of polynomials (one per line). Using string tokenizers and a linked list, I run a while loop that captures two lines in each pass and adds them to the linked lists. After the numbers have been loaded into linked lists, the goal is to add these polynomials together from the linked list and create a new linked list containing this polynomial.

For example, the first two lines in a file:

2x ^ 4 -5x ^ 3 + 9x ^ 2 -10

3x ^ 4 -6x ^ 3 + 10x ^ 2 -11

---

= 5x ^ 4 -11x ^ 3 + 19x ^ 2 -21

Here is my code:

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); } } 

Here is my node class:

 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; } } 

The problem arises after this, when some lines are not complete, and the line to which they should be added is complete, like -12x ^ 8 + 5x ^ 2 -3 and 8x ^ 3 + 2x

The answer to this should be -12x ^ 8 + 8x ^ 3 + 5x ^ 2 + 2x -3

What can I do to solve this problem?

Answer 1

Well, after a long chat, this is what we “came up with”. I understand that this only erodes the answer.

However, with a solid implementation in a clean style, Java 1.4 code could do a lot to help you understand.

Particular attention was paid to printing the result in tabular form, aligning the terms of different operands in the columns of their corresponding indicator.

the code

There are two files:

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(); } } 

Sample data:

Input:

 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 

Output:

<sub>

  +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 

sub>

Answer 2

I would completely abandon the linked list approach. Or, if you need to use it, use it as an input for the next approach.

First select an array with some upper bound on the size, then use the indexes of the array as an exponent of x , and in the corresponding index / exponent you will save the coefficient of this term. So when you parse 2x^3 , you say polysum[3] += 2 (assuming the array was initialized with 0 ). If you do this for both polynomials with the same polysomic array, you will get an array containing the coefficients of the sum of the two polynomials.

Then you need to create the corresponding output, which is mathematically equivalent: polysum[0] + polysum[1] * x + polysum[2] * x^2 , etc.

If you may have to handle completely arbitrary metrics, and pre-allocating an array is not possible, use HashMap, where the key is the metric and the value is a coefficient.

Edit: if you really have to solve it using a linked list, sort the two lists and repeat the parallel parallel lists. In a Python-like pseudo-code:

 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 

If you know that the input is always sorted, you can skip sorting. Otherwise, the sorting will be nontrivial.

Answer 3

I would recommend an array or arraylist, using the array index as polynomial exponential, and the array value as polynomial coefficients.

For example, 3+ 4 * x + 5 * x ^ 4 would be 3 4 0 0 5 for an arraylist.

It would be better if you created the Polynomial class and defined its actions. Instead of using Node as a class.

Answer 4

3x ^ 3 - x ^ 1 is the same as 3x ^ 3 + 0x ^ 2 - x ^ 1 + 0. Try to fill each value in the way you read it.

Answer 5

This suggests that the polynomials are written in exponentially descending form: (Let me know if this is not the case!)

When you read items in a line, make sure that the metric of the current item is exactly one less than the previous item. If they are, then there is no problem. If this is not the case, use this approach:

Let a be the exponent of the current element and b previous element.

Then use this sample code to fix this:

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

Answer 6

I agree with the approach using an array, but we cannot optimize anymore in terms of complexity of space if we use hashmap.

Thus, each polynomial equation will be a hashmap, where the key will be the exponent x, and the value will be the coefficient x.

Now you can simply scroll through the keys of one hash file and add it to another hash map.