Menu
I am using String Tokenizer and Linked Lists, and the Linked Lists are required for this assignment. There is an external file in there are numerous lines of polynomials (one per line). Using String Tokenizers and Linked List, I am running a while loop which captures two lines on each pass and adds them to linked lists. After the numbers have been loaded into linked lists, the goal is to add those polynomials together from their linked list and create a new linked list that contains that polynomial.
For example, first two lines in the file are this:
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 comes after this where some lines are not complete while the line they have to be added to is complete like -12x^8 +5x^2 -3 and 8x^3 +2x
The answer to this is supposed to be -12x^8 +8x^3 +5x^2 +2x -3
What can I do to solve this?
286
Ok, after lenghty labour in the chat, this is what 'we' came up with. I realize this is just blurting the answer, to an extent.
Even so, having a solid implementation in clean style Java 1.4 code could do a lot to help your understanding.
Special attention has been given to printing the result in tabulated form, aligning terms of different operand in the columns of their respective exponent.
There are two files:
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) });
}
}
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();
}
}
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:
+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
I'd completely drop the linked-list approach. Or if you have to use it, use it as an input to the following approach.
Pre-allocate an array with some upper bound on size, then use the indices of the array as the exponent of x and at the corresponding index/exponent you store the coefficient of the 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 polysum array, you will get an array containing the coefficients of the sum of the two polynomials.
Then you have to create the corresponding output which is the equivalent of, mathematically speaking: polysum[0] + polysum[1] * x + polysum[2] * x^2 etc.
In case you may have to handle totally arbitrary exponents and pre-allocation of an array is infeasible, use a HashMap where the key is the exponent, and value is the coefficient.
Edit: If you really have to solve it by using your linked list, sort the two lists, and then iterate through the lists in parallel. In 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 the input is always sorted, you can skip the sorting. Otherwise, the sorting will be non-trivial.
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
