11 ноября 2021

Применение структуры данных стек

Пример 1. Проверка сбалансированности скобок. Решим следующую задачу. Дана строка line. Среди символов в строке встречаются символы открывающихся ((, [) и закрывающихся (), ]) скобок. Необходимо определить является ли последовательность скобок согласованной. Примеры согласованных последовательностей:

Примеры несогласаванных посдедовательностей:

Алгоритм решения этой задачи - следующий:

  1. Заводим стек символов.
  2. Читаем символы строки слева направо, пропуская все символы, кроме скобок.
  3. Если очередной символ - открывающаяся скобка ( или [, то помещаем символ в стек.
  4. Если очередной символ - закрывающаяся скобка ) или ], то поверяем, что
    • Стек не пуст
    • Верхний элемент стека является соответсвующей открывающейся скобкой (( сообветствует ))
  5. Если условия предыдущего пункта выполнены, то удаляем элемент со стека и продолжаем обработку символов. В противном случае последовательность скобок не согласована.
  6. При достижении конца строки стек должен быть пустым, иначе последовательность скобок не согласована.

Примеры выражений

Пример программы, которая считывает каждую строку файла:

#include <stdio.h>
#include <stdlib.h>

int main() {
    FILE* fptr = fopen("data.txt", "r");
    char* s = NULL;
    size_t bufsize;
    while (!feof(fptr)) {
        ssize_t len = getline(&s, &bufsize, fptr);
        printf("%s %lu %lu\n", s, bufsize, len);
    }
    free(s);
    return 0;
}

Пример 2. Стековая машина. Математические выражения можно записывать эквивалентно в обратной польской нотации. Операнды при такой записи расположены перед операторами. Примеры:

Инфиксная нотация Обратная польская нотация
a + b a b +
a + b + c a b + c +
a * (b + c / 2) a b c 2 / + *

Эта форма записи позволяет избежать использования скобок. Кроме того, существует простой алгоритм для вычисления значения выражений, записанных в обратной польской нотации. Для преобразования инфиксной нотации в обратную польскую нотацию можно использовать, например, алгоритм сортировочной станции. Мы не будем обсуждать детали этого алгоритма.

Нашей задачей будет написать программу для вычисления значения арифметического выражения, записанного в обратной польской нотации и содержащие только четыре бинарных оператора: +, -, /, *. Деление будем выплонять целочисленно.

Алгоритм вычисления выражения:

  1. Создаем стек целых чисел.
  2. Читаем очередной токен.
    • Если это число, то помещаем его в стек.
    • Если это оператор, то берем со стека два значения, применяем к ним оператор и помещаем результат обратно в стек.
  3. Оставшееся значение в стеке является искомым результатом вычисления.

Примеры выражений