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.

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

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.