Assignment Description:
The goal for this assignment is to implement Stack ADT using linked-list implementation. Then, write a program to use an object of the developed Stack class to solve simple and practical problems.
Part 1: (50 points)
Reusing some and related code from the LinkedList.java class you completed for assignment #2, develop a new class, called Stack.java, to implement stack operations [push(e), pop(), top(), size(), isEmpty()]we discussed from Chapter 20 (see slide 20, file Chapter-20-Part3-Stacks). Note that our LinkedList class does not use variable size, so you may use variable size in class stack as you implement method size() for stack. Also, the stack class needs to be defined as generic stack with type so that we can create stack objects that can hold data of different types, such as integer stack, string stack, char stack, double stack, etc. Furthermore, define class Node as part of class Stack, similar to class LinkedList in the previous assignment.
Next, develop a simple test program called TestStack.java, similar to that you developed for the previous assignment, to test each stack operation listed above and defined in your class Stack. Use integer type stack for the test program. Organize the outputs of this test program similar to that of test linked list, where you show the stack content before and after calling an operation with proper labels.
Part 2: (25 points)
Using class Stack.java above, implement another simple and short program, called ReverseString.java, which prompts the user to enter a string of any length. Using class Stack, the program creates one stack object that holds strings and uses the stack object to reverse the input string. Note that we are required to extract individual words from the input string and put onto the stack. The program displays both the original input string and the reversed string with proper labels.
For example, if the user enters the string: This is a test string
The program output, including the prompt, input string, and output would be as follows:
—-jGRASP exec: java -ea ReverseString Enter a string: This is a test string Input String: This is a test string Reversed String: string test a is This —-jGRASP: operation complete.
Design the program such that it allows the user to re-enter different inputs (strings) during the same run session. Use a proper prompt such “Do you want to re-run code with different input string (Y/N)?” If the user enters Y, the program then prompts the user for new input string. Otherwise, the program terminates. Document your code and organize the outputs properly.
Part 3: (25 points)
Using class Stack.java above, implement another short and simple program, call it TestPalindrome.java, which prompts the user to enter a string of any length. Using class Stack, the program creates one stack object and uses the object to check whether the entered input string is a palindrome or not. The program displays both the input string and the judgment statement (Palindrome or Not Palindrome). The sample program runs below show the output and its format.
—-jGRASP exec: java -ea TestPalindrome Enter a string: Racecar Input String: Racecar Judgment: Palindrome —-jGRASP: operation complete.
—-jGRASP exec: java -ea TestPalindrome Enter a string: CS5040 Input String: CS5040 Judgment: Not Palindrome —-jGRASP: operation complete.
Design the program such that it allows the user to re-enter different inputs during the same run session. Use a proper prompt such “Do you want to re-run code with different input string (Y/N)?” If the user enters Y, the program then prompts the user for new input string. Otherwise, the program terminates. Document your code and organize the outputs properly.

HW-2 Java Program

LinkedList.java

