[SDP/E1] Added work from today's exam

3 files changed, 205 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/Exam 1/ex1.cpp b/Year 2/Structures and data algorithms/Exam 1/ex1.cpp
new file mode 100644
index 0000000..f309dcb
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Exam 1/ex1.cpp
@@ -0,0 +1,94 @@
+#include <iostream>
+
+template <typename T>
+struct Node {
+	T value;
+	Node<T>* next;
+
+	Node(T value, Node<T>* next = nullptr) : value(value), next(next) {}
+};
+
+template <typename T, typename U>
+struct Pair {
+	T left;
+	U right;
+
+	Pair(T left, U right) : left(left), right(right) {}
+};
+
+#define PII Pair<int, int>
+#define NPII Node<Pair<int, int>*>
+
+template <typename T>
+void reverseSublist(Node<T>*& list, int start, int end) {
+	Node<T>* prev = nullptr; // element before first in range
+	Node<T>* iter = list; // first element in range
+	while (start > 0) {
+		prev = iter;
+		iter = iter->next;
+		start--;
+		end--;
+	}
+	Node<T>* eter = iter; // last element in range
+	Node<T>* next = nullptr; // element after last in range
+	for (int i = 0; i < end; i++) {
+		eter = eter->next;
+		next = eter->next;
+	}
+
+	prev->next = eter;
+	Node<T>* last;
+	Node<T>* prevLast;
+	while (end > 0) {
+		prevLast = iter;
+		last = iter->next;
+		for (int i = 1; i < end; i++) {
+			prevLast = prevLast->next;
+			last = last->next;
+		}
+		last->next = prevLast;
+		end--;
+	}
+	prevLast->next = next;
+}
+
+template <typename T>
+void reverseSublists(Node<T>*& list, NPII* intervals) {
+	while (intervals != nullptr) {
+		reverseSublist(list, intervals->value->left, intervals->value->right);
+		intervals = intervals->next;
+	}
+}
+
+template <typename T>
+void print(Node<T>* list) {
+	while (list != nullptr) {
+		std::cout << list->value << " ";
+		list = list->next;
+	}
+	std::cout << std::endl;
+}
+
+int main() {
+	NPII* intervals = new NPII(new PII(1, 3), new NPII(new PII(2, 5), new NPII(new PII(5, 6))));
+	Node<int>* list = new Node<int>(11, new Node<int>(4, new Node<int>(3, new Node<int>(7, new Node<int>(13, new Node<int>(4, new Node<int>(5)))))));
+
+	print(list);
+	reverseSublists(list, intervals);
+	print(list);
+
+	NPII* temp = nullptr;
+	while (intervals != nullptr) {
+		delete intervals->value;
+		temp = intervals->next;
+		delete intervals;
+		intervals = temp;
+	}
+
+	Node<int>* temp1 = nullptr;
+	while (list != nullptr) {
+		temp1 = list->next;
+		delete list;
+		list = temp1;
+	}
+}
diff --git a/Year 2/Structures and data algorithms/Exam 1/ex2.cpp b/Year 2/Structures and data algorithms/Exam 1/ex2.cpp
new file mode 100644
index 0000000..99128d0
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Exam 1/ex2.cpp
@@ -0,0 +1,56 @@
+#include <iostream>
+
+template <typename T>
+struct Node {
+	T value;
+	Node<T>* next;
+
+	Node(T value, Node<T>* next = nullptr) : value(value), next(next) {}
+};
+
+
+bool makeTotal(Node<int>* head) {
+	int len = 0;
+	for (Node<int>* i = head; i != nullptr; i = i->next)
+		len++;
+	if (len < 3) return false;
+
+	Node<int>* prev = head;
+	Node<int>* next = head->next->next;
+	head = head->next;
+	bool balanced = true;
+	while (next != nullptr) {
+		if (prev->value + next->value != head->value) {
+			balanced = false;
+			break;
+		}
+
+		prev = prev->next;
+		head = head->next;
+		next = next->next;
+	}
+
+	if (!balanced) {
+		prev->next = next;
+		delete head;
+		makeTotal(prev);
+	}
+	return balanced;
+}
+
+int main() {
+	// Node<int>* list = new Node<int>(1, new Node<int>(-4, new Node<int>(-5, new Node<int>(-1, new Node<int>(4)))));
+	Node<int>* list = new Node<int>(10, new Node<int>(-5, new Node<int>(-5, new Node<int>(-15, new Node<int>(2)))));
+
+	std::cout << makeTotal(list) << std::endl;
+	for (Node<int>* i = list; i != nullptr; i = i->next)
+		std::cout << i->value << " ";
+	std::cout << std::endl;
+
+	Node<int>* tmp = nullptr;
+	while (list != nullptr) {
+		tmp = list->next;
+		delete list;
+		list = tmp;
+	}
+}
diff --git a/Year 2/Structures and data algorithms/Exam 1/ex3.cpp b/Year 2/Structures and data algorithms/Exam 1/ex3.cpp
new file mode 100644
index 0000000..d1f0a31
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Exam 1/ex3.cpp
@@ -0,0 +1,55 @@
+#include <iostream>
+#include <queue>
+#include <stack>
+#include <string>
+
+bool readAndDelete(std::stack<char>& st, std::string& word) {
+	std::queue<char> backlog;
+	int index = 0;
+	while (!st.empty()) {
+		if (st.top() == word[index])
+			index++;
+		else
+			backlog.push(st.top());
+		st.pop();
+	}
+
+	while (!backlog.empty()) {
+		st.push(backlog.front());
+		backlog.pop();
+	}
+
+	return index == word.length();
+}
+
+void printStack(std::stack<char>& st) {
+	// Знам че принтирането е в обратен ред, бързам!
+	while (!st.empty()) {
+		std::cout << st.top() << std::endl;
+		st.pop();
+	}
+	std::cout << std::endl;
+}
+
+int main() {
+	std::string word1 = "mom";
+	std::stack<char> st1;
+	st1.push('m');
+	st1.push('o');
+	st1.push('o');
+	st1.push('f');
+	st1.push('m');
+	std::cout << readAndDelete(st1, word1) << std::endl;
+	printStack(st1);
+
+
+	std::string word2 = "car";
+	std::stack<char> st2;
+	st2.push('y');
+	st2.push('a');
+	st2.push('d');
+	st2.push('c');
+	st2.push('c');
+	std::cout << readAndDelete(st2, word2) << std::endl;
+	printStack(st2);
+}