COP4530 Project 2: Build a Deque-Based Notation Converter in C++

Understanding the Assignment: Deque and Notation Conversion

In Project 2 for COP4530, you are tasked with implementing a deque (double-ended queue) using a doubly linked list, and then using that deque to build a NotationConverter class that converts between postfix, infix, and prefix notations. This is a classic data structures exercise that tests your understanding of linked lists, stacks, queues, and expression parsing. The assignment forbids using STL containers, so you must build everything from scratch.

Why is this relevant now? In 2026, expression parsing is at the heart of many trending applications. For example, AI code assistants like GitHub Copilot and ChatGPT use similar algorithms to understand and generate code. Even in finance, high-frequency trading systems parse mathematical expressions in real-time. Understanding how to convert between notations is a foundational skill for building interpreters and compilers.

What Is a Deque?

A deque (pronounced “deck”) is a data structure that allows insertion and deletion at both ends. Think of it like a line at a concert where fans can join either at the front or the back, and people can leave from either end. In C++, you will implement a deque using a doubly linked list, where each node has pointers to both the previous and next nodes. This gives you O(1) operations for push_front, push_back, pop_front, and pop_back.

template <typename T>
class Deque {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(const T& value) : data(value), prev(nullptr), next(nullptr) {}
    };
    Node* head;
    Node* tail;
    size_t size;
public:
    Deque() : head(nullptr), tail(nullptr), size(0) {}
    ~Deque();
    void push_front(const T& value);
    void push_back(const T& value);
    void pop_front();
    void pop_back();
    T& front();
    T& back();
    bool empty() const;
    size_t getSize() const;
};

Your deque must be fully functional and used as the only container (besides strings) in your conversion algorithms.

The Three Notations

Arithmetic expressions can be written in three common notations:

Infix: The standard notation where operators are between operands, e.g., ( ( X + B ) * ( Y - D ) ). Parentheses are used to indicate precedence.
Postfix (Reverse Polish): Operators follow their operands, e.g., c d / a b * r r * / *. No parentheses are needed.
Prefix (Polish): Operators precede their operands, e.g., * + A B - C D. Again, no parentheses.

The assignment requires you to implement six conversion methods. However, you can reduce the workload by chaining conversions. For example, to convert postfix to prefix, you can first convert postfix to infix using one method, then infix to prefix using another. This is a smart strategy that reuses code.

Building the NotationConverter Class

Your NotationConverter class will have six public methods, each taking a string and returning a string. The class will use your deque internally. Here is the skeleton:

class NotationConverter {
public:
    std::string postfixToInfix(std::string inStr);
    std::string postfixToPrefix(std::string inStr);
    std::string infixToPrefix(std::string inStr);
    std::string infixToPostfix(std::string inStr);
    std::string prefixToInfix(std::string inStr);
    std::string prefixToPostfix(std::string inStr);
private:
    Deque<std::string> deque;
    // Helper methods for parsing and conversion
};

Notice that the input strings contain spaces between tokens, and parentheses (only in infix) must have spaces on the outside but not inside. Your parsing logic must handle these formatting rules precisely.

Algorithm Overview: Postfix to Infix

Let’s walk through one conversion to illustrate the process. To convert postfix to infix:

Tokenize the input string by spaces into a deque of strings (operands and operators).
Process tokens from left to right using a stack (which you can simulate with your deque using only one end).
When you encounter an operand (a letter), push it onto the stack as a string.
When you encounter an operator, pop the top two operands from the stack, combine them into an infix expression with parentheses: ( operand1 operator operand2 ), and push the result back.
After processing all tokens, the stack should contain a single string, which is the infix expression.

This algorithm uses your deque as a stack (using push_back and pop_back). The same idea works for prefix to infix, but you process tokens from right to left.

Handling Operator Precedence in Infix Conversions

When converting from infix to postfix or prefix, you must respect operator precedence. The standard precedence is: * and / have higher precedence than + and -. Parentheses override precedence. The classic algorithm is the Shunting Yard algorithm by Edsger Dijkstra. It uses a stack for operators and a queue for output. You can implement it using your deque as both the stack and the queue.

For infix to postfix:

Tokenize the input string.
For each token:
- If it’s an operand, push it to the output queue.
- If it’s an operator, pop operators from the stack to the output queue while they have higher or equal precedence, then push the current operator onto the stack.
- If it’s a left parenthesis, push it onto the stack.
- If it’s a right parenthesis, pop operators from the stack to the output queue until a left parenthesis is encountered, then discard both parentheses.
After all tokens, pop any remaining operators from the stack to the output queue.
The output queue now contains the postfix expression.

For infix to prefix, you can reverse the infix string, swap parentheses, apply a modified Shunting Yard, and then reverse the result. Alternatively, use your infix-to-postfix method and then postfix-to-prefix.

Testing Your Implementation

Your converterDriver.cpp should include test cases that cover all six conversions. Use the examples from the assignment description. For instance:

NotationConverter converter;
std::string postfix = "c d / a b * r r * / *";
std::string infix = converter.postfixToInfix(postfix);
// Expected: ( ( c / d ) / ( ( a * b ) / ( r * r ) ) )
std::cout << infix << std::endl;

Make sure your output formatting matches exactly: single spaces between tokens, no extra spaces inside parentheses, and parentheses around every binary operation in infix. The rubric allocates 90 points for test cases and 10 for documentation.

Trend Context: Why This Matters in 2026

Expression parsing is not just an academic exercise. In 2026, AI-powered tools like ChatGPT and Copilot rely on similar algorithms to understand and generate code. For example, when you ask an AI to “add two numbers and multiply by three,” it must parse the infix expression and convert it to an abstract syntax tree. The deque you implement is a versatile container that can act as a stack or queue, making it ideal for these algorithms. In the gaming world, game engines parse mathematical expressions for physics calculations. Even in finance, algorithmic trading systems evaluate expressions in real-time. By mastering this project, you are building skills directly applicable to modern software development.

Final Tips

Start with the deque: Implement and test your doubly linked list deque thoroughly before moving to the converter.
Use helper functions: Write functions to tokenize strings, check if a token is an operator, and determine precedence.
Chain conversions: Implement the most direct conversions first (e.g., postfix to infix, infix to postfix) and then use them to derive the others.
Test edge cases: Single operand expressions, expressions with many parentheses, and expressions with all four operators.
Document your code: The rubric includes 10 points for documentation. Write clear comments explaining the purpose of each method and the logic of your algorithms.

With careful planning and incremental testing, you can successfully complete Project 2 and deepen your understanding of data structures and expression parsing. Good luck!