/*
This class define a linked list that stores integer values.
*/
public class LinkedList
{
public Node head, tail;

//constructor method to create a list of object with head, tail, and size.
public LinkedList()
{
head = null;
tail = null;
}
  
//method add node to tail of list
public void addLastNode(int data)
{
if (tail == null)
head = tail = new Node(data); //empty list
else
{
tail.next = new Node(data); //link new node as last node
tail = tail.next; //make tail pointer points to last node
}
}
  
//======== Your part to complete for this assignment =========
//method #1: add first node
public void addFirstNode(int data)
{
Node nptr = new Node(data);
  
if(head == null)
{
head = nptr;
tail = head;
}
else
{
nptr.next=head;
head = nptr;
}
}
  
//method #2: add node at index
public void addAtIndex(int index, int data)
{
Node nptr = new Node(data);
Node ptr = head;
int size=countNodes();
index = index – 1 ;
for (int i = 1; i
{
if (i == index)
{
Node tmp = ptr.next ;
ptr.next=nptr;
nptr.next=tmp;
break;
}
ptr = ptr.next;
}
}
  
//method #3: remove first node
public void removeFirstNode()
{
if(head!=null)
head = head.next;
}
  
//method #4: remove last node
public void removeLastNode()
{
Node s = head;
Node t = head;
while (s != tail)
{
t = s;
s = s.next;
}
tail = t;
tail.next=null;
}
  
//method #5: remove node at index
public void removeAtIndex(int index)
{
int size=countNodes();   
if (index == 1)
{
head = head.next;
return ;
}
if (index == size)
{
Node s = head;
Node t = head;
while (s != tail)
{
t = s;
s = s.next;
}
tail = t;
tail.next=null;
return;
}
Node ptr = head;
index = index – 1 ;
for (int i = 1; i
{
if (i == index)
{
Node tmp = ptr.next;
tmp = tmp.next;
ptr.next=tmp;
break;
}
ptr = ptr.next;
}
}
  
//method #6: countNodes
public int countNodes()
{
int listSize= 0;
//complete this method
//this methods returns th//e list size
Node temp=head;
while(temp!=null)
{
listSize++;
temp=temp.next;
}
return listSize;
}

//method #7: pritnInReverse (Recursive method)
public void printInReverse(Node L)
{
if ( L != null )
{
printInReverse(L.next);
System.out.print(L.data+” “);
}
  
}   
  

//================= tail of your part ==============

//method to print out the list
public void printList()
{
Node temp;
temp = head;
while (temp != null)
{
System.out.print(temp.data + ” “);
temp = temp.next;
}
}
  
//class to create nodes as objects
private class Node
{
private int data; //data field
private Node next; //link field
  
public Node(int item) //constructor method
{
data = item;
next = null;
}
}
}

myTest.java

import java.util.Scanner;

public class myTest
{
public static void main (String[] args)
{
LinkedList myList = new LinkedList(); //create a list object
System.out.println(“Singly Linked List Testn”);
int choice;
Scanner scan = new Scanner(System.in);
/* Perform list operations */
System.out.println(“nSingly Linked List Operationsn”);
System.out.println(“0. Exit Program”);
System.out.println(“1. Add First Node”);
System.out.println(“2. Add Last Node”);
System.out.println(“3. Add At Index”);
System.out.println(“4. Remove First Node”);
System.out.println(“5. Remove Last Node”);
System.out.println(“6. Remove At Index”);
System.out.println(“7. Print List Size”);
System.out.println(“8. Print List (forward)”);
System.out.println(“9 Print List In Reverse”);
  
do
{
System.out.print(“nEnter your choie: “);
choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.print(“nEnter integer element to insert: “);
myList.addFirstNode(scan.nextInt() );   
break;
case 2 :
System.out.print(“nEnter integer element to insert: “);
myList.addLastNode(scan.nextInt() );   
break;   
case 3 :
System.out.print(“nEnter integer element to insert:”);
int num = scan.nextInt() ;
System.out.print(“Enter position: “);
int pos = scan.nextInt() ;
if (pos <= 1 || pos > myList.countNodes())
System.out.println(“Invalid positionn”);
else
myList.addAtIndex(pos, num);
break;   
case 4:
myList.removeFirstNode();
break;
case 5:
myList.removeLastNode();
break;
case 6 :
System.out.print(“nEnter position: “);
int p = scan.nextInt() ;
if (p < 1 || p > myList.countNodes())
System.out.println(“Invalid positionn”);
else
myList.removeAtIndex(p);
break;
case 7 :
System.out.println(“nSize of the list is : “+myList.countNodes());
break;   
case 8 :
System.out.println(“nList is: “);
myList.printList();
System.out.println(“n”);
break;
case 9 :
System.out.println(“nReverse list is: “);
myList.printInReverse(myList.head);
System.out.println(“nn”);
break;
case 0:
break;
default :
System.out.println(“nWrong Entry n “);
break;   
}
/* Display List */
  
} while (choice!=0);
}
}



Source link

Leave a Reply

Your email address will not be published. Required fields are marked *