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

3. Далее немедленно начнем реализовывать наш анализатор ОПН. Он станет принимать пару итераторов, указывающих на начало и конец математического выражения, передаваемого в качестве строки, которое будет проработано токен за токеном:

template

double evaluate_rpn(IT it, IT end)

{

4. Пока мы итерируем по токенам, нам следует запоминать все операнды до тех пор, пока мы не встретим операцию. Для этого и нужен стек. Все числа будут проанализированы и сохранены с удвоенной точностью, поэтому мы заводим стек элементов типа double:

  stack val_stack;

5. Чтобы удобным образом получить доступ к элементам стека, реализуем вспомогательную функцию. Она изменяет стек, извлекая значение с его вершины, а затем возвращает это значение. Таким образом мы сможем выполнить нашу задачу за один шаг:

  auto pop_stack ([&](){

    auto r (val_stack.top());

    val_stack.pop();

    return r;

  });

6. Еще одним приготовлением будет определение всех поддерживаемых математических операций. Мы сохраним их в ассоциативный массив, где каждый токен операции будет связан с самой операцией. Операции представлены вызываемыми лямбда-выражениями, которые принимают два операнда, а затем, например, складывают или умножают их и возвращают результат:

  map 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{cin}, {})

         << '\n';

  }

14. Опять же эту строку мы обернули в блок try, поскольку существует вероятность, что пользовательские данные содержат операции, которые у нас не реализованы. В таких ситуациях нужно перехватывать генерируемое исключение и выводить на экран сообщение об ошибке:

  catch (const invalid_argument &e) {