From 3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Wed, 20 Nov 2024 15:37:03 -0500 Subject: Add Seminar06 --- Seminar06/src/balanced-brackets.cpp | 43 ++++++ Seminar06/src/forward-iterator-bst.hpp | 260 +++++++++++++++++++++++++++++++++ Seminar06/src/test-bst-iter.cpp | 19 +++ 3 files changed, 322 insertions(+) create mode 100644 Seminar06/src/balanced-brackets.cpp create mode 100644 Seminar06/src/forward-iterator-bst.hpp create mode 100644 Seminar06/src/test-bst-iter.cpp (limited to 'Seminar06/src') 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 +#include + +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 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 +#include +#include +#include + +template > +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& other); + Bst& operator=(const Bst& 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 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 +bool Bst::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 +bool Bst::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 +typename Bst::Node** Bst::findMinNode(Node** root) +{ + Node** current = root; + + while ((*current)->left) + { + current = &(*current)->left; + } + return current; +} + +template +bool Bst::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 +size_t Bst::getSize() const +{ + return size; +} + +template +bool Bst::isEmpty() const +{ + return getSize() == 0; +} + +template +typename Bst::Node* Bst::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 +void Bst::free(Node* current) +{ + if (!current) + return; + free(current->left); + free(current->right); + delete current; +} + +template +Bst::Bst(const Bst& other) : comp(other.comp) +{ + root = copy(other.root); + size = other.size; +} + +template +Bst& Bst::operator=(const Bst& other) +{ + if (this != &other) + { + free(root); + root = copy(other.root); + size = other.size; + comp = other.comp; + } + return *this; +} + +template +Bst::~Bst() +{ + free(root); +} + +void treeSort(std::vector& v) +{ + Bst 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 + +int main() +{ + Bst 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 -- cgit v1.3.1-26-gb76a