Reverse Iterators Implementation

Reverse iterators are specialized iterator adapters that traversee a container in the opposite direction. They are implemented as template classes that wrap existing iterators, providing a reverse traversal interface while maintaining compatibility with standard algorithms.

A key aspect of reverse iterator implementation is the operator* method, which returns a reference to the element preceding the current iterator position. This design ensures symmetry between the rbegin() and rend() methods.

Iterator Implementation

#pragma once

template<typename iterator="" pointer="" reference="" typename="">
struct BidirectionalReverseIterator
{
    typedef BidirectionalReverseIterator<iterator pointer="" reference=""> SelfType;

    BidirectionalReverseIterator(Iterator pos)
        : current(pos)
    {}

    Reference operator*()
    {
        Iterator temp = current;
        --temp;
        return *temp;
    }

    SelfType& operator++()
    {
        --current;
        return *this;
    }

    SelfType& operator--()
    {
        ++current;
        return *this;
    }

    bool operator!=(const SelfType& other) const
    {
        return current != other.current;
    }

    bool operator==(const SelfType& other) const
    {
        return current == other.current;
    }

    Iterator current;
};
</iterator></typename>

Container Integration

#pragma once
#include<assert.h>
#include"Iterator.h"

namespace mylib
{
    template<typename t="">
    struct Node
    {
        T value;
        Node<t>* next;
        Node<t>* prev;

        Node(const T& data = T())
            : value(data)
            , next(nullptr)
            , prev(nullptr)
        {}
    };

    template<typename pointer="" reference="" t="" typename="">
    struct ContainerIterator
    {
        typedef Node<t> NodeType;
        typedef ContainerIterator<t pointer="" reference=""> Self;
        NodeType* node_ptr;
        
        ContainerIterator(NodeType* ptr)
            : node_ptr(ptr)
        {}

        Reference operator*()
        {
            return node_ptr->value;
        }

        Pointer operator->()
        {
            return &node_ptr->value;
        }

        Self& operator++()
        {
            node_ptr = node_ptr->next;
            return *this;
        }

        Self& operator--()
        {
            node_ptr = node_ptr->prev;
            return *this;
        }

        Self operator++(int)
        {
            Self temp(*this);
            node_ptr = node_ptr->next;
            return temp;
        }

        Self operator--(int)
        {
            Self temp(*this);
            node_ptr = node_ptr->prev;
            return temp;
        }

        bool operator!=(const Self& other) const
        {
            return node_ptr != other.node_ptr;
        }

        bool operator==(const Self& other) const
        {
            return node_ptr == other.node_ptr;
        }
    };

    template<typename t="">
    class DoublyLinkedList
    {
        typedef Node<t> Node;
    public:
        typedef ContainerIterator<t t=""> iterator;
        typedef ContainerIterator<t const="" t=""> const_iterator;
        typedef BidirectionalReverseIterator<iterator t=""> reverse_iterator;
        typedef BidirectionalReverseIterator<const_iterator const="" t=""> const_reverse_iterator;

        reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }

        reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }

        const_reverse_iterator rbegin() const
        {
            return const_reverse_iterator(end());
        }

        const_reverse_iterator rend() const
        {
            return const_reverse_iterator(begin());
        }

        iterator begin()
        {
            return head->next;
        }

        iterator end()
        {
            return head;
        }

        const_iterator begin() const
        {
            return head->next;
        }

        const_iterator end() const
        {
            return head;
        }

        void initialize_empty()
        {
            head = new Node;
            head->next = head;
            head->prev = head;
            count = 0;
        }

        DoublyLinkedList()
        {
            initialize_empty();
        }

        DoublyLinkedList(std::initializer_list<t> init_list)
        {
            initialize_empty();
            for (const auto& item : init_list)
            {
                push_back(item);
            }
        }

        DoublyLinkedList(const DoublyLinkedList<t>& other)
        {
            initialize_empty();
            for (const auto& item : other)
            {
                push_back(item);
            }
        }

        DoublyLinkedList<t>& operator=(DoublyLinkedList<t> temp_list)
        {
            swap(temp_list);
            return *this;
        }

        ~DoublyLinkedList()
        {
            clear();
            delete head;
            head = nullptr;
        }

        void clear()
        {
            auto current = begin();
            while (current != end())
            {
                current = erase(current);
            }
        }

        void swap(DoublyLinkedList<t>& other)
        {
            std::swap(head, other.head);
            std::swap(count, other.count);
        }

        void push_back(const T& item)
        {
            insert(end(), item);
        }

        void push_front(const T& item)
        {
            insert(begin(), item);
        }

        iterator insert(iterator position, const T& item)
        {
            Node* current_node = position.node_ptr;
            Node* previous_node = current_node->prev;
            Node* new_node = new Node(item);

            new_node->next = current_node;
            current_node->prev = new_node;
            new_node->prev = previous_node;
            previous_node->next = new_node;
            ++count;
            return new_node;
        }

        void pop_back()
        {
            erase(--end());
        }

        void pop_front()
        {
            erase(begin());
        }

        iterator erase(iterator position)
        {
            assert(position != end());

            Node* previous_node = position.node_ptr->prev;
            Node* next_node = position.node_ptr->next;
            previous_node->next = next_node;
            next_node->prev = previous_node;
            --count;
            return next_node;
        }

        size_t size() const
        {
            return count;
        }

        bool empty() const
        {
            return count == 0;
        }

    private:
        Node* head;
        size_t count;
    };
}
</t></t></t></t></t></const_iterator></iterator></t></t></t></typename></t></t></typename></t></t></typename></assert.h>

Testing Implementation

#include<iostream>
#include<algorithm>
#include<list>
#include<vector>
using namespace std;
#include"DoublyLinkedList.h"

