add seminar02

8 files changed, 273 insertions, 1 deletions

diff --git a/README.md b/README.md
index 4182248..5d9ad8e 100644
--- a/README.md
+++ b/README.md
@@ -1,2 +1,3 @@
 # Код от семинариe по СДП - Компютърни науки
-* Тема 1: Технически преговор - указатели и памет. Дефиниция на структура от данни. Сложност.
\ No newline at end of file
+* Тема 1: Технически преговор - указатели и памет. Дефиниция на структура от данни. Сложност.
+* Тема 2: Стек.
\ No newline at end of file
diff --git a/Seminar02/README.md b/Seminar02/README.md
new file mode 100644
index 0000000..acb20d6
--- /dev/null
+++ b/Seminar02/README.md
@@ -0,0 +1,80 @@
+# Задачи за стекове 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, го е премахнало. Тоест то не е първото по - голямо число намиращо се вляво.
diff --git a/Seminar02/recursion.cpp b/Seminar02/recursion.cpp
new file mode 100644
index 0000000..63f4aa0
--- /dev/null
+++ b/Seminar02/recursion.cpp
@@ -0,0 +1,33 @@
+#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
new file mode 100644
index 0000000..3c98376
--- /dev/null
+++ b/Seminar02/task01.cpp
@@ -0,0 +1,28 @@
+#include<string>
+#include<stack>
+#include<iostream>
+
+std::string removeStars(const std::string& s) {
+        std::stack<char> st;
+        
+        for(char c : s) {
+            if(c == '*')
+                st.pop();
+            else
+                st.push(c);
+        }
+        
+        std::string res(st.size(), '\0');
+        size_t idx = st.size() - 1;
+
+        while(!st.empty()) {
+            res[idx--] = st.top();
+            st.pop();
+        }
+        
+        return res;
+}
+
+int main() {
+
+}
\ No newline at end of file
diff --git a/Seminar02/task02.cpp b/Seminar02/task02.cpp
new file mode 100644
index 0000000..108e1f1
--- /dev/null
+++ b/Seminar02/task02.cpp
@@ -0,0 +1,24 @@
+#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
new file mode 100644
index 0000000..d460551
--- /dev/null
+++ b/Seminar02/task03.cpp
@@ -0,0 +1,59 @@
+#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(c));
+    
+    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
new file mode 100644
index 0000000..91207a0
--- /dev/null
+++ b/Seminar02/task04.cpp
@@ -0,0 +1,47 @@
+#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
new file mode 100644
index 0000000..fdd03a9
--- /dev/null
+++ b/Seminar02/Стек.pdf