# Задачи за стекове 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