void test_reverse_iteration()
{
    mylib::DoublyLinkedList<int> lst;
    lst.push_back(1);
    lst.push_back(20);
    lst.push_back(3);
    lst.push_back(5);
    lst.push_back(5);
    lst.push_back(4);
    lst.push_back(5);
    lst.push_back(6);
    
    cout << "Forward iteration: ";
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    cout << "Reverse iteration: ";
    for (auto it = lst.rbegin(); it != lst.rend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main()
{
    test_reverse_iteration();
    return 0;
}
</int></vector></list></algorithm></iostream>

Expression Evaluation Using Stacks

Stack are fundamental data structures for evaluating mathematical expressions, particularly in the context of Reverse Polish Notation (RPN) and infix-to-postfix conversions.

Evaluating Reverse Polish Notation

Reverse Polish Notation (RPN) is a mathematical notation where operators follow their operands. This eliminates the need for parentheses and makes evaluation straightforward using a stack-based approach.

The algorithm processes each token in sequence:

1. If the token is an operand, push it onto the stack
2. If the token is an operator, pop the top two operands, apply the operation, and push the result back
3. After processing all tokens, the stack contains the final result

RPN Evaluator Implementation

#include<vector>
#include<stack>
#include<string>
#include<stdexcept>

class ExpressionEvaluator {
public:
    int evaluateRPN(const vector<string>& tokens) {
        stack<int> value_stack;

        for (const string& token : tokens) {
            if (isOperator(token)) {
                if (value_stack.size() < 2) {
                    throw invalid_argument("Insufficient operands for operator");
                }
                
                int operand2 = value_stack.top();
                value_stack.pop();
                int operand1 = value_stack.top();
                value_stack.pop();
                
                int result = performOperation(operand1, operand2, token);
                value_stack.push(result);
            } else {
                value_stack.push(stoi(token));
            }
        }
        
        if (value_stack.size() != 1) {
            throw invalid_argument("Invalid expression format");
        }
        
        return value_stack.top();
    }

private:
    bool isOperator(const string& token) const {
        return token == "+" || token == "-" || token == "*" || token == "/";
    }

    int performOperation(int operand1, int operand2, const string& op) const {
        if (op == "+") return operand1 + operand2;
        if (op == "-") return operand1 - operand2;
        if (op == "*") return operand1 * operand2;
        if (op == "/") {
            if (operand2 == 0) {
                throw runtime_error("Division by zero");
            }
            return operand1 / operand2;
        }
        throw invalid_argument("Unknown operator");
    }
};
</int></string></stdexcept></string></stack></vector>

Infix to Postfix Conversion

Converting infix expressions to postfix notation involves handling operator precedence and parentheses. The algorithm uses a stack to manage operators and output operands directly.

The key steps are:

1. Proces each token in the infix expression
2. For operands, add them directly to the output
3. For operators, push them onto the stack after handling higher precedence operators
4. For opening parentheses, push them onto the stack
5. For closing parentheses, pop operators until an opening parenthesis is found
6. After processing all tokens, pop any remaining operators from the stack

Expression Converter Implementation

#include<vector>
#include<stack>
#include<string>
#include<cctype>

class ExpressionConverter {
public:
    vector<string> infixToPostfix(const string& infix_expr) {
        vector<string> postfix_tokens;
        stack<char> operator_stack;
        size_t index = 0;

        while (index < infix_expr.length()) {
            char current_char = infix_expr[index];

            if (isspace(current_char)) {
                index++;
                continue;
            }

            if (isdigit(current_char)) {
                string number;
                while (index < infix_expr.length() && isdigit(infix_expr[index])) {
                    number += infix_expr[index];
                    index++;
                }
                postfix_tokens.push_back(number);
            } else if (current_char == '(') {
                operator_stack.push(current_char);
                index++;
            } else if (current_char == ')') {
                while (!operator_stack.empty() && operator_stack.top() != '(') {
                    postfix_tokens.push_back(string(1, operator_stack.top()));
                    operator_stack.pop();
                }
                
                if (operator_stack.empty()) {
                    throw invalid_argument("Mismatched parentheses");
                }
                
                operator_stack.pop(); // Remove the '('
                index++;
            } else {
                // Handle negative numbers
                if (current_char == '-' && (index == 0 || !isdigit(infix_expr[index-1]) && infix_expr[index-1] != ')')) {
                    string number = "0";
                    index++;
                    while (index < infix_expr.length() && isdigit(infix_expr[index])) {
                        number += infix_expr[index];
                        index++;
                    }
                    postfix_tokens.push_back(number);
                    continue;
                }
                
                while (!operator_stack.empty() && getPrecedence(operator_stack.top()) >= getPrecedence(current_char)) {
                    postfix_tokens.push_back(string(1, operator_stack.top()));
                    operator_stack.pop();
                }
                
                operator_stack.push(current_char);
                index++;
            }
        }

        while (!operator_stack.empty()) {
            if (operator_stack.top() == '(') {
                throw invalid_argument("Mismatched parentheses");
            }
            postfix_tokens.push_back(string(1, operator_stack.top()));
            operator_stack.pop();
        }

        return postfix_tokens;
    }

private:
    int getPrecedence(char op) const {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0; // For parentheses
    }
};
</char></string></string></cctype></string></stack></vector>

Complete Expression Calculator

#include<string>
#include<vector>

class Calculator {
public:
    int calculate(const string& expression) {
        ExpressionConverter converter;
        ExpressionEvaluator evaluator;
        
        string normalized_expr = normalizeExpression(expression);
        vector<string> postfix_tokens = converter.infixToPostfix(normalized_expr);
        return evaluator.evaluateRPN(postfix_tokens);
    }

private:
    string normalizeExpression(const string& expr) {
        string normalized;
        for (char c : expr) {
            if (!isspace(c)) {
                normalized += c;
            }
        }
        return normalized;
    }
};
</string></vector></string>