из стека, применяем к ним операцию и помещаем результат обратно в стек. Чтобы понять весь код примера, важно разобраться, как мы различаем
операнды и
операторы, работаем со стеком, а также выбираем и применяем правильную математическую операцию.
Работа со стеком
Мы помещаем элементы в стек с помощью функции 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. Теперь начнем писать саму программу. Создадим ассоциативный массив, в котором будут связаны каждое встреченное нами слово и счетчик, показывающий, насколько часто это слово встречается. Дополнительно введем переменную, которая будет содержать величину самого длинного встреченного нами слова, чтобы в конце работы программы перед выводом на экран
