add seminar02

1 files changed, 80 insertions, 0 deletions

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, го е премахнало. Тоест то не е първото по - голямо число намиращо се вляво.