Главная

Парсинг формул в 40 строк

2014-03-20 в 2:05, admin, рубрики: Без рубрики

Иногда бывает интересно взять какую небольшую задачку(по типу тех, что дают на собеседованиях) и найти для нее необычное решение.
В этот раз такой это стала задача от Яндекса. В самом посте и в комментариях было предложено несколько вариантов решения, темой этого топика станет поиск короткого решения в функциональном стиле.

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

Получившейся код:

#include <iostream>
#include <map>
#include <stack>
#include <functional>
#include <utility>
#include <stdlib.h>

using namespace std;

int main(int argc, char** argv) {
  stack<double> s;  stack< pair<int, char> > ops;

  auto p = [&s, &ops] (function<double (double, double)>& f)
    {double r=s.top();s.pop();r=f(s.top(),r);s.pop();s.push(r);ops.pop();};

  map< char, pair< int, function<double (double, double)> > > m =
    {{'+', {1, [](double a, double b){return a+b;}}},{'-', {1, [](double a, double b){return a-b;}}},
     {'*', {2, [](double a, double b){return a*b;}}},{'/', {2, [](double a, double b){return a/b;}}}};

  const int order = 2; int level = 0;
  for (char* sp = argv[1];; ++sp) {
    while (*sp == '(') {level += order; ++sp;}

    s.push(strtod(sp, &sp));

    while (*sp == ')') {level -= order; ++sp;}

    if (!*sp) {while(!ops.empty()) p(m[ops.top().second].second); break;}

    const int op =  m[*sp].first + level;
    while (!ops.empty() && ops.top().first >= op) p(m[ops.top().second].second);

    ops.push(make_pair(op, *sp));
  }

  cout << s.top() << endl;
  return 0;
}

Запуск: