для записи математических выражений таким образом, чтобы их было проще анализировать. В ОПН выражение 1 + 2 выглядит как 1 2 +. Сначала идут операнды, а затем — оператор. Еще один пример: выражение (1 + 2) * 3 в ОПН выглядит как 1 2 + 3 *, оно уже показывает, почему подобные выражения проще анализировать, и нам не нужны скобки, чтобы определить подвыражения (рис. 2.4).
Как это делается
В этом примере мы считаем математическое выражение, записанное в формате ОПН, из стандартного потока ввода, а затем передадим его в функцию, которая вычислит его значение. Наконец, выведем на экран численный результат.
1. Мы будем использовать множество вспомогательных объектов из STL, поэтому сначала разместим несколько директив включения:
#include <iostream>
#include <stack>
#include <iterator>
#include <map>
#include <sstream>
#include <cassert>
#include <vector>
#include <stdexcept>
#include <cmath>
2. Мы также объявляем, что используем пространство имен std, чтобы сэкономить немного времени, которое ушло бы на набор текста:
using namespace std;
3. Далее немедленно начнем реализовывать наш анализатор ОПН. Он станет принимать пару итераторов, указывающих на начало и конец математического выражения, передаваемого в качестве строки, которое будет проработано токен за токеном:
template <typename IT>
double evaluate_rpn(IT it, IT end)
{
4. Пока мы итерируем по токенам, нам следует запоминать все операнды до тех пор, пока мы не встретим операцию. Для этого и нужен стек. Все числа будут проанализированы и сохранены с удвоенной точностью, поэтому мы заводим стек элементов типа double:
stack<double> val_stack;
5. Чтобы удобным образом получить доступ к элементам стека, реализуем вспомогательную функцию. Она изменяет стек, извлекая значение с его вершины, а затем возвращает это значение. Таким образом мы сможем выполнить нашу задачу за один шаг:
auto pop_stack ([&](){
auto r (val_stack.top());
val_stack.pop();
return r;
});
6. Еще одним приготовлением будет определение всех поддерживаемых математических операций. Мы сохраним их в ассоциативный массив, где каждый токен операции будет связан с самой операцией. Операции представлены вызываемыми лямбда-выражениями, которые принимают два операнда, а затем, например, складывают или умножают их и возвращают результат:
map<string, double (*)(double, double)> ops {
{"+", [](double a, double b) { return a + b; }},
{"-", [](double a, double b) { return a - b; }},
{"*", [](double a, double b) { return a * b; }},
{"/", [](double a, double b) { return a / b; }},
{"^", [](double a, double b) { return pow(a, b); }},
{"%", [](double a, double b) { return fmod(a, b); }},
};
7. Теперь наконец можно проитерировать по входным данным. Предположив, что входные итераторы передали строки, мы передаем данные в новый поток std::stringstream токен за токеном, поскольку он может анализировать числа:
for (; it != end; ++it) {
stringstream ss {*it};
8. Теперь, когда у нас есть все токены, попробуем получить на их основе значение типа double. Если эта операция завершается успешно, то у нас появляется операнд, который мы помещаем в стек:
if (double val; ss >> val) {
val_stack.push(val);
}
9. Если же операция завершается неудачно, то перед нами нечто отличное от оператора. Это может быть только операнд. Зная, что все поддерживаемые нами операции бинарны, нужно вытолкнуть два последних операнда из стека:
else {
const auto r {pop_stack()};
const auto l {pop_stack()};
10. Теперь мы получаем операнд путем разыменования итератора it, который возвращает строки. Обратившись в ассоциативный массив ops, мы получаем лямбда-объект, принимающий в качестве параметров два операнда — l и r:
try {
const auto & op (ops.at(*it));
const double result {op(l, r)};
val_stack.push(result);
}
11. Мы окружили математическую часть приложения блоком try, поэтому можем отловить потенциально возникающие исключения. Вызов функции at для контейнера map сгенерирует исключение out_of_range, если пользователь даст команду выполнить математическую операцию, о которой мы не знаем. В таком случае мы повторно сгенерируем другое исключение, сообщающее о том, что полученный аргумент некорректен (invalid argument), и содержащее строку, которая оказалась неизвестной для нас:
catch (const out_of_range &) {
throw invalid_argument(*it);
}
12. На этом все. Когда цикл прекратит свою работу, у нас в стеке будет итоговый результат. Так что мы просто вернем его. (В тот момент можно проверить, равен ли размер стека единице. Если нет, значит, некоторые операции были пропущены.)
}
}
return val_stack.top();
}
13. Теперь можно воспользоваться нашим анализатором ОПН. Для этого обернем стандартный поток ввода данных с помощью пары итераторов std::istream_iterator и передадим его функции-анализатору ОПН. Наконец, выведем результат на экран:
int main()
{
try {
cout << evaluate_rpn(istream_iterator<string>{cin}, {})
<< 'n';
}
14. Опять же эту строку мы обернули в блок try, поскольку существует вероятность, что пользовательские данные содержат операции, которые у нас не реализованы. В таких ситуациях нужно перехватывать генерируемое исключение и выводить на экран сообщение об ошибке:
catch (const invalid_argument &e) {
cout << "Invalid operator: " << e.what() << 'n';
}
}
15. После компиляции программы можно с ней поэкспериментировать. Входные данные "3 1 2 + * 2 /" представляют собой выражение (3 * (1 + 2) ) / 2, которое приложение преобразует к корректному результату:
$ echo "3 1 2 + * 2 /" | ./rpn_calculator
4.5
Как это работает
Весь пример строится на помещении операндов в стек до тех пор, пока мы не найдем во входных данных операцию. В этой ситуации мы выталкиваем два последних операнда
