To get experience working with a stack, and linked lists, I have to code an EvaluateExpression class. Stacks can be used to evaluate an expression, i.e., (1 + 2) * 4 - 3NOTE: You cannot use the Java built in Stack class. You can use another reference implementation of a stack if you wish but you must supply the code and cite the source. YOU MUST implement the stacks using linked lists.

This program will evaluate a compound expression with multiple operators and parentheses. Limit the operators to binary arithmetic operators (+, -, *. /). You will use two linked list implementations of stacks, one for the operands, and one for the operators.Operands and operators are pushed into stacks before they are processed. When an operator is processed, it is popped from the operator stack and applied to the top two elements of the operand stack (two operands are thus popped from the operand stack). The result of the operation is pushed back onto the operand stack.

Phase 1.

The program scans the expression by a user entered string from left to right to extract operands, operators, and the parentheses. Here is your algorithm:

a. If the extracted item is an operand, push it on the operand stack.

b. if the extracted item is a + or - operator, process all the operators at the top of the operator stack, and push the extracted operator to the operator stack.

c. if the extracted item is a * or / operator, process the * or / operators at the top of the operator stack, and push the extracted operator to the operator stack.

d. if the extracted item is a '(' then push it to the operator stack.

e. If the extracted item is a ')', repeatedly process the operators from the top of the operator stack until you see the '(' symbol on the stack.

Phase 2.

Repeatedly process the operators from the top of the operator stack until the operator stack is empty.