Implement a Deque (Double-Ended Queue) and use that data structure to write a class that can convert between Postfix, Infix, and Prefix notation.

Using these functions:

std::string postfixToInfix(std::string inStr)

std::string postfixToPrefix(std::string inStr)

std::string infixToPostfix(std::string inStr)

std::string infixToPrefix(std::string inStr)

std::string prefixToInfix(std::string inStr)

std::string prefixToPostfix(std::string inStr)

You need to implement a fully functional deque using a doubly linked list. When writing the methods to convert between the notations, you can ONLY use your deque and strings for storing data in the algorithms. You may not use the any C++ Standard Library containers, such as the STL Deque, Stack, Queue, Vector, or List.

Example Output:

White space (one or more characters of space) separate all operand and

operators, while parentheses must have white space on the outside (between operators), and

inside parentheses white space is optional. Parentheses are only used in infix strings.

Parentheses must have operators between them, as all operations must be binary and not

implied.

Hints

It would be a good idea to decode the input string and place it into a deque to make it easier to read for the various methods

In the algorithm header, there is a method that can reverse strings.

When dealing with infix notations, remember that operator precedence is very important.

Remember, a deque can operate like a stack or a queue, queues and stacks can be considered specializations of a deque

You may not need to write a separate algorithm for all six methods. For example, when going from postfix to prefix, you can go from postfix to infix and infix to prefix if those methods are already implemented.

Please explain your code.