add Seminar06

7 files changed, 344 insertions, 0 deletions

diff --git a/Seminar06/DLLSkeleton.cpp b/Seminar06/DLLSkeleton.cpp
new file mode 100644
index 0000000..77811b8
--- /dev/null
+++ b/Seminar06/DLLSkeleton.cpp
@@ -0,0 +1,70 @@
+#ifndef DOUBLY_LINKED_LIST_IMPL_
+#define DOUBLY_LINKED_LIST_IMPL_
+
+#include<exception>
+
+template<class T>
+class DoublyLinkedList {
+private:
+    struct DLListNode {};
+
+    using Node = DLListNode;
+
+    Node* head;
+    Node* tail;
+
+    void copy(const DoublyLinkedList<T>& other);
+    void free();
+    
+    class Iterator {
+    private:
+        Node* current;
+        Iterator(Node* c) {}
+
+    public:
+        Iterator& operator++() {}
+
+        Iterator operator++(int) {}
+
+        Iterator& operator--() {}
+
+        Iterator operator--(int) {}
+
+        const T& operator*() {}
+
+        bool operator==(const Iterator& other) const {}
+
+        bool operator!=(const Iterator& other) const {}
+
+        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();
+};
+
+#endif
\ No newline at end of file
diff --git a/Seminar06/Linked-List-Perm.cpp b/Seminar06/Linked-List-Perm.cpp
new file mode 100644
index 0000000..ee2b1e4
--- /dev/null
+++ b/Seminar06/Linked-List-Perm.cpp
@@ -0,0 +1,28 @@
+#include"../Seminar04/linked-list-utils.h"
+
+bool isLinkedListPermRec(const LinkedListNode<int>*& begin, const LinkedListNode<int>* end) {
+    if(end == nullptr)
+        return true;
+
+    bool res = isLinkedListPermRec(begin, end->next) && (begin->data == end->data);
+
+    begin = begin->next;
+    return res;
+}
+
+template<class T>
+bool isLinkedListPerm(const LinkedListNode<T>* ll) {
+    if(ll == nullptr)
+        return true;
+    
+    const LinkedListNode<int>* begin = ll;
+    const LinkedListNode<int>* end = ll;
+    
+    return isLinkedListPermRec(begin, end);
+}
+
+int main() {
+    LinkedListNode<int>* ll = new LinkedListNode(0, new LinkedListNode(1, new LinkedListNode(1)));
+
+    std::cout << isLinkedListPerm(ll);
+}
\ No newline at end of file
diff --git a/Seminar06/README.md b/Seminar06/README.md
new file mode 100644
index 0000000..deb6873
--- /dev/null
+++ b/Seminar06/README.md
@@ -0,0 +1,73 @@
+# Двойно свързани списъци. Допълнителни задачи върху списъци.
+
+При едносвързания списък свързаните компоненти пазеха указател към следващия елемент. Ситуацията при двойно свързаните списъци е подобна - отново имаме указател към следващия елемент, но вече имаме и един допълнителен указател към предишния.
+
+![](media/dll.png)
+
+Когато представяме двусвързания списък като указател към началото и указател към края сложност на операциите му са:
+* Добавяне на елемент на произволна позиция: O(n)
+* Добавяне на елемент в началото/края O(1)
+* Премахване на елемент от произволна позиция: O(n)
+* Премахване на елемент от началото / **края**: O(1)
+* Обхождане: O(n)
+Тук вече премахването на елемент от края на списъка е O(1) (Защо?)
+
+Елемента на двойно свързания списък би изглеждал по следния начин:
+```cpp
+template<class T>
+struct DLListElement {
+    T data;
+    DLListElement<T>* prev;
+    DLListElement<T>* next;
+}
+```
+
+## Задача първа
+Да се напише функция
+```cpp
+template<class T>
+void insertSorted(std::list<T>& ll, const T& elem);
+```
+която приема сортиран свързан списък и добавя *elem* на правилното място.
+
+## Задача втора
+Нека имаме двусвързан списък от опашки и символи. Във всяка опашка от налачото към края е записан валиден израз в обратна полска нотация. Операторите са [+, -, *, /] а операндите за улеснение са **едноцифрени числа**.
+
+Да се напише функция, която приема такъв списък, изчислява стойността на всички опашки, и връща дали списъка от резултатите е симетричен спрямо средата.
+
+Пример:
+
+```
+      *           *     +   
+      |           |     |   
+      7           *     3    
+      |           |     |   
++     +           7     *    
+|     |           |     |    
+5     6           7     3    
+|     |           |     |    
+4     1     8     1     2    
+|     |     |     |     |    
+* <-> * <-> * <-> * <-> * 
+```
+Изход: 1
+
+Примера ще се оцени до 9 <-> 49 <-> 8 <-> 49 <-> 9, който е симетричен списък.
+
+## Задача трета - Linked List Cycyle
+Да се напише функция, която проверява дали в едносвързан списък има цикъл.
+
+## Задача четвърта
+Да се провери дали едносвързан списък е пермутация.
+
+Пример:
+
+Вход:
+``` 1 -> 2 -> 3 -> 2 -> 1 ```
+
+Изход: true
+
+Вход:
+``` 1 -> 2 -> 3 ```
+
+Изход: false
\ No newline at end of file
diff --git a/Seminar06/insertSorted.cpp b/Seminar06/insertSorted.cpp
new file mode 100644
index 0000000..5bed694
--- /dev/null
+++ b/Seminar06/insertSorted.cpp
@@ -0,0 +1,30 @@
+#include<iostream>
+#include<list>
+#include<algorithm>
+
+template<class T>
+void insertSorted(std::list<T>& ll, const T& elem) {
+    auto iter = ll.begin();
+
+    while(iter != ll.end()) {
+        if(*iter > elem) {
+            ll.insert(iter, elem);
+            break;
+        }
+        ++iter;
+    }
+
+    if(iter == ll.end())
+        ll.push_back(elem);
+}
+
+int main() {
+    std::list<int> ll;
+
+    srand(time(NULL));
+
+    for (size_t i = 0; i < 55555; i++)
+        insertSorted(ll, rand());
+
+    std::cout << std::is_sorted(ll.begin(), ll.end());
+}
\ No newline at end of file
diff --git a/Seminar06/linkedListCycle.cpp b/Seminar06/linkedListCycle.cpp
new file mode 100644
index 0000000..4aa33c6
--- /dev/null
+++ b/Seminar06/linkedListCycle.cpp
@@ -0,0 +1,33 @@
+#include"../Seminar04/linked-list-utils.h"
+
+bool hasCycle(LinkedListNode<int>* head) {
+    LinkedListNode<int> *fast = head;
+    LinkedListNode<int> *slow = head;
+
+    while (fast && fast->next && slow) {
+        fast = (fast->next)->next;
+        slow = slow->next;
+
+        if (fast == slow)
+            return true;
+    }
+
+    return false;
+}
+
+int main() {
+    using Node = LinkedListNode<int>;
+
+    Node* last = new Node(6);
+
+    Node* list = new Node(1,
+    new Node(2,
+    new Node(3,
+    new Node(4,
+    new Node(5,  
+    last)))));
+
+    last->next = list->next->next;
+
+    hasCycle(list);
+}
\ No newline at end of file
diff --git a/Seminar06/media/dll.png b/Seminar06/media/dll.png
new file mode 100644
index 0000000..03b98d7
--- /dev/null
+++ b/Seminar06/media/dll.png
diff --git a/Seminar06/task02.cpp b/Seminar06/task02.cpp
new file mode 100644
index 0000000..5f8bf92
--- /dev/null
+++ b/Seminar06/task02.cpp
@@ -0,0 +1,110 @@
+#include<list>
+#include<iostream>
+#include<queue>
+#include<stack>
+
+bool isSymethric(const std::list<int>& ll) {
+    auto start = ll.begin();
+    auto end = --(ll.end());
+
+    while(start != end) {
+        if(*start != *end)
+            return false;
+        
+        ++start;
+        if(start == end)
+            break;
+        --end;
+    }
+
+    return true;
+}
+
+int evaluateExpr(char op, int fst, int snd) {
+    // assert(isOperator(op));
+    
+    switch (op) {
+        case '+':
+            return (fst + snd);
+        break;
+         case '-':
+            return (fst - snd);
+        break;
+         case '*':
+            return (fst * snd);
+        break;
+         case '/':
+            return (snd / fst);
+        break;
+    }
+}
+
+size_t evaluateQueue(std::queue<char> q) {
+    std::stack<int> nums;
+
+    while(!q.empty()) {
+        if(isdigit(q.front())) {
+            int cDigit = q.front() - '0';
+            q.pop();
+            nums.push(cDigit);
+        }
+        else {
+            int fst = nums.top();
+            nums.pop();
+            int snd = nums.top();
+            nums.pop();
+            char op = q.front();
+            q.pop();
+
+            nums.push(evaluateExpr(op, fst, snd));
+        }
+    }
+    return nums.top();
+}
+
+bool solution(const std::list<std::queue<char>>& ll) {
+    std::list<int> l;
+
+    for(auto elem : ll)
+        l.push_back(evaluateQueue(elem));
+    
+    return isSymethric(l);
+}
+
+int main() {
+    std::list<std::queue<char>> test(5);
+
+    auto it = test.begin();
+    (*it).push('4');
+    (*it).push('5');
+    (*it).push('+');
+
+    ++it;
+
+    (*it).push('1');
+    (*it).push('6');
+    (*it).push('+');
+    (*it).push('7');
+    (*it).push('*');
+    ++it;
+
+    (*it).push('8');
+    ++it;
+
+    (*it).push('1');
+    (*it).push('7');
+    (*it).push('7');
+    (*it).push('*');
+    (*it).push('*');
+
+    ++it;
+
+    (*it).push('2');
+    (*it).push('3');
+    (*it).push('*');
+    (*it).push('3');
+    (*it).push('+');
+
+
+    std::cout << solution(test);
+}
\ No newline at end of file