Стек

Стек – структура данных, которая позволяет добавлять элементы только на вершину и доставать элементов только с вершины. Принцип LIFO (“Last in – First out”, то есть “Последним пришел – Первым ушел”).

Операции, которые поддерживает стек:

Есть разные реализации стека: на фиксированном или динамическом массиве, но использование C++ позволяет не задумываться и использование встроенный тип std::stack<T>

Таким образом, стек не поддерживает больше никаких операций: ни итераций, ни обращения по индексу.

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;

    stack.push(1); // push элемента на вершину стека

    // top -- получение элемента
    std::cout << stack.top() << std::endl;

    stack.pop(); // pop удаление элемента с вершины стека

    // empty -- пуст ли стек
    if (stack.empty()) {
        std::cout << "Stack is empty" << std::endl;
    } else {
        std::cout << "Stack is not empty" << std::endl;
    }

    return 0;
}

Вообще такое ограничение в использовании знакомых конструкций не напрасно:

Классическая задача на стек – проверка скобочных последовательность на правильность.

Скобочные последовательности

Скобочная последовательность – любая строка, которая состоит из любого количества закрывающих и открывающих скобок.

Формально она называется правильной, если она:

  • пуста

  • равна \(AB\), где \(A\) и \(B\) правильный скобочные по последовательности

  • равна \((A)\), где \(A\) правильная. Вместо круглых может быть любой тип скобок по условию задачи

Примеры правильных: \(((()()()))\), \((()())()()\)

Примеры неправильных: \()(\), \(())()()\), \(((())))\)

Один тип скобок

Заметим, что количество открывающих скобок должно равняться количество закрывающих. Также ни в какой момент количество закрывающих не должно превышать количество открывающих.

Поскольку у нас только 1 тип скобок, эти условия можно проверить балансом скобок. При открытии скобки \(+1\), при закрытии \(-1\)

Условия на баланс:

  • итоговый баланс равен \(0\)

  • баланс всегда \(\ge 0\)

Соблюдение этих условий на баланс скобок равносильно правильности скобочной последовательности

Несколько типов скобок

Для определенность пусть типов будет 3: \(()\{\}[]\)

Теперь уже недостаточно поддерживать баланс всех скобок или баланс по типам скобок? потому что не отражает зависимости между расстановкой скобок. Например, последовательность \(([)]\) является “правильной” по каждой из скобок (балансы неотрицательны, в конце равны \(0\)), но неправильной по нашему определению

Для решения такой задачи придется использовать стек. Требования:

  • в конце последовательности стек пуст

  • если скобка открывающая, то добавляем ее в стек

  • если скобка закрывающая, то

    • если стек пуст, то последовательность неправльная

    • берем с вершины стека скобку и проверяем, что она совпадает с нашей закрывающей по типу – круглая с круглой, квадратная с квадратной и так далее

Обратная польская нотация

Постфиксная запись (или обратная польская нотация, как ее еще называют) – способ удобной записи арифметических выражений.

Как посчитать арифметическое выражение, записанное в обратной нотации:

  • идем по последовательности слева направо

  • если встретилось число, добавляем в структуру

  • если встретился знак арифметической операции, то

    • выполняем эту арифметическую операцию с 2 числами, которые были добавлены последними – удалем их из структуры

    • добавляем в структуру результат операции

  • по окончании прохода в структуре должно находиться только одно число – это и есть значение всего выражения

  • если одну из операций невозможно выполнить, то это ошибка записи. Например, нужно взять из структуры 2 числа, а там их меньше чем 2. Итог – ошибка записи

Пример:5 15 + 4 7 + 1 - /

  • 5

  • 5 15

  • 5 15 +→ 20

  • 20 4

  • 20 4 7

  • 20 4 7 + → 20 11

  • 20 11 1

  • 20 11 1 - →20 10

  • 20 10 / → 2

  • 2 – результат