Implement MyArrayStack (constructor, push, pop, peek and isEmpty), MyLinkedStack (constructor, push, pop, peek and isEmpty) and MyLinkedQueue (constructor, offer, poll, peek and isEmpty), and write the following two program to test them. (10 points) [Please do not leave out the MyLinkedQueue. It is required and also do not exclude the methods as well for each of the following classes]

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

For stack testing, use it to Evaluating Expressions (10 points)

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 operatorStackuntil seeing the ( symbol on the stack.

Phase 2: Clearing the stack

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

Bonus: support for exponent ^ and use HashMap for counting keyword occurrence in a Java program.

This is what I have so far.

public class MyArrayStack

{

private int stackSize;

private T[] stackArr;

private int top;

public MyArrayStack(int size)

{

this.stackSize = size;

this.stackArr = (T[]) new Object[stackSize];

this.top = -1;

}

public void push(T entry)

{

if(this.full())

{

System.out.println(("Stack is full. Increasing the capacity."));

}

this.stackArr[++top] = entry;

}

public T pop() throws Exception

{

if(this.isEmpty())

{

throw new Exception("Stack is empty. Can not remove element.");

}

T entry = this.stackArr[top--];

return entry;

}

public T peek()

{

return stackArr[top];

}

public boolean isEmpty()

{

return (top == -1);

}

public boolean full()

{

return (top == stackSize - 1);

}

}

========================================================================

import java.util.EmptyStackException;

public final class MyLinkedStack implements StackInterface

{

private Node topNode;

public MyLinkedStack()

{

topNode = null;

}

public void push(T entry)

{

topNode = new Node(newEntry, topNode);

}

public T pop()

{

T top = peek();

assert (topNode != null);

topNode = topNode.getNextNode();

return top;

}

public T peek()

{

if (isEmpty())

{

throw new EmptyStackException();

}

else

{

return topNode.getData();

}

}

public boolean isEmpty()

{

return (top == -1);

}

public boolean full()

{

return (top == stackSize - 1);

}

}

=============================================================================================

import java.util.NoSuchElementException;

import java.util.Iterator;

public class MyLinkedQueue

{

Node head;

Node tail;

int n;

public MyLinkedQueue()

{

head=null;

tail=null;

n=0;

}

class Node

{

Node next;

Object object;

Node(Object o)

{

this.object=o;

}

Node()

{

}

}

public boolean isEmpty()

{

return head==null;

}

public int length()

{

return n;

}

public E poll()

{

if (tail.next == null)

return null;

tail = tail.next;

E e = tail.o;

tail.o = null;

return e;

}

public void offer(Object o)

{

if (o==null)

return;

Node old=tail;

tail=new Node();

tail.object=o;

tail.next=null;

if (isEmpty())

head=tail;

else

old.next=tail;

n++;

}

public Object peek()

{

if (isEmpty())

throw new NoSuchElementException("Queue underflow");

return head.object;

}

}

===============================================================================================

//One of the two programs to test

import java.util.Scanner;

import java.util.Stack;

public class ExpressionCalculator

{

public static void main(String[] args)

{

MyLinkedQueue mlk = new MyLinkedQueue();

}

/*public static void main(String[] args)

{

Scanner consoleIn = new Scanner(System.in);

System.out.println("Enter an expression: ");

String expression = consoleIn.nextLine().replaceAll("\\s+", "");

consoleIn.close();

Stack numstack = new Stack();

Stack operandStack = new Stack();

int pos = 0;

while (pos < expression.length())

{

char ch = expression.charAt(pos);

pos += 1;

if (isOperator(ch))

{

if (operandStack.size() == 0)

{

operandStack.push(ch);

}

else

{

char previousOp = operandStack.pop();

if (precedence(ch) > precedence(previousOp))

{

operandStack.push(previousOp);

}

else

{

evaluateTop(numstack, previousOp);

}

operandStack.push(ch);

}

}

else if (ch == '(')

{

operandStack.push(ch);

}

else if (ch == ')')

{

boolean done = false;

while (!done)

{

if (operandStack.size() == 0)

{

printError("No matching");

}

char previousOp = operandStack.pop();

if (previousOp == '(')

{

done = true;

}

else

{

evaluateTop(numstack, previousOp);

}

}

}

else if (Character.isDigit(ch))

{

int start = pos - 1;

while (pos < expression.length() && Character.isDigit(expression.charAt(pos)))

{

pos += 1;

}

String number = expression.substring(start, pos);

numstack.push(Integer.parseInt(number));

}

else

{

printError("Number, operator or parenthesis expected.");

}

}

while (operandStack.size() > 0)

{

char previousOp = operandStack.pop();

if (previousOp == '(')

{

printError("No matching");

}

else

{

evaluateTop(numstack, previousOp);

}

}

if (numstack.size() == 0)

{

printError("Invalid expression");

}

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

if (numstack.size() > 0)

{

printError("Invalid expression");

}

}

public static boolean isOperator(char ch)

{

return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%';

}

public static void printError(String message)

{

System.out.println("ERROR! " + message);

System.exit(1);

}

public static int precedence(char ch)

{

if (ch == '+' || ch == '-')

{

return 1;

}

else if (ch == '*' || ch == '/' || ch == '%')

{

return 2;

}

else

{

return 0;

}

}

public static void evaluateTop(Stack stack, char operator)

{

if (stack.size() == 0)

{

printError("Invalid expression");

}

int y = stack.pop();

if (stack.size() == 0)

{

printError("Invalid expression");

}

int x = stack.pop();

int z = 0;

if (operator == '*')

{

z = x * y;

}

else if (operator == '/')

{

if (y == 0)

{

printError("Divide by 0");

}

else

{

z = x / y;

}

}

else if (operator == '+')

{

z = x + y;

}

else if (operator == '-')

{

z = x - y;

}

else if(operator=='%')

{

z=x%y;

}

else

{

printError("Syntax error");

}

stack.push(z);

} */

}

//Basically I got stuck when I tried to edit ExpressionCalculator . Is there a way for me to fix the ExpressionCalculator class?