This assignment must be completed in Java or Python.

To get experience working with a stack, and linked lists, you will write an EvaluateExpression class. Stacks can be used to evaluate an expression, i.e., (1 + 2) * 4 - 3

NOTE: The spirit behind Assignment 5 is for you to create your own stack class using a linked list implementation, and not to try and get around it by using java/Python library classes with all the defined methods where all you do is to write a class with nothing more than wrapper methods that call the java LinkedList class or Python llist extension module.

I also don't want you to use Python's built-in List data structure which comes bundled with methods to simulate both stack and queue operations.

You cannot use/extend the java LinkedList class, or the java Stack class, and you also cannot use the Python llist or deque class. In other words, I better see a Stack class in your code with the fully written push, pop, peek etc. methods (no wrapper methods). There are many reference implementations out there that you can use as long as you cite the source.

Your 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.

NOTE: In order to get any credit YOU MUST implement the stacks using linked lists.

Operand Stack Expression (1+2) * 4-3 (1+2) 4-3 (1+2) * 4-3 Scan ( 1 Operator Stack ( ( * 1 + 1 + ( (1+2) * 4-3 2 + ( 2 1 3 3 * ). * (1 + 2) 4-3 (1+2) * 4-3 (1+2) 4-3 * ** 4 4 3 (1+2) * 4-3 (1+2) 4-3 3 12 3 12 (1 + 2) * 4-3 None 9