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: (20 points)

Develop a new stand-alone generic class, called StackYourname, to implement, among others, key stack operations [push(e), pop(), peek(), size(), isEmpty()]we discussed in the class. Note that our LinkedList class does not use variable size, but you can use variable size in this class StackYourname. Again, class Stack 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.

StackYourname Class must have these methods

• methodname(argument): return type
• isEmpty(): Boolean Returns true if this stack is empty
• size(): int Returns the number of elements in this stack
• peek(): E Returns the top element in this stack
• pop(): E Returns and removes the top element in this stack
• push(E element): E Adds a new element to the top of this stack
• search(E element): int Returns the position of the specified element in this stack
• toString(): String Returns the String with all elements in current stack

Part 2: (10 points)

Next, develop a simple test program called TestStackYourname, similar to that you developed in 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 need to show the stack content before and after calling a stack operation. Use proper labels. Please DO NOT hard-code test data. Make sure to allow the user to enter the stack content using interactive menu (embedded inside the sentinel loop):

-----MAIN MENU----- 0 - Exit Program 1 - Push 2 - Pop 3 Peek (Top) 4 - Size 5 Is Empty? 6 - Print Stack

Again, you cannot change method names, return type and parameter types.

To evaluate your Classs methods, the instructor will use another Test Program and will use your methods.

Part 3: (10 points)

Using class StackYourname above, implement another short and simple program, call it TestPalindromeYourname, which prompts the user to enter a string value of any length. Using class StackYourname, the TestPalindrome 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).

This program is case insensitive. Also, it ignores whitespaces.

Enter a string: Race car Input String: Race car Judgment: Palindrome

Enter a string: CS5040 Input String: CS5040 Judgment: Not Palindrome

You can use a sentinel loop to run the program again and again. But it is not mandatory, it is good even if your program runs only one time.

Part 4: (10 points)

Using class StackYourname above, implement another short and simple program, call it PostfixEvalYourname, which prompts the user to enter a string value of postfix expression. Using class StackYourname, the program should evaluate the postfix expression and get the correct calculated result. The program displays both the input

Assumption:

Input postfix string doesnt have whitespaces.

All input number is one-digit number. (positive digit 0 to 9)

Operator ^ + - * / can be used.

If postfix input is not calculatable, show the result

Enter a string: 562^2-* Result value: 170

Enter a string: 562^2- Result value: The input Postfix expression is not valid.

This is the code from the previous assignment:

LinkedList.java:

public class LinkedList { Node head; Node tail; public class Node { E data; Node next; public Node(E element) { data = element; next = null; } @Override public String toString() { return String.valueOf(this.data); } } public void add(int index, E element) { Node temp1 = head; while (--index > 0) temp1 = temp1.next; Node temp = new Node(element); temp.next = temp1.next; temp1.next = temp; } public void addFirst(E element) { Node temp = new Node(element); if (head == null) { tail = temp; } temp.next = head; head = temp; } public void addLast(E element) { Node temp = new Node(element); if (tail == null) { tail = temp; head = temp; } else { tail.next = temp; tail = temp; } } public E getFirst() { return head.data; } public E getLast() { return tail.data; } public void remove(int index) { Node temp1 = head; while (--index > 0) temp1 = temp1.next; temp1.next = temp1.next.next; } public E removeFirst() { E data = head.data; head = head.next; return data; } public E removeLast() { E data = tail.data; Node temp = head; while (temp.next != tail) { temp = temp.next; } temp.next = null; tail = temp; return data; } public int size() { int count = 0; Node temp = head; while (temp != null) { temp = temp.next; count++; } return count; } @Override public String toString() { Node temp = head; String str = "["; while (temp.next != null) { str = str + temp.data + ","; temp = temp.next; } str = str + temp.data; return str + "]"; } } 

ListTestYourName.java:

import java.util.Scanner; public class ListTestYourName { public static void main(String[] args) { int option; Scanner keyboardInput = new Scanner(System.in); // declare and initialize LinkedList object LinkedList list = new LinkedList<>(); // continue to get user choice until the option is 0 do { // display menu System.out.println("----- Linked List Test Program -----"); 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.print("Select option: "); // get user option option = keyboardInput.nextInt(); // option check switch (option) { // check addFirstNode method case 1: System.out.println("Testing method addFirstNode()"); // get the element to be inserted System.out.print("Enter the first node element: "); int nodeFirstElement = keyboardInput.nextInt(); // call addFirst method list.addFirst(nodeFirstElement); // print the list after insertion System.out.println("List contents after adding first node is : " + list.toString()); break; // check addLast method case 2: System.out.println("Testing method addLastNode()"); // get the element to be inserted System.out.print("Enter the last node element: "); int nodeLastElement = keyboardInput.nextInt(); // call addLast method list.addLast(nodeLastElement); // print the list after insertion System.out.println("List contents after adding last node is : " + list.toString()); break; // check add method case 3: System.out.println("Testing method add()"); // get the index at which it should be inserted System.out.print("Enter the index in which element to be inserted: "); int index = keyboardInput.nextInt(); // get the element to be inserted System.out.print("Enter the node element to be inserted: "); int nodeElement = keyboardInput.nextInt(); // call add method with index and element list.add(index, nodeElement); // print the list after insertion System.out.println("List contents after adding node at given index is : " + list.toString()); break; // check removeFirst method case 4: // when there is no element in the list if (list.size() == 0) { System.out.println("List is Empty now."); } else { // if there is element in list System.out.println("List contents before removing first node is: " + list.toString()); list.removeFirst(); System.out.println("List contents after removing first node is : " + list.toString()); } break; // check removeLast method case 5: // when there is no element in the list if (list.size() == 0) { System.out.println("List is Empty now."); } else { // if there is element in list System.out.println("List contents before removing last node is: " + list.toString()); list.removeLast(); System.out.println("List contents after removing last node is : " + list.toString()); } break; // check remove method case 6: if (list.size() == 0) { System.out.println("List is Empty now."); } else { // if there is element in list get index at which the removed System.out.println("Enter the index of the node to be removed: "); int indexRemove = keyboardInput.nextInt(); // print the list contents before removal System.out.println( "List contents before removing node at index " + indexRemove + " is: " + list.toString()); // call remove method list.remove(indexRemove); // print the list contents after removal System.out.println( "List contents after removing node at index " + indexRemove + " is: " + list.toString()); } break; // display the size of the list case 7: System.out.println("Size of the list is: " + list.size()); break; // terminate the program case 0: System.out.println("Good Bye!!!"); break; default: System.out.println("Invalid choice!!!"); break; } } while (option != 0); keyboardInput.close(); } }