Homework SourseHow to use a stack to solve a fibbonaci sequence in java I h
How to use a stack to solve a fibbonaci sequence in java?
I have to write java code to use a stack solution for a fibbonacci sequnece.
I have already written the Linked list class to be implemented to use in my Stack class
my current problem is when i try to use my stack solution for the fib sequence i get a null pointer exceptions.
I think the problem is with my pop method in my stack class.
Code for the assignment:
import edu.hawaii.honolulu.ics211.LinkedList;
import edu.hawaii.honolulu.ics211.ListException;
public class Lab6<T> {
public static void main(String[] args) {
long n = 0;
int method = 0;
try {
n = Long.parseLong(args[0]);
method = Integer.parseInt(args[1]);
}
catch (ArrayIndexOutOfBoundsException e) {
System.out.println(\"Usage java Lab6 n m\");
System.out.println(\"where n is the number to find fib() for\");
System.out.println(\"and m is 1 (recursive) or 2 (stack)\");
System.exit(1);
}
if (method == 1) {
System.out.println(\"Using recursive solution\");
System.out.println(\"fib(\" + n + \") = \" + fib1(n));
}
else if (method == 2) {
System.out.println(\"Using stack-based solution\");
System.out.println(\"fib2(\" + n + \") = \" + fib2(n));
}
else {
System.out.println(\"Second argument must be 1 or 2\");
}
}
private static long fib1(long n) {
if (n < 2) {
return 1;
}
else {
return fib1(n-2) + fib1(n-1);
}
}
private static long fib2(long n) {
if (n <= 2){
return 1;
}
else {
Stack<Long> myStack = new Stack<Long>();
myStack.push(new Long(1));
myStack.push(new Long(1));
boolean done = false;
long counter=3;
while (done==false) {
long last = myStack.pop();
long nextlast = myStack.peek();
long fib2 = last + nextlast;
myStack.push(last);
myStack.push(fib2);
if (counter == n){
done = true;
}
counter++;
}
}
return fib1(n-2) + fib1(n-1);
}
}
Code for Stack class:
import edu.hawaii.honolulu.ics211.LinkedList;
import edu.hawaii.honolulu.ics211.ListException;
public class Stack<T> {
private LinkedList<T> mylist;
public Stack() {
mylist = new LinkedList<T>();
}
public boolean isEmpty() {
return mylist.isEmpty();
}
//remove item off the top of the stack
public T pop() {
try {
if (this.size() > 0) {
return mylist.remove(1);
}
}
catch (ListException e){
}
return null;
}
//add item on top of stack
public void push(T item) {
try {
mylist.insert(item,1);
}
catch(ListException e) {
}
}
//Return item from top of stack without removing it
public T peek() {
try {
if (this.size() > 0) {
return mylist.retrieve(1);
}
}
catch(ListException e) {
}
return null;
}
public int size() {
return mylist.length();
}
}
/*
* Nicolas Lum
* Lab 5
*/
public class LinkedList<T> implements MyListIFace<T> {
private Node head;
private Node tail;
private int numLinks;
/* private inner class */
private class Node {
T data;
Node next;
Node(T data) {
this.data = data;
next = null;
}
}
public LinkedList() {
super();
head = null;
tail = null;
numLinks = 0;
}
public int add(T item) {
Node newNode = new Node(item);
if (numLinks == 0) {
head = newNode;
tail = newNode;
}
else if (numLinks > 0) {
tail.next = newNode;
tail = newNode;
}
numLinks++;
return numLinks;
}
public String toString() {
String temp = \"[-\";
Node node = head;
if (numLinks > 0) {
temp += head.data.toString() + \"-\";
}
for (int i = 0; i < numLinks; i++) {
if (node.next != null) {
node = node.next;
temp += node.data.toString() + \"-\";
}
}
temp +=\"|\";
return temp;
}
public void insert(T item, int pos) throws ListException {
if (pos < 1 || pos > this.numLinks + 1) {
throw new ListException (\"Position invalid\");
}
if (numLinks == 0) {
add(item);
}
else if (pos == numLinks + 1) {
add(item);
}
else if (pos == 1) {
Node nd = new Node(item);
nd.next = head;
head = nd;
numLinks = numLinks+1;
}
else {
Node nd = new Node(item);
Node prev = Jump(pos-2);
nd.next = prev.next;
prev.next = nd;
numLinks = numLinks+1;
}
}
private Node Jump(int numJumps) {
Node node = head;
for (int i = 0; i < numJumps; i++) {
node = node.next;
}
return node;
}
Code for Linked list class:
public T remove(int pos) throws ListException {
T removedItem = null;
if (pos < 1 || pos > numLinks +1) {
throw new ListException (\"Position Invalid\");
}
else if (numLinks == 1) {
removedItem = head.data;
head = null;
tail = null;
numLinks--;
}
else if (pos == 1) {
if (numLinks > 1) {
Node prev = Jump(pos-2);
prev.next = null;
tail = prev;
numLinks--;
}
}
else if (pos == numLinks) {
Node prev = Jump(pos-2);
prev.next = null;
tail = prev;
numLinks--;
}
else {
Node prev = Jump(pos-2);
removedItem = prev.next.data;
prev.next = prev.next.next;
numLinks--;
}
return removedItem;
}
public int remove(T item) {
int pos = 0;
int numRemoved = 0;
Node nd = head;
while ((pos = find(item)) > 0) {
try {
remove(pos);
numRemoved++;
}
catch(ListException e) {
e.printStackTrace();
}
}
return numRemoved;
}
public int find(T item) {
int pos = 1;
Node nd = head;
for (int i = 0; i < numLinks; i++) {
if (nd.data.equals(item)) {
return pos;
}
pos++;
nd = nd.next;
}
return 0;
}
public T retrieve(int pos) throws ListException {
int numFound = 0;
Node nd = head;
if (pos < 1 || pos > numLinks + 1 ) {
throw new ListException (\"Postion Invalid\");
}
for (int i = 1; i < pos; i++) {
nd = nd.next;
}
return nd.data;
}
public int length() {
return numLinks;
}
public LinkedList<T> copy() {return null;}
public boolean isEmpty() {
return numLinks == 0;
}
public boolean equals(Object list) {return false;}
public void replace(T item, int pos) throws ListException {}
public LinkedList<T> combine(MyListIFace<T> list2) {return null;}
public LinkedList<T> reverse() {return null;}
}
Solution
I remove method, numLinks are not decrementing...
public int remove(T item) {
int pos = 0;
int numRemoved = 0;
Node nd = head;
while ((pos = find(item)) > 0) {
try {
remove(pos);
numRemoved++;
numLinks--; // missing num links statement
}
catch(ListException e) {
e.printStackTrace();
}
}
return numRemoved;
}
