Write a class calledEvaluatorwith the following static methods.

public static Deque infixToPostfix(Deque in) public static BigInteger evalPostfix(Deque in)

TheinfixToPostfixmethod should take an infix expression and return a postfix expression. TheevalPostfixmethod should take a postfix expression and return the evaluated result as aBigInteger. Clients of your class can invoke the methods asEvaluator.infixToPostfixandEvaluator.evalPostfix. Because these are static, they do not exist inside objects, so nobody should ever donew Evaluator.

Each of these Deque's is behaving like a Queue, with the front of the Queue being the first element of the expression being evaluated. For example, "(1+3)-2" is represented as the Queue ["(", "1", "+", "3", ")", "-", "2"]. Your methods should not alter the Deques passed as parameters. Instead, your methods should make a local copy and remove from the local copy. You can copy a collection by passing the collection to copy to the new collection's constructor.

Deque copy = new ArrayDeque(in);

Each string in each Deque should be either an integer of any length (ie, one or more digit characters preceded by '-' if negative) or any one of the symbols,*,/,+,-,%,(,). These single-character strings will represent their usual meaning as mathematical operators. No other character or space should appear in any of the strings.

The methodinfixToPostfixshould rearrange the order of the strings into a new Deque (and delete all parentheses) using Dijkstra's Shunting-Yard algorithm (http://www.oxfordmathcenter.com/drupal7/node/628). The methodevalPostfixshould evaluate a postfix expression and return its result as aBigIntegerobject. Recall that postfix evaluation is done by pushing each value onto a stack, and each time an operator is encountered popping two values off the stack and pushing the operator's result back onto the stack. Once the postfix expression is consumed there should be a single value on the stack and it should be the result. Some simple pseudocode can be found in the Stack and Queue lecture slides.

You should read the javadoc forBigInteger, it has built-in all the mathematical operations you need to do your calculations. If an input has an error, the method should throw anIllegalArgumentException. Errors could occur because strings contain incorrect characters or expressions are not well-formed. If any of this specification is ambiguous, post a query to Piazza asking for clarification.

Testing

You should write and submit a classEvaluatorTestwhich is a comprehensive test that prints the single word "true" to the screen if all tests pass and the single word "false" if any test does not pass. You can look at theDeck / Card test driverto get the idea of what I'm looking for.

You should test your class in a variety of situations, some ordinary some extreme. You should study the specification carefully and ask yourself what are the weirdest inputs I can give to methods that is within spec, and then test your code to make sure it behaves correctly. That's what I will do and if your program fails any of my tests, you will get no credit. If you think the specification is ambiguous or unclear, it's your responsibility to ask for clarification.