220 DATA STRUCTURES

INFIX AND POSTFIX JAVA PROGRAM

1. Feel free to make changes to my code where you see fit

2. Please attempt to finish in an hour, please

3. Please use the code below that I provided

4. Follow the directions in the pictures, please

5. Also, post the bonus as a separate step so I can tell which part is the bonus or label it pleasee

6. And leave comments please throughout the code

Here is an example of the algorithm that was in the notes:

Now here's my code from the generic stack, list, and queue.

My Genric List:

/** Linked List implementation of our List abstract data type */ public class List { // put all fields from ListAsLinkedList class here class List implements IList { private Node head; private int size; public List() { } public void append(Datatype value) { if (this.head == null) { this.head = new Node(value); ++this.size; } else { Node currrent; for (current = this.head; current.next != null; current = current.next) { } current.next = new Node(value); ++this.size; } } public void prepend(Datatype value) { Node current = new Node(value); current.next = this.head; this.head = current; ++this.size; } public void deleteAt(int index) { if (index >= 0 && index  current = this.head; for(int i = 0; i = 0 && index  current = this.head; for (int i = 0; i  { // put all fields from Node class here public Datatype value; public Node next; public Node(Datatype value) { this.value = value; this.next = null; } } 

My Genric Queue:

/** Queue abstract data type */ public class Queue { /** List objects to hold our queue items. Use List operations to implement the methods below */ private List list; public Queue() { // instantiate list here list = newList(); } public void enqueue(Datatype value) { // add an item to the back of the queue list.append(value); } public Datatype dequeue() { // remove and return the item from the front of the queue Datatype deqVal = list.getValueAt(0); list.delteAt(0); return deqVal; } public Datatype front() { // return the iteam at the front of the queue return list.getValueAt(0); } public boolean isEmpty() { // return true if the queue is empty return list.size() == 0; } } 

My Generic Stack

/** Stack abstract data type */ public class Stack { /** List objects to hold our stack items. Use List operations to implement the methods below */ private List list; public Stack() { // instantiate list here list = newList(); } public void push(Datatype value) { // push an item onto the stack list.prepend(value); } public Datatype pop() { // pop an item off the stack Datatype popVal = list.getValueAt(0); list.deleteAt(0); return popVal; } public Datatype peek() { // peek at the item on the top off the stack return list.getValueAt(0); } public boolean isEmpty() { // returns true if the stack is empty return list.size() == 0; } } 

Your objective is to take an infix expression from the user, convert it into postfix form, then evaluate it to find an answer to the expression. You will need your generic Stack, generic Queue, generic List and generic Node class for this assignment. The reason why you will need generic classes, is that in some cases you will need to use a Stack of Character objects and in other cases you will need a Stack of Integer objects. Create a file called "Main.java" that would contain a public class called "Main". All work will be done inside this Main class. Here are the methods you must implement inside this class: - Entry point - This should prompt the user for an infix expression, send that expression to the infixToPostfix method (described below), this will return a postfix expression (as a string), you will then send that to evalPostfix (described below) for evaluation, and then finally print out the summary shown in the sample output. - int getinfixpriority (char c) - This takes in a char (a single character) and determines the infix priority as described in the notes. It then returns this priority. - int getstackPriority (char c) - This takes in a char (a single character) and determines the stack priority as described in the notes. It then returns this priority. - boolean isoperand (char c) - This will return true if c is an operand (basically a single digit from 0 to 9 inclusively). It will return false otherwise. To keep things simple, only single digit numbers are allowed in the input specified by the user. This means both the infix and the postfix notation will contain only single digit numbers. As you evaluate the expression, multi-digit numbers will naturally arise, and that's ok. - int eval (char operator, int a, int b) - The operator character is one of the following operators: +,,,/, or . These are the only operators allowed (except for parentheses which is not handled by this method). Simply return a value of 1 if the operator is invalid. a and b are your operands. The order goes, a operator b. This method returns the result of applying the given operator, operator, to the operands, a and b - String infixtoPostfix(String infixstring) - This method takes in an expression in infix form and produces the equivalent expression in postfix form. Here is where your stack and queue implementations will come into play. You must implement the algorithm from the notes. I don't want you grabbing some code from some online source and sticking it in here. - int evalpostfix(string postfixstring) - This takes an expression in postfix form and evaluates it, returning the evaluated result. All numbers are restricted to a single digit, no floating point numbers allowed, division symbols are handled as integer division, the final answer along with any intermediate answers are allowed to be multiple digits (i.e. it should return the mathematically correct answer, using integer division for any division). No input validation is needed here. Assume the user will only enter single digit numbers and no floats. Also assume the user will only enter valid operators along with parentheses (if desired). No spaces are allowed in the input (this is so parsing the input is made a little easier), so you can safely assume no spaces are in the input. The valid operators you must handle are: + (addition), - (subtraction), / (integer division), * (multiplication), and (exponentiation). Here are some sample outputs. Your output and prompts should look exactly like this, obviously with respect to whatever the user enters. \$ javac Main.java \$ java Main Enter infix expression: 23 Summary Infix: 23 Postfix: 23 Result: 1 \$ java Main Enter infix expression: 5+29 Summary - Infix: 5+29 Postfix: 529+ Result: 23 \$ java Main Enter infix expression: (52)/9 Summary -n-re- Infix: (5^2)/9 Postfix: 529/ Result: 2 BONUS: If you can add a conversion from postfix back into infix and then show the resulting infix form, I will add an additional 5 points to your assignment. To be clear, this means implementing the postfixToInfix method and calling it from main. Here are the details: - String postfixtolnfix(String postfixstring) - This method takes in an expression in postfix form and produces the equivalent expression in infix form. Here are some sample outputs with the bonus implementation. Your output for the infix form (converted back from postfix) may look a little different, but as long as it is correct (order of operations are correct as was originally specified by the user), then you are fine. Feel free to use extra parentheses as needed. \$ javac Main.java \$ java Main Enter infix expression: 23 Summary Infix: 23 Postfix: 23 - Back to Infix: (23) Result: 1 \$ java Main Enter infix expression: 5+29 Summary Infix: 5+29 Postfix: 529+ Back to Infix:(5+(29)) Result: 23 \$ java Main Enter infix expression: (52)/9 Summary Infix: (52)/9 Postfix: 529/ Back to Infix:((52)/9) Result: 2