• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

nullpointerexception

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am trying to solve this problem:
Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.
I made a class Node which contains an int variable called value, and a Node reference. Using this class, I made another class Stack where I implemented the functions push(),pop(),peek() and isEmpty(). I made another class called sortStack, containing the main method.
In the main, I made two stack objects, stack1 and stack2. The main prompts user input to fill up stack1, and should then proceed to fill up stack2 which would be sorted in ascending order. The following is the code:

But when I run the program, I get the folowing output:


D:\code>javac sortStack.java

D:\code>java sortStack
Make the stack by entering integers(enter END to terminate):
45
67
34
54
31
78
99
END
Following is the stack:
45
67
34
54
31
78
99
Exception in thread "main" java.lang.NullPointerException
at Stack.pop(sortStack.java:33)
at sortStack.main(sortStack.java:94)

D:\code>
Can someone please help me out?
 
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
At

You don't check if stack2 is empty.

45 is in stack2, 67 is the temp. Pop stack2, push it into stack1. Peek at stack2 which is now empty.

I am not 100% sure I am right, as I am a bit tired, but I think that might be it.
 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Not sure about the Null Pointer Exception.

Though your logic is correct , why do you have 2 references ( head and last) in the Stack class? Is head alone not sufficient? Instead of pushing and popping the element from the end of the stack, if you push and pop from the head of the stack, only one reference will be enough. The code will look simple.

Another thing, in line 38, the verification should be while(ref1.next!=null). Your pop will work wrongly if the stack has 2 elements.


 
sonu jha
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i factored that in...and the code now looks like


The output now is:

D:\>cd code

D:\code>javac sortStack.java

D:\code>java sortStack
Make the stack by entering integers(enter END to terminate):
56
32
45
67
89
12
90
55
443
END
Unsorted stack:
56
32
45
67
89
12
90
55
443
Exception in thread "main" java.lang.NullPointerException
at Stack.pop(sortStack.java:33)
at sortStack.main(sortStack.java:100)

D:\code>
As you see, again a nullpointerexception..this time with the method pop()
 
sonu jha
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@kalpana yeah.....looks like i could have done without that "last" Node....the method pop() works if there are two elements, because the second element value will be accessed by ref.next.value where ref=head.
 
Kalpana Periasamy
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You are right. It will work for 2 elements also.

If you use just one pointer, then the code will become way simpler, like

