Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar06 / src
diff options
context:
space:
mode:
Commit3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-11-20 15:37:03 -0500
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-11-20 15:37:03 -0500
Files551a81327303eb2d8458b1fdf03327aa31a2fa0c /Seminar06/src
Data-structures-and-algorithms-3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69.tar
Data-structures-and-algorithms-3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69.tar.gz
Data-structures-and-algorithms-3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69.zip
Parent98f6872efa0cd02e892ed5d7b836c6929d5c0e10 (diff)
Add Seminar06
3 files changed, 322 insertions, 0 deletions
-rw-r--r--Seminar06/src/balanced-brackets.cpp43
-rw-r--r--Seminar06/src/forward-iterator-bst.hpp260
-rw-r--r--Seminar06/src/test-bst-iter.cpp19
diff --git a/Seminar06/src/balanced-brackets.cpp b/Seminar06/src/balanced-brackets.cpp
new file mode 100644
index 0000000..cce5d01
--- /dev/null
+++ b/Seminar06/src/balanced-brackets.cpp
@@ -0,0 +1,43 @@
+#include <stack>
+#include <string>
+
+bool is_opening_bracket(char ch)
+{
+ return ch == '(' || ch == '{' || ch == '[';
+}
+
+bool is_closing_bracket(char ch)
+{
+ return ch == ')' || ch == ']' || ch == '}';
+}
+
+bool is_corresponding_brackets(char left, char right)
+{
+ return left == '(' && right == ')' || left == '{' && right == '}' || left == '[' && right == ']';
+}
+
+bool balanced_brackets(const std::string& str)
+{
+ std::stack<char> s;
+
+ for (char c : str)
+ {
+ if (is_opening_bracket(c))
+ {
+ s.push(c);
+ }
+ else if (is_closing_bracket(c))
+ {
+ if (s.empty())
+ return false;
+
+ char top = s.top();
+ s.pop();
+
+ if (!is_corresponding_brackets(top, c))
+ return false;
+ }
+ }
+
+ return s.empty();
+} \ No newline at end of file
diff --git a/Seminar06/src/forward-iterator-bst.hpp b/Seminar06/src/forward-iterator-bst.hpp
new file mode 100644
index 0000000..9e3a722
--- /dev/null
+++ b/Seminar06/src/forward-iterator-bst.hpp
@@ -0,0 +1,260 @@
+#pragma once
+#include <iostream>
+#include <functional>
+#include <stack>
+#include <vector>
+
+template <class T, typename Compare = std::less<T>>
+class Bst
+{
+private:
+ struct Node
+ {
+ T data;
+ Node* left;
+ Node* right;
+ Node(const T& data, Node* left = nullptr, Node* right = nullptr) : data(data), left(left), right(right) {}
+ };
+
+ Node* root = nullptr;
+ size_t size = 0;
+ Compare comp; // comparator instance
+
+ Node** findMinNode(Node** root);
+ void free(Node* current);
+ Node* copy(Node* current);
+
+public:
+ Bst() = default;
+ explicit Bst(const Compare& comparator) : comp(comparator) {}
+ Bst(const Bst<T, Compare>& other);
+ Bst<T, Compare>& operator=(const Bst<T, Compare>& other);
+ ~Bst();
+
+ bool insert(const T& data);
+ bool contains(const T& data) const;
+ bool remove(const T& data);
+
+ size_t getSize() const;
+ bool isEmpty() const;
+
+ class ForwardIterator
+ {
+ private:
+ std::stack<Node*> nodeStack;
+
+ void pushLeft(Node* node)
+ {
+ while (node != nullptr)
+ {
+ nodeStack.push(node);
+ node = node->left;
+ }
+ }
+
+ public:
+ ForwardIterator(Node* root = nullptr)
+ {
+ pushLeft(root);
+ }
+
+ T& operator*() const
+ {
+ return nodeStack.top()->data;
+ }
+
+ ForwardIterator& operator++()
+ {
+ Node* right = nodeStack.top()->right;
+ nodeStack.pop();
+ pushLeft(right);
+
+ return *this;
+ }
+ ForwardIterator operator++(int)
+ {
+ ForwardIterator copy(*this);
+ ++(*this);
+ return copy;
+ }
+
+ bool operator!=(const ForwardIterator& other) const
+ {
+ return !(*this == other);
+ }
+
+ bool operator==(const ForwardIterator& other) const
+ {
+ return (other.nodeStack.empty() && nodeStack.empty()) || (nodeStack.size() && other.nodeStack.size() && nodeStack.top() == other.nodeStack.top());
+ }
+ };
+
+ ForwardIterator begin() const
+ {
+ return ForwardIterator(root);
+ }
+
+ ForwardIterator end() const
+ {
+ return ForwardIterator(nullptr);
+ }
+};
+
+template <class T, typename Compare>
+bool Bst<T, Compare>::insert(const T& data)
+{
+ Node** current = &root;
+
+ while (*current)
+ {
+ if (comp(data, (*current)->data))
+ current = &(*current)->left;
+ else if (comp((*current)->data, data))
+ current = &(*current)->right;
+ else
+ return false; // Data already exists
+ }
+ *current = new Node(data);
+ size++;
+ return true;
+}
+
+template <class T, typename Compare>
+bool Bst<T, Compare>::contains(const T& data) const
+{
+ Node* current = root;
+
+ while (current)
+ {
+ if (comp(data, current->data))
+ current = current->left;
+ else if (comp(current->data, data))
+ current = current->right;
+ else
+ return true;
+ }
+ return false;
+}
+
+template <class T, typename Compare>
+typename Bst<T, Compare>::Node** Bst<T, Compare>::findMinNode(Node** root)
+{
+ Node** current = root;
+
+ while ((*current)->left)
+ {
+ current = &(*current)->left;
+ }
+ return current;
+}
+
+template <class T, typename Compare>
+bool Bst<T, Compare>::remove(const T& data)
+{
+ Node** current = &root;
+
+ while (*current)
+ {
+ if (comp(data, (*current)->data))
+ current = &(*current)->left;
+ else if (comp((*current)->data, data))
+ current = &(*current)->right;
+ else
+ break;
+ }
+
+ if (!(*current))
+ return false; // Data not found
+
+ Node* toDelete = *current;
+
+ if (!(*current)->left && !(*current)->right)
+ *current = nullptr; // Node has no children
+ else if (!(*current)->right)
+ *current = (*current)->left; // Node has only left child
+ else if (!(*current)->left)
+ *current = (*current)->right; // Node has only right child
+ else
+ {
+ Node** rightMin = findMinNode(&(*current)->right);
+
+ *current = *rightMin;
+ *rightMin = (*rightMin)->right;
+
+ (*current)->left = toDelete->left;
+ (*current)->right = toDelete->right;
+ }
+ delete toDelete;
+ size--;
+ return true;
+}
+
+template <class T, typename Compare>
+size_t Bst<T, Compare>::getSize() const
+{
+ return size;
+}
+
+template <class T, typename Compare>
+bool Bst<T, Compare>::isEmpty() const
+{
+ return getSize() == 0;
+}
+
+template <class T, typename Compare>
+typename Bst<T, Compare>::Node* Bst<T, Compare>::copy(Node* current)
+{
+ if (!current)
+ return nullptr;
+ Node* res = new Node(current->data);
+ res->left = copy(current->left);
+ res->right = copy(current->right);
+ return res;
+}
+
+template <class T, typename Compare>
+void Bst<T, Compare>::free(Node* current)
+{
+ if (!current)
+ return;
+ free(current->left);
+ free(current->right);
+ delete current;
+}
+
+template <class T, typename Compare>
+Bst<T, Compare>::Bst(const Bst<T, Compare>& other) : comp(other.comp)
+{
+ root = copy(other.root);
+ size = other.size;
+}
+
+template <class T, typename Compare>
+Bst<T, Compare>& Bst<T, Compare>::operator=(const Bst<T, Compare>& other)
+{
+ if (this != &other)
+ {
+ free(root);
+ root = copy(other.root);
+ size = other.size;
+ comp = other.comp;
+ }
+ return *this;
+}
+
+template <class T, typename Compare>
+Bst<T, Compare>::~Bst()
+{
+ free(root);
+}
+
+void treeSort(std::vector<int>& v)
+{
+ Bst<int> bst;
+ for (int i = 0; i < v.size(); i++)
+ bst.insert(v.at(i));
+
+ unsigned index = 0;
+ for (auto it = bst.begin(); it != bst.end(); it++)
+ v.at(index++) = *it;
+} \ No newline at end of file
diff --git a/Seminar06/src/test-bst-iter.cpp b/Seminar06/src/test-bst-iter.cpp
new file mode 100644
index 0000000..c1d6ba4
--- /dev/null
+++ b/Seminar06/src/test-bst-iter.cpp
@@ -0,0 +1,19 @@
+#include "forward-iterator-bst.hpp"
+#include <iostream>
+
+int main()
+{
+ Bst<int> b;
+ b.insert(1);
+ b.insert(2);
+ b.insert(3);
+ b.insert(0);
+ b.insert(4);
+ b.insert(5);
+ b.insert(6);
+
+ for(int x : b)
+ {
+ std::cout << x << " ";
+ }
+} \ No newline at end of file