[SDP/S06] Solved exercises from seminar 6

2 files changed, 425 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/DoublyLinkedList.hpp b/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/DoublyLinkedList.hpp
new file mode 100644
index 0000000..f1bb01e
--- /dev/null
+++ b/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/DoublyLinkedList.hpp
@@ -0,0 +1,294 @@
+#ifndef DOUBLY_LINKED_LIST_IMPL_
+#define DOUBLY_LINKED_LIST_IMPL_
+
+#include<exception>
+
+template<class T>
+class DoublyLinkedList {
+private:
+    struct DLListNode {
+        T data;
+        DLListNode* next;
+        DLListNode* prev;
+
+        DLListNode(const T& d, DLListNode* n = nullptr, DLListNode* p = nullptr) :
+            data {d},
+            next {n},
+            prev {p} {}
+    };
+
+    using Node = DLListNode;
+
+    Node* head;
+    Node* tail;
+
+    void copy(const DoublyLinkedList<T>& other);
+    void free();
+    
+    class Iterator {
+    private:
+        Node* current;
+        Iterator(Node* c = nullptr) : current { c } {}
+
+    public:
+        Iterator& operator++() {
+            if(current == nullptr) 
+                return *this;
+            current = current->next;
+            return *this;
+        }
+
+        Iterator operator++(int) {
+            if(current == nullptr)
+                return *this;
+            
+            Iterator tmp = *this;
+            current = current->next;
+            return tmp;
+        }
+
+        Iterator& operator--() {
+             if(current == nullptr)
+                return *this;
+            
+            current = current->prev;
+            return *this;
+        }
+
+        Iterator operator--(int) {
+            if(current == nullptr)
+                return *this;
+            
+            Iterator tmp = *this;
+            current = current->prev;
+            return tmp;
+        }
+
+        const T& operator*() {
+            if(current == nullptr)
+                throw std::exception();
+            
+            return current->data;
+        }
+
+        bool operator==(const Iterator& other) const {
+            return current == other.current;
+        }
+
+        bool operator!=(const Iterator& other) const {
+            return !(*this == other);
+        }
+
+        friend class DoublyLinkedList<T>;
+    };
+
+public:
+    DoublyLinkedList();
+
+    DoublyLinkedList(const DoublyLinkedList<T>&);
+    DoublyLinkedList& operator=(const DoublyLinkedList<T>&);
+
+    DoublyLinkedList(DoublyLinkedList<T>&&);
+    DoublyLinkedList& operator=(DoublyLinkedList<T>&&);
+
+    void pushBack(const T&);
+    void popBack();
+
+    void pushFront(const T&);
+    void popFront();
+
+    bool empty() const;
+
+    const T& back() const;
+    const T& front() const;
+
+    Iterator begin();
+    Iterator end();
+
+    void insert(Iterator at, const T& elem);
+
+    ~DoublyLinkedList();
+};
+
+template<class T>
+DoublyLinkedList<T>::DoublyLinkedList() : head { nullptr }, tail { nullptr } {}
+
+template<class T>
+DoublyLinkedList<T>::DoublyLinkedList(const DoublyLinkedList<T>& other) : head {nullptr}, tail {nullptr} {
+    copy(other);
+}
+
+template<class T>
+DoublyLinkedList<T>& DoublyLinkedList<T>::operator=(const DoublyLinkedList<T>& other) {
+    if(this != &other) {
+        free();
+        copy(other);
+    }
+    return *this;
+}
+
+template<class T>
+DoublyLinkedList<T>::DoublyLinkedList(DoublyLinkedList<T>&& other) {
+    head = other.head;
+    tail = other.tail;
+
+    other.head = other.tail = nullptr;
+}
+
+template<class T>
+DoublyLinkedList<T>& DoublyLinkedList<T>::operator=(DoublyLinkedList<T>&& other) {
+    if(this != &other) {
+        free();
+
+        head = other.head;
+        tail = other.tail;
+
+        other.head = other.tail = nullptr;
+    }
+    return *this;
+}
+
+template<class T>
+void DoublyLinkedList<T>::copy(const DoublyLinkedList<T>& other) {
+    Node* iter = other.head;
+
+    while(iter) {
+        pushBack(iter->data);
+        iter = iter->next;
+    }
+}
+
+template<class T>
+void DoublyLinkedList<T>::free() {
+    while(head) {
+        Node* toDelete = head;
+        head = head->next;
+        delete toDelete;
+    }
+}
+
+template<class T>
+bool DoublyLinkedList<T>::empty() const {
+    return head == nullptr;
+}
+
+template<class T>
+void DoublyLinkedList<T>::pushBack(const T& elem) {
+    Node* toInsert = new Node(elem);
+
+    if(empty()) {
+        head = tail = toInsert;
+    }
+    else {
+        toInsert->prev = tail;
+        tail->next = toInsert;
+        tail = toInsert;
+    }
+}
+
+template<class T>
+void DoublyLinkedList<T>::pushFront(const T& elem) {
+    Node* toInsert = new Node(elem);
+
+    if(empty()) {
+        head = tail = toInsert;
+    }
+    else {
+        toInsert->next = head;
+        head->prev = toInsert;
+        head = toInsert;
+    }
+}
+
+template<class T>
+void DoublyLinkedList<T>::popBack() {
+    if(empty())
+        throw std::exception();
+    
+    if(tail == head) {
+        delete head;
+        tail = head = nullptr;
+        return;
+    }
+
+    tail->prev->next = nullptr;
+
+    Node* toDelete = tail;
+    tail = tail->prev;
+    delete toDelete;
+}
+
+
+template<class T>
+void DoublyLinkedList<T>::popFront() {
+    if(empty())
+        throw std::exception();
+    
+    Node* toDelete = head;
+
+    if(head == tail) {
+        delete toDelete;
+        head = tail = nullptr;
+        return;
+    }
+
+    head->next->prev = nullptr;
+    head = head->next;
+    delete toDelete;
+}
+
+template<class T>
+typename DoublyLinkedList<T>::Iterator DoublyLinkedList<T>::begin() {
+    return Iterator(head);
+}
+
+template<class T>
+typename DoublyLinkedList<T>::Iterator DoublyLinkedList<T>::end() {
+    return Iterator(nullptr);
+}
+
+template<class T>
+void DoublyLinkedList<T>::insert(Iterator at, const T& elem) {
+    // Ако е nullptr предполагам, че са подали .end() и добавям в края
+    if(at.current == nullptr) {
+        tail->next = new Node(elem, nullptr, tail);
+        tail = tail->next;
+        return;
+    }
+
+    Node* toInsert = new Node(elem, at.current, at.current->prev);
+    
+    if(at.current->prev != nullptr)
+        at.current->prev->next = toInsert;
+    
+    at.current->prev = toInsert;
+
+    if(at.current == head)
+        head = toInsert;
+    
+    if(at.current == tail)
+        tail = toInsert;
+
+    at.current = toInsert;
+}
+
+template<class T>
+const T& DoublyLinkedList<T>::back() const {
+    if(empty())
+        throw std::exception();
+    
+    return tail->data;
+}
+
+template<class T>
+const T& DoublyLinkedList<T>::front() const {
+    if(empty())
+        throw std::exception();
+    
+    return head->data;
+}
+
+template<class T>
+DoublyLinkedList<T>::~DoublyLinkedList(){ free(); }
+
+#endif
\ No newline at end of file
diff --git a/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/exercises.cpp b/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/exercises.cpp
new file mode 100644
index 0000000..1981501
--- /dev/null
+++ b/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/exercises.cpp
@@ -0,0 +1,131 @@
+#include <list>
+#include <iostream>
+#include <queue>
+#include "DoublyLinkedList.hpp"
+
+// Ex1
+
+template<class T>
+void insertSorted(std::list<T>& ll, const T& elem) {
+	auto iter = ll.cbegin();
+	while (*iter < elem)
+		++iter;
+	ll.insert(iter, elem);
+}
+
+void ex1() {
+	std::list<int> l;
+	l.push_back(1);
+	l.push_back(2);
+	l.push_back(4);
+	l.push_back(5);
+
+	for (int n : l) std::cout << n << " ";
+	std::cout << std::endl;
+	insertSorted(l, 3);
+	for (int n : l) std::cout << n << " ";
+	std::cout << std::endl;
+}
+
+// Ex2
+
+void print(DoublyLinkedList<std::queue<int>*>& dll) {
+	for (std::queue<int>* val : dll)
+		std::cout << val->front() << " ";
+	std::cout << std::endl;
+}
+
+int operate(int a, int b, char op) {
+	switch(op) {
+		case '+': return a + b;
+		case '-': return a - b;
+		case '*': return a * b;
+		case '/': return a / b;
+		default: return 0;
+	}
+}
+
+int evaluateRPQueue(std::queue<int>& eq) {
+	int accum = eq.front() - '0';
+	eq.pop();
+	char buf;
+	while (!eq.empty()) {
+		buf = eq.front();
+		eq.pop();
+		accum = operate(accum, buf - '0', eq.front());
+		eq.pop();
+	}
+	return accum;
+}
+
+void evaluateQueues(DoublyLinkedList<std::queue<int>*>& dll) {
+	for (std::queue<int>* eq : dll) {
+		eq->push(evaluateRPQueue(*eq));
+	}
+}
+
+template <class T>
+bool isSymmetricBad(DoublyLinkedList<std::queue<T>*> dll) {
+	while (!dll.empty()) {
+		if (dll.back()->front() != dll.front()->front())
+			return false;
+		dll.popBack();
+		if (dll.empty()) return true;
+		dll.popFront();
+	}
+	return true;
+}
+
+template <class T>
+bool isSymmetric(DoublyLinkedList<std::queue<T>*>& dll) {
+	auto frontIter = dll.begin();
+	auto backIter = --dll.end();
+
+	while (frontIter != backIter) {
+		if ((*frontIter)->front() != (*backIter)->front())
+			return false;
+		++frontIter;
+		if (frontIter == backIter) return true;
+		--backIter;
+	}
+	return true;
+}
+
+void ex2() {
+	DoublyLinkedList<std::queue<int>*> dll;
+	dll.pushBack(new std::queue<int>());
+	dll.back()->push('4');
+	dll.back()->push('5');
+	dll.back()->push('+');
+	dll.pushBack(new std::queue<int>());
+	dll.back()->push('1');
+	dll.back()->push('6');
+	dll.back()->push('+');
+	dll.back()->push('7');
+	dll.back()->push('*');
+	dll.pushBack(new std::queue<int>());
+	dll.back()->push('8');
+	dll.pushBack(new std::queue<int>());
+	dll.back()->push('1');
+	dll.back()->push('7');
+	dll.back()->push('*');
+	dll.back()->push('7');
+	dll.back()->push('*');
+	dll.pushBack(new std::queue<int>());
+	dll.back()->push('2');
+	dll.back()->push('3');
+	dll.back()->push('*');
+	dll.back()->push('3');
+	dll.back()->push('+');
+
+	print(dll);
+
+	evaluateQueues(dll);
+	print(dll);
+
+	std::cout << isSymmetric(dll) << std::endl;
+}
+
+int main() {
+	ex2();
+}