Infix, prefix, Postfix expression in Java using Queue & Stacks. . I am having trouble implementing the Psuedocode for the algorithm. Provided the instructions , my implementation of a Generic Queue & Stack. Psuecode for the algorithm.

You will need a generic Stack and a generic Queue class for this assignment. The reason why you will need generic classes, is that in some cases you will need to create a Stack and/or Queue of Character objects and in other cases you will need Integer objects. It is up to you to decide which is needed where.

Create a file called Main.java, put a public class called Main inside of it, and use this class to work on this assignment. All work will be done inside this class as there is no work needed in the Stack, Queue, nor List classes. You must create and use the following methods:

We use an infix Queue that represents the arithmetic expression received from the user (String infix=scanner.nextLine())

tokenized to char

We use a postfix Queue and an operator stack

Methods to be implemented

----public static void main(String[]args)

This method should prompt the user for an infix expression, send that expression to the infixToPostfix method (described below), print out the postfix form, send the postfix form to evalPostfix (described below) for evaluation, then print out the integer result of evaluation.

---private static int getInfixPriority(char c) o This takes in a char (a single character) and determines the infix priority It then returns this priority

Already implemented code below

public static int getInfixPriority(char c) { switch (c) { case '(': return 4; case '^': return 3; case '*': return 2; case '/': return 2; case '+': return 1; case '-': return 1; } return 0; }

---private static int getStackPriority(char c) o This takes in a char (a single character) and determines the stack priority It then returns this priority

Already implemented code below

private static int getStackPriority(char c) {

switch (c) { case '^': return 2; case '*': return 2; case '/': return 2; case '+': return 1; case '-': return 1; } return 0; }

---private static boolean isOperand(char c) o 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 thats ok.

---private static int eval(char op,int a,int b) o The op 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. o a and b are your operands. The order goes, a op b. o This method returns the result of applying the given operator ,op,to the operands,a

and b

private static String infix To Post fix(String infix) o 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 **Algorithm provided below**

private static int eval Postfix(String postfix) o This takes an expression in postfix form and evaluates it, returning the evaluated result.

private static StringinfixToPrefix(String infix) o This method takes in an expression in infix form and produces the equivalent expression

in prefix form.

private static int evalPrefix(String prefix) o This takes an expression in prefix 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, with respect to whatever the user enters:

$ javac Main.java $ java Main Enter infix expression: 3*4-(7-8/2)

Postfix: 34*782/-- Result: 9

GENERIC CODE FOR QUEUE

public class Queue { private List list; public Queue() { list = new List(); } public void enqueue(T value) { list.append(value); } public T dequeue() { Object container = list.getContainerAt(0); if (container != null) { T value = list.getValueFromContainer(container); list.delete(container); return value; } else { return null; } } public T peekFront() { Object container = list.getContainerAt(0); if (container != null) { T value = list.getValueFromContainer(container); return value; } else { return null; } }

GENERIC CODE FOR STACK

public class Stack { private List list;

public Stack() { list = new List(); }

public void push(T value) { list.prepend(value); }

public T pop() { Object container = list.getContainerAt(0); if (container != null) { T value = list.getValueFromContainer(container); list.delete(container); return value; } else { return null; } }

public T peekTop() { Object container = list.getContainerAt(0); if (container != null) { T value = list.getValueFromContainer(container); return value; } else { return null; } }

public boolean isEmpty() { return list.size() == 0; } }

Psuecode below

Here is the algorithm: infixQ infix expression postfixQ empty queue opers empty stack repeat token,"-infixo. dequeue() if token is an operand then postfixQ.enqueue (token) else if token is a right parenthesis then op opers.pop () while op is not a left parenthesis postfixQ.enqueue (op) op opers.pop() end else if opers is not empty then op opers.peekTop() while stack priority(op) infix priority(token) op-opers.pop () postfix.enqueue (op) if opers is not empty then opopers.peekTop () else break end end end opers.push (token) end until infixQ is empty while opers is not empty op oper.pop () postfix0.enqueue (op) end e through this algorithm