HW4:

1) Implement MyArrayStack (constructor, push, pop, peek and isEmpty), and MyLinkedQueue with both next and previous pointers (constructor enqueuer/offer, dequeuer/poll, peek and isEmpty), and write the following two program to test them.

2) For stack testing, write a program to check if a string has matching parenthesis such as "(O)", but not "(.

3) For stack testing, use it to "Evaluating Expressions" using the algorithm given below.

The Algorithm for Step 3:

Phase 1: Scanning the expression

The program scans the expression from left to right to extract operands, operators, and the parentheses.

1.1. If the extracted item is an operand, push it to operandStack.

1.2. If the extracted item is a + or - operator, process all the operators at the top of operatorStack and push the extracted operator to operatorStack.

1.3. If the extracted item is a or / operator, process the or/operators at the top of operatorStack and push the extracted operator to operatorStack.

1.4. If the extracted item is a ( symbol, push it to operatorStack.

1.5. If the extracted item is a ) symbol, repeatedly process the operators from the top of operatorStack until seeing the ( symbol on the stack

Phase 2: Clearing the stack

Repeatedly process the operators from the top of operatorStack until operatorStack is empty.

Check the explanation

Explanation:

1)

import java.util.*;

public class ArrayStack {

// Declare an Array List

ArrayList<String> aList;

// Constructor that Instantiates arrayList object

ArrayStack() {

aList = new ArrayList<String>();

}

public void push(String object) {

//Add the Value

aList.add(object);

}

public String pop() {

String ret = null;

//Check the size of list if 0 means Stack is Empty

if (aList.isEmpty())

System.out.println("Stack is Empty");

else {

//Return the last value entered as Stack is LAST IN FIRST OUT

// Remove it

ret = aList.get(aList.size() - 1);

aList.remove(aList.size() - 1);

}

return ret;

}

public String peek() {

String ret = null;

//Check the size of list if 0 means Stack is Empty

if (aList.isEmpty())

System.out.println("Stack is Empty");

else {

//Return the last value entered as Stack is LAST IN FIRST OUT

// DO not remove it

ret = aList.get(aList.size() - 1);

}

return ret;

}

public boolean isEmpty() {

//Check the size of list if 0 means Stack is Empty

return aList.size()==0;

}

public static void insertionSort(int arr[], int n)

{

int i, j;

for(i=2;i< n;i++){

arr[0] = arr[i];

j = 1;

while(j <= i-1){

/* implement your code here /*

/* you must start compare arr[j] with a[0], notice that j = 1 */

}

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

ArrayStack aStack = new ArrayStack();

aStack.push("Hey");

aStack.push("Hello");

aStack.push("Bye");

System.out.println(aStack.pop());

System.out.println("Peek: " + aStack.peek());

System.out.println(aStack.pop());

System.out.println(aStack.isEmpty());

System.out.println(aStack.pop());

// int arr[] = new int[] {3,4,2,1,6,7,5};

// insertionSort(arr,7);

// System.out.println(Arrays.toString(arr));

}

}

LinkedQueue

interface QueueInterface {

public void enqueue(Object item);

// Effect: Adds item to the rear of this queue.

// Precondition: This queue is not full.

// Postcondition: item is at the rear of this queue.

public Object dequeue();

// Effect: Removes front element from this queue and returns it.

// Precondition: This queue is not empty.

// Postconditions: Front element has been removed from this queue.

// Return value = (the removed element)

public boolean isEmpty();

// Effect: Determines whether this queue is empty.

// Postcondition: Return value = (this queue is empty)

public boolean isFull();

// Effect: Determines whether this queue is full.

// Postcondition: Return value = (queue is full)

public int size();

}

public class LinkedQueue implements QueueInterface {

private class QueueNode

// Used to hold references to queue nodes for the linked queue

// implementation

{

private Object info;

private QueueNode link;

}

private QueueNode front; // reference to the front of this queue

private QueueNode rear; // reference to the rear of this queue

public LinkedQueue()

// Constructor

{

front = null;

rear = null;

}

public void enqueue(Object item)

// Adds item to the rear of this queue.

{

QueueNode newNode = new QueueNode();

newNode.info = item;

newNode.link = null;

if (rear == null)

front = newNode;

else

rear.link = newNode;

rear = newNode;

}

public Object dequeue()

// Removes front element from this queue and returns it.

{

Object item;

item = front.info;

front = front.link;

if (front == null)

rear = null;

return item;

}

public boolean isEmpty()

// Determines whether this queue is empty.

{

if (front == null)

return true;

else

return false;

}

public Object peek()

// Determines whether this queue is empty.

{

if (front == null)

return null;

else

return front.info;

}

public int size()

// Determines whether this queue is empty

{

QueueNode curr = front;

int count = 0;

while (curr != null) {

++count;

curr = curr.link;

}

return count;

}

public String toString()

// Determines whether this queue is empty.

{

QueueNode curr = front;

String res = "";

while (curr != null) {

res = res + curr.info + " ";

curr = curr.link;

Note that i could not complete the answers to all the question because the codes are above the character limit, you might need to ask the question 2 and 3 separately.

Kindly check the outputs in the attached images below

this would start to sound a little like mortal combat