Step $1$ Doubly Linked List Class

From the lecture material create a doubly linked list class. This class should be generic so that it will operate on any given type.

Your class should have the ability to add to the front, add to the rear, insert $($you can insert before or after a node$),$ delete, and find. Your list class should also implement functionality that will allow you traverse the list forward and backward.

As for the naming conventions and interface into the list I will leave all of that up to you.

Step $2$ Stack and Queue

Using the linked list class you created in Step $1$ create stack and queue classes. I will leave it up to you as to whether to use composition or inheritance but whatever way you choose to go you should be able to explain why you chose the relationship type you did.

The stack class should have the following interface

push

pop

peek

The queue should have the following interface

enqueue

dequeue

peek

Again I will leave it up to you as to the parameters to the functions and the return type. As usual please have good reasoning for why you have been doing things.

Step $3$ The RPN Calculator

By now you should have a working stack and queue. Use the Stack to create an RPN calculator. You will have to make a decision whether you want to use inheritance or simple composition to make the RPN calculator work. You will also have to make a decision as to what the interface into the RPN calculator is$.$

One of the things that needs to be considered is parsing the input. We know that an RPN calculator will operate on an expression like so:

$325*+$

but what happens if someone puts more that one space in between each token of the input? You will need to handle something things like:

$325*+$

What you should do is allow the interface to take a string type and then parse the tokens out of the string.

Step $4$ Infix Notation Calculator

Infix notation is an expression like this:

$3+2*5$

In this step you are to create a calculator that allows for expression like the above. Your calculator should support $+,-,*,/.$ This is an extremely difficult thing to solve because we need to consider the operator precedence. Probably the best way to solve the problem is to convert the infix to postfix $($RPN$).$ You may be wondering how to convert from infix to postfix.

Extra Credit

If you would like an extra $10$ points or simply be able to have bragging rights try adding functions like sine$,$ cosine, and tan to your calculator. You could do something like this:

$3*2+$ sine$(45)$

This problem is probably bigger than anything that you have worked on to this point. It is important that you learn good organizational skills. Anything you discover about organization you should share with your fellow students via the discussion

In c$++$ please and thank you!