In this project you will create your own stack and name it MyStack.

Requirements for MyStack:

Use an array of Strings as the underlying data structure. $($Just an array of string not a generic data

type$)$

Top should store the index of the last element. Pay attention that in the example of the textbook

top pointed to the empty space after the last element. But in MyStack top should point the last

element $($the first element to be popped$).$ For instance, if the following is the current state of the

stack, top should be $4.$

$123255437612$

Top $=5$

For an empty stack problem: prevent the user to pop from an empty stack and print a message.

For a full stack problem: if the stack size is n and the user attempts to push the element number

n$+1,$ the first element should be removed. One way to implement it$,$ is copying the old array in a

new one without the first element. But you should NOT use this approach because it is too

expensive. With this approach, after the stack is full, for each push you need O$($n$)$ time. You must

use a circular array to implement it with the cost of O$(1)$ for every operation.

There is a circular array implementation in your textbook $($chapter $14),$ in this implementation

the stack will be full if n$-1$ space of the array is taken. But with your implementation stack should

be considered as full if all the elements are full. So$,$ with an array of size n$,$ textbook example

holds maximum n$-1$ values but your implementation will hold n values.

In the driver class you should let the user test your stack. The following output is part of the test:

What is the size of the stack?

$3$

$============================$

Choose from the menu:

$1.$ Push.

$2.$ Pop.

$3.$ Peak.

$4.$ Exit.

$1$

Enter an integer to push into the stack:

$1$

Elements in the stack:

$[1]$

$============================$

Choose from the menu:

$1.$ Push.

$2.$ Pop.

$3.$ Peak.

$4.$ Exit.

$1$

Enter an integer to push into the stack:

$2$

Elements in the stack:

$[12]$

$============================$

Choose from the menu:

$1.$ Push.

$2.$ Pop.

$3.$ Peak.

$4.$ Exit.

$1$

Enter an integer to push into the stack:

$3$

Elements in the stack:

$[123]$

$============================$

Choose from the menu:

$1.$ Push.

$2.$ Pop.

$3.$ Peak.

$4.$ Exit.

$1$

Enter an integer to push into the stack:

$4$

Elements in the stack:

$[234]$

$============================$

Choose from the menu:

$1.$ Push.

$2.$ Pop.

$3.$ Peak.

$4.$ Exit.

$2$

$4$ is removed from the stack.

Elements in the stack:

$[23]$

$============================$

Choose from the menu:

$1.$ Push.

$2.$ Pop.

$3.$ Peak.

$4.$ Exit.

$4$

Elements in the stack:

$[23]$

As you see on the above example, a stack with size $3$ is created. Then user four times selected

the push operator and tried to push $1,2,3,$ and $4.$ When $4$ was pushed, $1$ was remove and $4$

became the top of the stack. So$,$ the fifth operation was pop, which popped $4.$ Your code should

print the elements of the stack after each operation.

Then create a class that converts an infix expression to a postfix one $($InfixToPostfix$.$java$)$ and

create another class that evaluates a postfix expression to find the result $($PostfixEvaluator$.$java$).$

In the same driver class, after giving the chance for the user to test your stack. Prompt the user

to enter an infix expression. Your application should show the postfix form of the input and the

result. Then ask if the user wants to enter another infix expression. You should use MyStack,

InfixToPostfix and PostfixEvaluator classes for this part of the project.

Sample output for the second part of the project:

Enter an infix expression:

$(3*4-(2+5))*4/2$

The postfix form of the expression is:

$34*25+-4*2/$

Result $=10$

Do you want to continue?

yes

Enter an infix expression:

$35*2-3*10$

The postfix form of the expression is:

$352*310*-$

Result $=40$

Do you want to continue?

no

Your program must accept a string and your code should separate it to the tokens. The user can

enter a string that contains four main operators $(+,-,*,/),$ operands $($number that can have more

than one digit$),$ and parentheses.

Important: If your program doesn$$t accept multiple digit numbers, when I test it will give an error.

Here is the algorithm for converting an infix expression to a postfix expression:

While $($there is a character in the postfix string$)$

$\{$

Read a token. A token can be a number $($as operand$),$ an open parenthesis, a close

parenthesis, or an operator $(+,-,*,/)$

If token is $(,$ push it into the stack

else If token is $),$ pop and save them into the output array$*$ one by one until $($ is popped

else If token is operand$**$

$,$ save it in the output array

else token is operator,

pop all elements in the stack and save them into the output array one by one until

the top element in the stack is lower or equal priority than the token.

push the token onto the stack

$\}$

Pop all elements in the stack and save them into the output array one by one.

$*$ Create an array of strings to store the tokens.

Class names should be:

$$ Tester.java $($for the driver class with the main method$)$

$$ MyStack.java

$$ InfixToPostfx

$$ PostfixEvaluator.java