I need help creating a creating a utility class that converts an infix expression to a postfix expression, a postfix expression to an infix expression and will evaluates a postfix expression.

I am supposed to create a generic queue class called MyQueue from scratch. MyQueue class will implement the QueueInterface already provided to me (See QueueInterface Below)

I also need to create a generic stack class called MyStack from scratch. MyStack class will implement the Stack Interface provided to me as well (See StackInterface Below)

The Notation class will have a method infixToPostfix to convert infix notation to postfix notation that will take in a string and return a string, a method postfixToInfix to convert postfix notation to infix notation that will take in a string and return a string, and a method to evaluatePostfix to evaluate the postfix expression. It will take in a string and return a double.

In the infixToPostfix method, I MUST use a queue for the internal structure that holds the postfix solution. Then use the toString method of the Queue to return the solution as a string.

For simplicity sake:

- operands will be single digit numbers

- the following arithmetic operations will be allowed in an expression:

+ addition

- subtraction

* multiplication

/ division

Exception Classes

Provide the following exception clases:

- InvalidNotationFormatException occurs when a Notation format is incorrect

- StackOverflowException occurs when a top or pop method is called on an empty stack.

- StackUnderflowException occurs when a push method is called on a full stack.

- QueueOverflowException occurs when a dequeue method is called on an empty queue.

- QueueUnderflowException occurs when a enqueue method is called on a full queue.

ALGORITHMS

Infix expression to postfix expression:

Read the infix expression from left to right and do the following:

- If the current character in the infix is a space, ignore it.

- If the current character in the infix is a digit, copy it to the postfix solution queue

- If the current character in the infix is a left parenthesis, push it onto the stack

- If the current character in the infix is an operator,

--> Pop operators (if there are any) at the top of the stack while they have equal or higher precedence than the current operator, and insert the popped operators in postfix solution queue

- Push the current character in the infix onto the stack

-If the current character in the infix is a right parenthesis

-Pop operators from the top of the stack and insert them in postfix solution queue until a left parenthesis is at the top of the stack, if no left parenthesis-throw an error

-Pop (and discard) the left parenthesis from the stack

When the infix expression has been read, Pop any remaining operators and insert them in postfix solution queue.

Postfix expression to infix expression:

Read the postfix expression from left to right and to the following:

- If the current character in the postfix is a space, ignore it.

- If the current character is an operand, push it on the stack

- If the current character is an operator,

--> Pop the top 2 values from the stack. If there are fewer than 2 values throw an error

- Create a string with 1st value and then the operator and then the 2nd value.

- Encapsulate the resulting string within parenthesis

- Push the resulting string back to the stack

- When the postfix expression has been read:

--> If there is only one value in the stack it is the infix string, if more than one value, throw an error

Evaluating a postfix expression

Read the postfix expression from left to right and to the following:

- If the current character in the postfix expression is a space, ignore it.

- If the current character is an operand or left parenthesis, push on the stack

- If the current character is an operator,

--> Pop the top 2 values from the stack. If there are fewer than 2 values throw an error --> Perform the arithmetic calculation of the operator with the first popped value as the right operand and the second popped value as the left operand --> Push the resulting value onto the stack

When the postfix expression has been read:

- If there is only one value in the stack it is the result of the postfix expression, if more than one value, throw an error

Example (I have already created the GUI):

QueueInterface.java

import java.util.ArrayList;

/** Interface for a Queue data structure * * @author Professor Kartchner * * @param data type */ public interface QueueInterface { /** provide two constructors * 1. takes an int as the size of the queue * 2. default constructor - uses a default as the size of the queue * */

/** * Determines if Queue is empty * @return true if Queue is empty, false if not */ public boolean isEmpty();

/** * Determines of the Queue is empty * @return */ public boolean isFull();

/** * Deletes and returns the element at the front of the Queue * @return the element at the front of the Queue */ public T dequeue() throws QueueUnderflowException;

/** * Number of elements in the Queue * @return the number of elements in the Queue */ public int size();

/** * Adds an element to the end of the Queue * @param e the element to add to the end of the Queue * @return true if the add was successful, false if not */ public boolean enqueue(T e) throws QueueOverflowException;

/** * Returns the string representation of the elements in the Queue, * the beginning of the string is the front of the queue * @return string representation of the Queue with elements */ public String toString();

/** * Returns the string representation of the elements in the Queue, the beginning of the string is the front of the queue * Place the delimiter between all elements of the Queue * @return string representation of the Queue with elements separated with the delimiter */ public String toString(String delimiter);

/** * Fills the Queue with the elements of the ArrayList, First element in the ArrayList * is the first element in the Queue * YOU MUST MAKE A COPY OF LIST AND ADD THOSE ELEMENTS TO THE QUEUE, if you use the * list reference within your Queue, you will be allowing direct access to the data of * your Queue causing a possible security breech. * @param list elements to be added to the Queue */ public void fill(ArrayList list);

}

--------------------------------------------------------------------------------------------------------------------------------------------------------

StackInterface.java

import java.util.ArrayList;

/** Interface for a generic Stack data structure * * @author Professor Kartchner * * @param data type */ public interface StackInterface {

/** * Provide two constructors * 1. takes in an int as the size of the stack * 2. default constructor - uses default as the size of the stack */

/** * Determines if Stack is empty * @return true if Stack is empty, false if not */ public boolean isEmpty();

/** * Determines if Stack is full * @return true if Stack is full, false if not */ public boolean isFull();

/** * Deletes and returns the element at the top of the Stack * @return the element at the top of the Stack */ public T pop() throws StackUnderflowException;

/** * Returns the element at the top of the Stack, does not pop it off the Stack * @return the element at the top of the Stack */ public T top() throws StackUnderflowException;

/** * Number of elements in the Stack * @return the number of elements in the Stack */ public int size();

/** * Adds an element to the top of the Stack * @param e the element to add to the top of the Stack * @return true if the add was successful, false if not */ public boolean push(T e) throws StackOverflowException;

/** * Returns the elements of the Stack in a string from bottom to top, the beginning * of the String is the bottom of the stack * @return an string which represent the Objects in the Stack from bottom to top */ public String toString();

/** * Returns the string representation of the elements in the Stack, the beginning of the * string is the bottom of the stack * Place the delimiter between all elements of the Stack * @return string representation of the Stack from bottom to top with elements * separated with the delimiter */ public String toString(String delimiter);

/** * Fills the Stack with the elements of the ArrayList, First element in the ArrayList * is the first bottom element of the Stack * YOU MUST MAKE A COPY OF LIST AND ADD THOSE ELEMENTS TO THE STACK, if you use the * list reference within your Stack, you will be allowing direct access to the data of * your Stack causing a possible security breech. * @param list elements to be added to the Stack from bottom to top */ public void fill(ArrayList list); }