Задачи за стекове 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+−. Предимството от тази нотация е, че нямаме нужда от скоби, което ускорява сметките. Нашата задача е да напишем функция, която приема валиден стринг в обратна полска нотация и връща пресметнатия резултат.

Монотонни стекове

Монотонен стек наричаме стек, чиито елементи са монотонно растящи или намаляващи. Монотонните стекове имат приложения върхо много различни и интересни задачи върху масиви.

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