Thread: Weird problem with my linkedlist

Hi guys.

I'm having this weird problem with my linked list. basically i'm making a linked list implementation of a polynomial; my nodes contain 2 elements (coefficient,powers). It works somewhat fine, when i directly add in a coefficient and exponent pair (example poly.add(5,3)) however it doesnt work through the users input and gives me a null pointer exception.

the user needs to input their text like so: 12x^5+3x^2 and then the regular expression will break it apart in the coefficient/exponent pairs. when i use this method, the linked list gives me the null pointer exception.

I'm pretty sure its a trivial error, but i'm just so fried from going over this for hours that i cant figure it out. I will be eternally grateful if someone can just test this program and let me know what the issue is here.

I think the error originates somewhere in my prep method, because when i bypass that method and just use add it works pretty alright

Code:

 
package project2;
 
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
class Polynomial
{
	Node head;	
 
	Polynomial()
	{
		head = null;
	}
 
	public void add(int coef, int power)
	{
 
		Node temp = new Node(coef, power, null);		
 
		if (head == null)
			head = temp;
		else {
			Node p = null;
			Node q = head;
			//insert in front if exponent is higher
			if (temp.getElement2() > q.getElement2())
			{
 
			temp.setNext(head);
			head = temp;
 
 
			} 
			else 
			{//insert at middle or end
				while ( q != null && q.getElement2() > temp.getElement2())
				{
					p = q;
					q = q.getNext();
				}
				p.setNext(temp);
				temp.setNext(q);
			}
		}
 
	}
 
//This is the regex method, it will take the users input and break it apart; i think the error may originate from somewhere here.	
	public Polynomial prep(String s)
	{
 
 
 
		Polynomial poly = new Polynomial();
 
		String str1 = "(-?[0-9]{1,})x\\^(-?[0-9]{1,})?";
		String str2 = "(-?[0-9]{1,})x";
		String str3 = "(-?[0-9]{1,})";
		Pattern p = Pattern.compile(str1);
		Pattern p2 = Pattern.compile(str2);
		Pattern p3 = Pattern.compile(str3);
 
		Matcher matcher = p.matcher(s);
		Matcher matcher2 = p2.matcher(s);
		Matcher matcher3 = p3.matcher(s);
 
		int index = 0;
		boolean matchFound;				 
		do{
			if(matchFound = matcher.find(index))
			{
				for (int i=1; i<=matcher.groupCount(); i++) {
			        String groupStr = matcher.group(i);
			        System.out.println(groupStr);
			        poly.add(Integer.parseInt(matcher.group(1)),Integer.parseInt(matcher.group(2)));
 
 
			    }
 
				index = matcher.end();
			}
			else if (matchFound = matcher2.find(index))
			{
				String groupStr = matcher2.group(1);
				System.out.println(groupStr);
				System.out.println(1);
				poly.add(Integer.parseInt(matcher2.group(1)),1);
 
 
				index = matcher2.end();
			}
			else if (matchFound = matcher3.find(index))
			{
				String groupStr = matcher3.group(1);
				System.out.println(groupStr);
				System.out.println(0);
				poly.add(Integer.parseInt(matcher3.group(1)),0);
 
 
				index = matcher3.end();
			}
			else
				matchFound = false;
 
		}while(matchFound);			
 
		System.out.println("Done");		
 
		return poly;
 
	}			
 
	public String toString()
	{
		Node current = head.getNext();
		String output = "";
		while(current != null)
		{
			output += "(" +current.Element1 + "," + current.Element2 + ")";
			current = current.getNext();
		}
		return output;
	}
 
 
	class Node
	{
		int Element1, Element2;
		Node next;
 
		public Node(int Element1,int Element2)
		{			
			this.Element1 = Element1;			
			this.Element2 = Element2;
			next = null;
		}
 
		public Node(int Element1, int Element2, Node n) 
		{
			this.Element1 = Element1;
			this.Element2 = Element2;
			next = n;
		}
 
		public Node getNext()
		{
			return next;
		}
 
		public void setNext(Node next)
		{
			this.next = next;
		}
 
		public int getElement1() {
			return Element1;
		}
 
		public void setElement1(int element1) {
			Element1 = element1;
		}
 
		public int getElement2() {
			return Element2;
		}
 
		public void setElement2(int element2) {
			Element2 = element2;
		}
 
 
	}
}
 
public class Project {
	public static void main(String[] args) {
 
		Polynomial p1 = new Polynomial();	
		Polynomial p2 = new Polynomial();	
		/*p1.add(2, 8);
		p1.add(0, 3);
		p1.add(4, 5);
		p1.add(6, 7);*/
 
	p1 = p1.prep("-12x^5+6x^3-3x+5");
 
 
 
 
 
		System.out.println(p1);
 
	}
 
}

gives me the null pointer exception.

Please post the full text of the error message.

Look at the line where the error occurs and find the variable with the null value. Then backtrack in the code to see why that variable does not have a non-null value.

With out getting to deep in your code, rather then remove "buggy" code.
It is better to replace it with dummy code.

	public Polynomial prep(String s)
	{
		// return //not to sure, but you should know exactly what a polynomial object is
	}

Quickly rewrite polynomial method hard coding its variables, and compile/run.
If it gives you the expected data, then we know we have found our monster.
Come back to the site, and I will help you look for the null pointer.
(note, it may help speed things up if you explain what your Polynomial Object is)

See you soon,
Jonathan

Why is the variable at line 46 null?

Have you found out why the variable is null yet?

