Problem 3: InfixEvaluator class (25') Description: Please write a progran that can evaluate an infix arithmetic expressions involving doubles combined with +, - *, /, and operators as well as parenthesis. The parenthesis does NOT have to be fully balanced. For example: (2*3^2). The fully parenthesized version of this expression would be (2* (32) However, make sure that: Each such expression always has one opening parenthesis and one closing parenthesis. For example, you need to represent as (2+3) not 2+3. Numbers and operators including parenthesis are all separated by a space. Please do not first convert the infix expression into postfix, and then evaluate the postfix. Hints: You need to have two stacks for this problem. One stack is to hold all operators (a stack of strings), and the other is to hold numbers a stack of doubles). Here shows a working algorithm for you reference: 1. While there are still tokens to be read: A. Get the next token. B. If the token is: a) A number: push it onto the value stack. b) A left paren"": push it onto the operator stack. c) A right paren"": 1) While the top element of the operator stack (use peek() not pop()) is not a left paren: Pop the operator from the operator stack. Pop the value stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the value stack. 2) Pop the left parenthesis from the operator stack, and discard it. d) An operator: 1) While the wperator stack is not empty, and the top thing on the operator stack has the same or greater precedence as the token, Pop the operator from the operator stack. Pop the value stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the value stack. 2) Push the token onto the operator stack. 2. At this point the operator stack should be empty, and the value stack should have only one value in it, which is the final result. Pop it and print it to System.out. Outputs: Your output should look something like follows. $ java InfixEvaluator Please enter an arithmetic expression: (2 + 3 * 4^2) The result is: 50.0 package hw2; import java.util.*; public class InfixEvaluator { public double evaluateInfix(String s) { // YOUR CODES return 0; // for compilation. You need to change it. ) public static void main(String[] args) throws Exception { InfixEvaluator infix - new InfixEvaluator(); System.out.print("Please enter an arithmetic expressions: "); Scanner input = new Scanner(System.in); String exp input.nextLine(); input.close(); System.out.println("The result is: " + infix.evaluateInfix(exp)); }