int pop(){
int element;
if(head==null)
throw Exception;
else {
element = head.value;
head = head.next;
return element;
}
 
Kalpana Periasamy
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think that you have pasted the same program again.
(There is no need of 2 references. Just keep 'head'. Always insert the new value to head and pop the value from the head)
 
sonu jha
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No, in the second version, I have added this condition (stack2.isEmpty()==false) to check if stack2 is empty before performing peek() on it. Also, in line 98, I added if(i>0) so that only if stack1 has been pushed into, the for loop to push back into stack2 works. I also deleted the code block to print the original unsorted stack(using the reference sth1 before), as it doesn't work as all the elements of stack1 which is the original stack will have been popped off to be accomodated in a sorted manner into stack2, which is printed out using the reference sth2, even though, I do print the original stack once, before the sorting is done.
 
Mori Gad
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Where do you reset i after the push backs?
 
sonu jha
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi, I took care of resetting i to 0 in the code below. But, still teh same problem. I have added some print statements as well to know what is going on if that's any help. Here is the modified code:




The output:


D:\code>javac sortStack.java

D:\code>java sortStack
Make the stack by entering integers(enter END to terminate):
8
7
6
5
4
3
2
1
END
Unsorted stack:
8
7
6
5
4
3
2
1
Temp: 1
1 pushed into stack2.
Temp: 2
1 pushed into stack1
Stack1 was pushed into 1 times.
2 pushed into stack2.
3 pushed into stack2
Temp: 4
3 pushed into stack1
2 pushed into stack1
Stack1 was pushed into 2 times.
4 pushed into stack2.
5 pushed into stack2
6 pushed into stack2
Temp: 7
6 pushed into stack1
5 pushed into stack1
4 pushed into stack1
Stack1 was pushed into 3 times.
7 pushed into stack2.
8 pushed into stack2
Exception in thread "main" java.lang.NullPointerException
at Stack.pop(sortStack.java:33)
at sortStack.main(sortStack.java:110)

D:\code>
 
Mori Gad
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


7 pushed into stack2.
8 pushed into stack2
Exception in thread "main" java.lang.NullPointerException
at Stack.pop(sortStack.java:33)
at sortStack.main(sortStack.java:110)



The error happened at 110, and it happened after you popped 8, which is the last item in stack1.



You try to pop it before checking if it is empty.

As an aside, were you supposed to write the stack class as well? Otherwise, Stack is already implemented in Java. Reinventing the wheel won't help you.

http://docs.oracle.com/javase/6/docs/api/java/util/Stack.html
 
sonu jha
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
First thing, if i>0, it means that i number of elements have been popped off stack2 and pushed into stack1, which means stack1 cannot be empty until all those i elements are popped off it, which is equal to the number of times the for loop executes(since j initialised to 0, and loop executes as long as j<i). So inside that for loop, we'll never have stack1 getting empty. Still, I added the condition if(stack1.isEmpty()==false) before stack2.push(stack1.pop()) in line 102. Now the code looks like (sorry..I am posting it over and over... )


The output:

D:\code>javac sortStack.java

D:\code>java sortStack
Make the stack by entering integers(enter END to terminate):
23
41
12
34
789
65
0
785
2
56
END
Unsorted stack:
23
41
12
34
789
65
0
785
2
56
The sorted stack:
789
34
12
41
23

D:\code>

As you see, not all elements are printed, moreover the output is not sorted.

I sure expected there to be a ready to use stack class in java, but still, being a newbie, I thought, a little bit of practice won't hurt..
 
Mori Gad
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I would suggest you go over your stack code. All you should need is a reference to the head. Kalpana made some good points, and your pop is just plain strange.

The best way to go about this is to use the Stack api and scrap your stack.

If you really need to write the stack, some points:
Write some for Node
Example


You should never need to loop in a stack, all you need is head = head.next, given that head is not null.

On pop and peek, if head is null, you should throw a new EmptyStackException();
 
sonu jha
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi....
I did it. The mistake that I made before was that I was not updating the reference last in pop. The code works fine now..
Thank you very much for the help....and I have taken note of your advice...
It would have have worked right away if I had used the stack api...but I simply couldn't give up on my code...I wanted to find out why it wasn't working...
 
Kalpana Periasamy
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Your sort logic is perfectly fine. If you change your stack logic, the code will work perfectly fine

Here is a sample Stack Code:
class Stack{
Node head;
public Stack(){
this.head = null;
}

void push(int value){
Node temp = new Node(value);
temp.next = head;
if(head == null)
head = temp;
else{
temp.next = head;
head = temp;
}
}

int pop(){
if(head != null){
int temp = head.value;
head = head.next;
return temp;
} else {
throw new EmptyStackException();
}
}

boolean isEmpty() {
return head == null;
}

int peek(){
if(!isEmpty())
return head.value;
else
throw new EmptyStackException();
}

void print(){
Node ref = head;
System.out.println("Contents of stack are:");
while(ref != null){
System.out.println(ref.value);
ref = ref.next;
}
}
}

class Node{
public int value;
public Node next;

public Node(int value){
this.value = value;
this.next = null;
}
}

Replace this stack code in your program. There you go.. Your input will be sorted
 
Kalpana Periasamy
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Still I couldnt find out your mistake. Can you post the new pop code? (Just curious..)
 
sonu jha
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
yeah..sure.. the new pop is below:


See the lines 7 and 15...i am updating the reference last after a pop operation...that's what was missing before...except for that it is all the same....
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

sonu jha wrote:yeah..sure.. the new pop is below:
See the lines 7 and 15...i am updating the reference last after a pop operation...that's what was missing before...except for that it is all the same....


Seems like an odd way to do things to me. The normal way to implement a Stack is that push() adds a new element to the 'top', and pop() removes the top element. You seem to be adding new elements at the end (or 'bottom'), and while there's nothing particularly wrong with that, it's certainly not what most people are going to expect.

If you really want to maintain a 'last' reference, you could do it like this:however, it does mean that you can't make Node's 'next' field final.

You'll notice that I made 'Node' a private nested class: There's no reason why anyone should need to know about the inner workings of your Stack.
I also added a 'next' parameter to the Node constructor; that allows it to be created "in place", which usually makes things a lot easier.

The generics is just there for instruction; you may not need it in your case.

HIH

Winston
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

sonu jha wrote:The main prompts user input to fill up stack1, and should then proceed to fill up stack2 which would be sorted in ascending order. The following is the code:...


Another point: Linked Lists (which is what your Stack is internally) make very poor structures for sorting. Using my suggestion above, you could probably make things much faster (and simpler) - at the expense of a bit of memory - by using a dump-sort-reload. Maybe something like this:I would definitely advise adding a size() method to your Stack class, and also either a toString() method that lists its contents, or an iterator() method that returns a java.util.Iterator to its values (which, as a by-product, would also make it an Iterable).

Winston
 
If you settle for what they are giving you, you deserve what you get. Fight for this tiny ad!
Smokeless wood heat with a rocket mass heater
https://woodheat.net
reply
    Bookmark Topic Watch Topic
  • New Topic