If you have an interactive debugger try using that.
Otherwise add lots of printlns to show the value of all the variables as the code executes to see what it is doing.
If you understand what the program is supposed to do, the print outs of what it is doing should help you figure out what is wrong.

i really do think it has something to do with my linked lists. I have several printlns in my program and it shows that my regex is able to extract coef/exp out of the input but for some reason its not adding it to the polynomial linked list correctly.

for instance when i insert the polynomial: "-12x^5+6x^3-3x+5"

it extracts the coef and the powers then displays:

-12
5
6
3
-3
1
5
0
Done

but the linked list comes out empty, because its supposed to print it out like (-12,5)(6,3)(-3,1)(5,0). im gonna fiddle around with it more, but if anyone can figure out why i'll be very thankful. I cant proceed with my project until this has been resolved...

just because an error occurs when trying to add, doesn't mean add is the problem.
rather then "look" through code you have to "trace" through it.


Elaboration:
these are the exception paths.
at Project.main(Project.java:11) => "p1 = p1.prep("-12x^5+6x^3-3x+5");"

at Polynomial.prep(Polynomial.java:80) => "poly.add(Integer.parseInt(matcher.group(1)),I nteg er.parseInt(matcher.group(2)));"

at Polynomial.add(Polynomial.java:46) => "p.setNext(temp);"

This is showing you HOW your program got to this spot.

p.setNext(temp); this statement is the problem.

Either p is null or temp is null

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

looking at this, if next is null it wouldnt hurt anything

p.next = next; so if next was null, it would just set p to null.

p must be null, trace p back to when it was made, and trace back everything about p to find out why it is null.
Hint: you will probably use 30+ print statements. take your time wording them!

Here's a technique that will be helpful. Add a toString() method to the Node class so when you print a reference to it, it will show all the data in the Node object.

Another hint: add ID Strings to your println statements so you can easily see what println printed any output.
Your print out of a list of numbers will be very hard to track back to the println that printed it.
For example:
System.out.println("p1=" + p1);

I played with your new poly method, and it never seems to print the first/ highest poly, but they seem to order correctly
I would look in your print (toString?) for this slight oversight.

The null problem still needs to be found, though I noticed your
add method does not handle adding the same poly twice. food for thought.

add this to your toString statement,
The reason you were not getting the first (highest) node is because you skipped doing anything with head.

if(head != null)
{
	output += "(" +head.Element1 + "," + head.Element2 + ")";
}

lets try and get back to finding that null pointer!

okay guys, so i did what you suggested (adding a bunch of println's) and VOILA! the null error was found. THANK YOU SO MUCH!

the problem was the for loop in my prep class. it would send each part one-by-one, so 12x^5 would become: (12, null) (null,5). so when it would pass the (12,null) it would try to compare the exponents, but the exponent was null.

so that is solved by removing the for loop in the first IF statement, then the prep method becomes:

Polynomial poly = new Polynomial();
		/*poly.add(0,0);
		poly.add(2, 4);
		poly.add(4,6);*/
 
		String str1 = "(-?[0-9]{1,})x\\^(-?[0-9]{1,})?";
		String str2 = "(-?[0-9]{1,})x";
		String str3 = "(-?[0-9]{1,})";
		Pattern p = Pattern.compile(str1);
		Pattern p2 = Pattern.compile(str2);
		Pattern p3 = Pattern.compile(str3);
 
		Matcher matcher = p.matcher(s);
		Matcher matcher2 = p2.matcher(s);
		Matcher matcher3 = p3.matcher(s);
		int coef;
		int exp;
 
		int index = 0;
		boolean matchFound;				 
		do{
			if(matchFound = matcher.find(index))
			{
 
			    coef = Integer.parseInt(matcher.group(1));
			    exp = Integer.parseInt(matcher.group(2));			    
 
			    poly.add(coef,exp);
 
				index = matcher.end();
			}
			else if (matchFound = matcher2.find(index))
			{
				String groupStr = matcher2.group(1);
				System.out.println(groupStr);
				System.out.println(1);
				poly.add(Integer.parseInt(matcher2.group(1)),1);
 
				index = matcher2.end();
			}
			else if (matchFound = matcher3.find(index))
			{
				String groupStr = matcher3.group(1);
				System.out.println(groupStr);
				System.out.println(0);
				poly.add(Integer.parseInt(matcher3.group(1)),0);
 
				index = matcher3.end();
			}
			else
				matchFound = false;
 
		}while(matchFound);			
 
		System.out.println("Done");	
 
		return poly;
 
	}

but we solved one problem, and now there is another. it doesnt appear to be printing the first pair...

any ideas?

see two posts above

OMG THANKS JONLANE!

it is all working perfectly now! it is printing and ordering the terms in canonical form! I cant tell you how much i appreciate your help. Same with you Norm.

Now, the hard part begins. Adding/Subtracting/Multiplying/Dividing polynomials....

:0

Well, you know why null pointer errors exist?

BECAUSE THEY FEEL SO DAMN GOOD ONCE FOUND!

Glad we could help.

lol thats true.

at the risk of sounding annoying, i do have one other question.

i've implemented the ability to add polynomials, and thats working perfectly. Now i need to subtract polynomials. Unfortunately i cant just copy paste the addition method and change the "+" signs to "-" as that results in some sign errors for certain polynomials.

Instead, i figured the easiest way would be to take the 2nd polynomial and then negate all the signs. finally i would then take poly1 and poly2 and ADD them instead of subtracting them. is there a way to take one linked list, flip the signs, and then copy the contents into another linked list?

Actually disregard that, i'm an idiot.

been programming for a straight 6 hours now; my head is throbbing...