Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

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

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

#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;
}

Запуск:

./calc "15/(7-(1 1))*3-(2 (1 1))"
5

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB