diff options
Cleanup
8 files changed, 0 insertions, 357 deletions
| -rw-r--r-- | Seminar02/README.md | 92 | ||||
| -rw-r--r-- | Seminar02/bonusTask01.cpp | 51 | ||||
| -rw-r--r-- | Seminar02/recursion.cpp | 33 | ||||
| -rw-r--r-- | Seminar02/task01.cpp | 51 | ||||
| -rw-r--r-- | Seminar02/task02.cpp | 24 | ||||
| -rw-r--r-- | Seminar02/task03.cpp | 59 | ||||
| -rw-r--r-- | Seminar02/task04.cpp | 47 | ||||
| -rw-r--r-- | Seminar02/Стек.pdf | bin | 174971 -> 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 Binary files differdeleted file mode 100644 index fdd03a9..0000000 --- a/Seminar02/Стек.pdf +++ /dev/null |
