C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц

из стека, применяем к ним операцию и помещаем результат обратно в стек. Чтобы понять весь код примера, важно разобраться, как мы различаем операнды и операторы, работаем со стеком, а также выбираем и применяем правильную математическую операцию.

Работа со стеком

Мы помещаем элементы в стек с помощью функции push класса std::stack:

val_stack.push(val);

Выталкивание элемента из стека выглядит чуть сложнее, поскольку нам пришлось реализовывать для этого лямбда-выражение, которое принимает ссылку на объект val_stack. Взглянем на код, только теперь добавим к нему комментарии:

  auto pop_stack ([&](){

    auto r (val_stack.top()); // Получаем копию верхнего значения

    val_stack.pop();          // Удаляем верхнее значение

    return r;                 // Возвращаем копию

  }

);

Это лямбда-выражение необходимо для получения верхнего значения стека удаления из самого адаптера всего за один шаг. Интерфейс класса std::stack не позволяет делать это с помощью одного простого вызова. Однако определить лямбда-выражение нетрудно, так что теперь можно получать значения следующим образом:

double top_value {pop_stack()};

Различаем в пользовательском вводе операнды и операторы 

В основном цикле функции evaluate_rpn мы получаем текущий токен строки из итератора и затем смотрим, является ли он операндом. Если строка может быть преобразована в переменную типа double, то данное число тоже операнд. Все остальные токены, которые нельзя легко преобразовать в число (например, "+"), мы считаем операторами.

Скелет кода для выполнения именно этой задачи выглядит следующим образом:

stringstream ss {*it};

if (double val; ss >> val) {

  // Это число!

} else {

  // Это что-то другое. Это операция!

}

Оператор потока >> говорит нам, является ли рассматриваемый объект числом. Сначала мы оборачиваем строку в std::stringstream. Затем используем способность объекта класса stringstream преобразовать объект типа std::string в переменную типа double, что включает в себя разбор. Если он не работает, то мы узнаем об этом, поскольку не получится преобразовать в число некий объект, который числом не является.

Выбираем и применяем нужную математическую операцию 

Разобравшись, что текущий токен, полученный от пользователя, не является числом, мы предполагаем, что это операция наподобие + или *. Затем обращаемся к ассоциативному массиву ops с целью найти требуемую операцию и получить функцию, принимающую два операнда и возвращающую сумму, произведение или другой подходящий результат.

Сам тип такого массива выглядит относительно сложно:

map<string, double (*)(double, double)> ops { ... };

Он соотносит строки и значения типа double (*)(double, double). Что означает вторая часть данного выражения? Это описание типа читается как «указатель на функцию, которая принимает два числа типа double и возвращает одно». Представьте, будто часть (*) представляет собой имя функции, как, например, double sum(double, double), что гораздо проще прочитать. Идея заключается в следующем: наше лямбда-выражение [](double, double) { return /* какое-то число типа double */ } можно преобразовать в указатель на функцию, фактически соответствующий описанию этого указателя. Лямбда-выражения, которые не захватывают переменных из внешнего контекста, могут быть преобразованы в указатели на функции.

Таким образом, это удобный способ запросить у ассоциативного массива корректную операцию:

const auto & op (ops.at(*it));

const double result {op(l, r)};

Ассоциативный массив неявно решает еще одну задачу. Если мы выполняем вызов ops.at("foo"), то в данном случае "foo" является корректным значением ключа, но мы не сохранили операцию с таким именем. В подобных случаях массив сгенерирует исключение, которое мы отлавливаем в нашем примере. При его перехвате мы генерируем другое исключение, чтобы представить более подробное сообщение об ошибке. Пользователь будет лучше понимать, что означает полученное исключение, сообщающее о некорректном аргументе (invalid argument), в отличие от исключения, гласящего о выходе за пределы контейнера. Обратите внимание: пользователь функции evaluate_rpn может быть незнаком с ее реализацией и поэтому не знает о том, что мы применяем ассоциативный массив.

Дополнительная информация

Поскольку функция evaluate_rpn принимает итераторы, ей можно легко передавать разные входные данные, не только стандартный поток ввода. Это позволяет довольно просто протестировать ее, а также адаптировать к различным источникам данных, получаемых от пользователя.

Передача в эту функцию итераторов строкового потока или вектора строк, например, выглядит следующим образом. При этом код функции evaluate_rpn остается без изменений:

int main()

{

  stringstream s {"3 2 1 + * 2 /"};

  cout << evaluate_rpn(istream_iterator<string>{s}, {}) << 'n';

  vector<string> v {"3", "2", "1", "+", "*", "2", "/"};

  cout << evaluate_rpn(begin(v), end(v)) << 'n';

}

 

 Используйте итераторы везде, где это имеет смысл. Так вы сможете многократно применять свой код.

Подсчитываем частоту встречаемости слов с применением контейнера std::map

Контейнер std::map очень полезен в тех случаях, когда нужно разбить данные на категории и собрать соответствующую статистику. Прикрепляя изменяемые объекты к каждому ключу, который представляет собой категорию объектов, вы легко можете реализовать, к примеру, гистограмму, показывающую частоту встречаемости слов. Этим мы и займемся.

Как это делается

В этом примере мы считаем все данные, которые пользователь передает через стандартный поток ввода и которые, скажем, могут оказаться текстовым файлом. Мы разобьем полученный текст на слова, чтобы определить частоту встречаемости каждого слова.

1. Как обычно, включим все заголовочные файлы для тех структур данных, которые планируем использовать:

#include <iostream>

#include <map>

#include <vector>

#include <algorithm>

#include <iomanip>

2. Чтобы сэкономить немного времени на наборе, объявляем об использовании пространства имен std:

using namespace std;

3. Задействуем одну вспомогательную функцию, с помощью которой будем обрезать прикрепившиеся знаки препинания (например, запятые, точки и двоеточия):

string filter_punctuation(const string &s)

{

  const char *forbidden {".,:; "};

  const auto idx_start (s.find_first_not_of(forbidden));

  const auto idx_end (s.find_last_not_of(forbidden));

  return s.substr(idx_start, idx_end - idx_start + 1);

}

4. Теперь начнем писать саму программу. Создадим ассоциативный массив, в котором будут связаны каждое встреченное нами слово и счетчик, показывающий, насколько часто это слово встречается. Дополнительно введем переменную, которая будет содержать величину самого длинного встреченного нами слова, чтобы в конце работы программы перед выводом на экран