Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar02
diff options
context:
space:
mode:
Commit7eee5a78005a9a569186d2c8b4b645a818ab9bf1 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Files84594e0af29cefa5aae76ace5f8eb81484400e31 /Seminar02
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
8 files changed, 0 insertions, 357 deletions
-rw-r--r--Seminar02/README.md92
-rw-r--r--Seminar02/bonusTask01.cpp51
-rw-r--r--Seminar02/recursion.cpp33
-rw-r--r--Seminar02/task01.cpp51
-rw-r--r--Seminar02/task02.cpp24
-rw-r--r--Seminar02/task03.cpp59
-rw-r--r--Seminar02/task04.cpp47
-rw-r--r--Seminar02/Стек.pdfbin174971 -> 0 bytes
diff --git a/Seminar02/README.md b/Seminar02/README.md
deleted file mode 100644
index d1779b2..0000000
--- a/Seminar02/README.md
+++ /dev/null
@@ -1,92 +0,0 @@
-# Задачи за стекове 12.10.22
-
-## Задача първа
-Имаме низ състоящ се от английски букви и символа \*. Всеки път когато видим \* трябва да премахнем символът отляво както и самата звезда.
-Пример:
-* aa\* -> "a"
-* erase\*\*\*\*\* -> ""
-* thi\*s i\*s exampl\*e -> "ths s exampe"
-
-Задачата да се реализира за линейно време с линейна памет.
-## Задача втора
-* Вход: Низ състоящ се от отварящи и затварящи скоби.
-* Изход: Дали скобите в този низ са балансирани
-
-Примери:
-* ((())) -> true
-* ))() -> false
-* )( -> false
-* ()()(()) -> true
-
-## Задача трета
-Обратен полски запис наричаме запис, в който операторите "следват" (са след) числата. Примерно изразът 3 + 4 в обратна полска нотация е 3 4 +. Или изразът 1−2+3 би изглеждал 1 2 −3+. Обикновено първо са дадени числата а след това операциите които извършваме върху тях.
-
-А как би изглеждал израза 1−(2+3). Тук първо трябва да извършим събирането и след това изваждането. Тоест израза се записва като 123+−. Предимството от тази нотация е, че нямаме нужда от скоби, което ускорява сметките. Нашата задача е да напишем функция, която приема валиден стринг в обратна полска нотация и връща пресметнатия резултат.
-
-
-# Монотонни стекове
-Монотонен стек наричаме стек, чиито елементи са монотонно растящи или намаляващи. Монотонните стекове имат приложения върхо много различни и интересни задачи върху масиви.
-
-```cpp
-void monotonicStackExample(const std::vector<int>& v) {
- // Нека v = {4, 1, 2, 6, 7, 3}
- // В стека можем да пазим стойности или индекси в зависимост от задачата.
- // По името може да познаете какво пазим и какъв е типа на стека.
- std::stack<int> minMonotonicValues;
-
- for(int i = 0; i < v.size(); i++) {
- while(!minMonotonicValues.empty() && minMonotonicValues.top() < v[i]) {
- minMonotonicValues.pop();
- }
- minMonotonicValues.push(v[i]);
- }
-
- /*
- В края на for цикъла при индекс i стека изглежда така:
- (върха на стека е най - десния елемент)
- i = 0 : [4]
- i = 1 : [4, 1]
- i = 2 : [4, 2]
- i = 3 : [6]
- i = 4 : [7]
- i = 5 : [7, 3]
- */
-}
-```
-Какво можем да забележим от този пример? Примерно, вярно е, че при i = k максимума на подмасива [0..k - 1] е на дъното на стека.
-
-## Задача четвърта
-Искаме да създадем статична структура от данни построена върху масив, която за константно време по индекс ни връща стойността на първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс.
-
-Пример:
-> [1, 4, 3, 8, 12, 7]
-* getMinLeft(0) -> -1 // няма по - голям елемент от 1 в негово ляво
-* getMinLeft(2) -> 4 // 4 е първия елемент по - голям от arr[2] = 3
-* getMinLeft(5) -> 12 // 12 е първия елемент по - голям от arr[5] = 7
-
-## Обяснение на решението:
-От тази задача можем да си направим извода, че точно преди да вкараме елемента в монотонния стек, върха на стека е първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс.
-
-Защо това е вярно?
-Нека
-
-$$arr = [a_1 \dots a_k \dots a_m \dots a_n]$$
-
-и нека в цикъла i = m. Твърдя, че ако $a_k$ е първото по - голямо число от $a_m$ то ще бъде задължително на върха на стека след приключване на while цикъла.
-
-
-Ако има други числа на върха на стека, то по предположение те са по - малки от $a_m$ и ще бъдат премахнати.
-
-Ами ако $a_k$ не е в стека? Ако то не е в стека то някое по - голямо от него число, намиращо се между $a_k$ и $a_m$, го е премахнало. Тоест то не е първото по - голямо число намиращо се вляво.
-
-## Бонус задачи
-1. Да се сортира стек като използвате само един допълнителен стек.
-
-2. Да се направи задачата със скобите, обаче този път функцията ни казва дали е възможно низът да стане балансиран след най - много едно изтриване на скоба.
-
-Пример:
-* )) -> false
-* ()) -> true
-* () -> true
-* (()()() -> true
-* ())) -> false \ No newline at end of file
diff --git a/Seminar02/bonusTask01.cpp b/Seminar02/bonusTask01.cpp
deleted file mode 100644
index 6e41016..0000000
--- a/Seminar02/bonusTask01.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#include <iostream>
-#include <stack>
-
-void sortStack(std::stack<int> &first)
-{
- std::stack<int> second;
- int currentElement = 0;
- while (!first.empty())
- {
- currentElement = first.top();
- first.pop();
-
- while (!second.empty() && second.top() > currentElement)
- {
- first.push(second.top());
- second.pop();
- }
- second.push(currentElement);
- }
-
- while (!second.empty())
- {
- first.push(second.top());
- second.pop();
- }
-}
-
-void stackPrint(std::stack<int> st)
-{
- while (!st.empty())
- {
- std::cout << st.top() << " ";
- st.pop();
- }
- std::cout << std::endl;
-}
-
-int main()
-{
- std::stack<int> st;
- st.push(8);
- st.push(2);
- st.push(4);
- st.push(1);
- st.push(5);
- st.push(3);
-
- stackPrint(st);
- sortStack(st);
- stackPrint(st);
-} \ No newline at end of file
diff --git a/Seminar02/recursion.cpp b/Seminar02/recursion.cpp
deleted file mode 100644
index 63f4aa0..0000000
--- a/Seminar02/recursion.cpp
+++ /dev/null
@@ -1,33 +0,0 @@
-#include<iostream>
-#include<stack>
-
-int fib(unsigned x) {
- if(x == 0 || x == 1)
- return 1;
-
- return fib(x - 1) + fib(x - 2);
-}
-
-// Малък пример как можем да симулираме рекурсия чрез стек.
-int fibStack(unsigned x) {
- std::stack<unsigned> s;
- s.push(x);
- int result = 0;
-
- while(!s.empty()) {
- int currArg = s.top();
- s.pop();
-
- if(currArg == 1 || currArg == 0)
- ++result; // Еквивалентно на return 1;
- else{
- s.push(currArg - 1); // Еквивалентно на fib(x - 1);
- s.push(currArg - 2); // Еквивалентно на fib(x - 2);
- }
- }
- return result;
-}
-
-int main() {
- std::cout << fib(10) << " " << fibStack(10);
-}
diff --git a/Seminar02/task01.cpp b/Seminar02/task01.cpp
deleted file mode 100644
index 288b3b5..0000000
--- a/Seminar02/task01.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#include<string>
-#include<stack>
-#include<iostream>
-
-std::string removeStars(const std::string& s) {
- std::stack<char> st;
-
- for (int i = 0; i < s.size(); i++) {
- if (s[i] == '*') {
- if (st.empty())
- throw "invalid expr";
- else
- st.pop();
- }
- else
- st.push(s[i]);
- }
-
- std::string res(st.size(), '\0');
- size_t idx = st.size() - 1;
-
- while (!st.empty()) {
- res[idx--] = st.top();
- st.pop();
- }
-
- return res;
-}
-
-std::string removeStarsTwo(const std::string& str) {
- // As we are using only push_back and pop_back here
- // the std::string is equivalent to a stack
- // and we save up some time and memory.
- std::string result;
-
- for(char c : str) {
- if(c == '*') {
- result.pop_back();
- }
- else {
- result.push_back(c);
- }
- }
-
- return result;
-}
-
-
-int main() {
-
-}
diff --git a/Seminar02/task02.cpp b/Seminar02/task02.cpp
deleted file mode 100644
index 108e1f1..0000000
--- a/Seminar02/task02.cpp
+++ /dev/null
@@ -1,24 +0,0 @@
-#include<iostream>
-#include<stack>
-#include<string>
-
-bool isStringBalanced(const std::string& str) {
- std::stack<char> s;
-
- for (size_t i = 0; i < str.size(); i++)
- {
- if(str[i] == ')'){
- if(s.empty())
- return false;
- s.pop();
- }
- else {
- s.push(str[i]);
- }
- }
- return s.empty();
-}
-
-int main() {
- std::cout << isStringBalanced("((()))(((");
-}
diff --git a/Seminar02/task03.cpp b/Seminar02/task03.cpp
deleted file mode 100644
index 1c7a095..0000000
--- a/Seminar02/task03.cpp
+++ /dev/null
@@ -1,59 +0,0 @@
-#include<iostream>
-#include<stack>
-#include<string>
-#include<cassert>
-
-bool isOperation(char c) {
- return (c == '+') || (c == '-') || (c == '*') || (c == '/');
-}
-
-bool isDigit(char c) {
- return c >= '0' && c <= '9';
-}
-
-int eval(int fst, int snd, char op) {
- assert(isOperation(op));
-
- switch (op) {
- case '+':
- return fst + snd;
- case '-':
- return fst - snd;
- case '*':
- return fst * snd;
- case '/':
- return fst / snd;
- }
-}
-
-int RPN(const std::string& str) {
- std::stack<int> numbers;
-
- for (size_t i = 0; i < str.size(); i++) {
- if(isOperation(str[i])) {
- int snd = numbers.top();
- numbers.pop();
-
- int fst = numbers.top();
- numbers.pop();
-
- numbers.push(eval(fst, snd, str[i]));
- }
- else if(str[i] != ' ') {
- int number = 0;
- while(i < str.size() && isDigit(str[i])) {
- number *= 10;
- number += str[i] - '0';
- i++;
- }
- i--;
- numbers.push(number);
- }
- }
-
- return numbers.top();
-}
-
-int main() {
- std::cout << RPN("9 3 4 * - 2 5 * -");
-} \ No newline at end of file
diff --git a/Seminar02/task04.cpp b/Seminar02/task04.cpp
deleted file mode 100644
index 91207a0..0000000
--- a/Seminar02/task04.cpp
+++ /dev/null
@@ -1,47 +0,0 @@
-#include<iostream>
-#include<stack>
-#include<vector>
-
-class firstLeftGreaterElement {
-private:
- std::vector<int> data;
-
- void init(const std::vector<int>& v) {
- std::stack<int> monotonicStack;
-
- data.resize(v.size());
-
- for (size_t i = 0; i < v.size(); i++) {
- while(!monotonicStack.empty() && monotonicStack.top() < v[i]) {
- monotonicStack.pop();
- }
-
- data[i] = monotonicStack.empty() ? -1 : monotonicStack.top();
- monotonicStack.push(v[i]);
- }
- }
-
-public:
- firstLeftGreaterElement(const std::vector<int>& v) {
- init(v);
- }
-
- int getFirstLeftGreaterElement(size_t idx) const {
- return data[idx];
- }
-};
-
-int main() {
- std::vector<int> example {4, 7, 2, 3, 12, 6, 4, 13};
- std::vector<int> example2 {1, 4, 3, 8, 12, 7};
-
- firstLeftGreaterElement f(example);
- firstLeftGreaterElement s(example2);
-
- for (size_t i = 0; i < example.size(); i++)
- std::cout << f.getFirstLeftGreaterElement(i) << " ";
-
- std::cout << std::endl;
-
- std::cout << s.getFirstLeftGreaterElement(0) << " " << s.getFirstLeftGreaterElement(2) << " " << s.getFirstLeftGreaterElement(5);
-} \ No newline at end of file
diff --git a/Seminar02/Стек.pdf b/Seminar02/Стек.pdf
deleted file mode 100644
index fdd03a9..0000000
--- a/Seminar02/Стек.pdf
+++ /dev/null
Binary files differ