Пользователь
0,0
рейтинг
20 марта 2014 в 06:05

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

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

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

Получившейся код:
#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
@lunserv
карма
15,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (27)

  • +10
    Ура, про перл :)
    • +2
      И Форт! )
  • +2
    Чем то напоминает двухстековый алгоритм Дейкстры.
  • –8
    Неплохо бы оформить это в виде .h и .cpp файлов, и на джитхаб!
    Очень хочется иметь набор простых заголовочников на все случаи жизни, без надобности сбора библиотеки и прочего.
    • +7
      Читается «гитхаб», однако.
      • +2
        буду знать.
    • –4
      Выделяешь, копируешь, сохраняешь где нужно. Ваш КО.
      Али нынче джоннихакеры настолько лениво-толстые и троллеобразные пошли?
      • +1
        уважаемый, вас никто не троллил, и никак в ваш адрес не выражался.
        В комментарии я написал про библиотеку с простыми функциями, а не про одну конкретную функцию. Не?
        Для меня отдельным секретом остается кол-во минусов на комментарии, но это уже дело хабра.
        • –5
          >для меня отдельным секретом остается кол-во минусов
          Бывает. Ну не дано понять, мал ещё.
    • 0
  • +1
    Может будет интересно (если кто не видел) Рекурсивный main(), или программирование квадратиком
    • 0
      Очень хороший пример для иллюстрации как делать не надо. :) Прямо идеальное дополнение к статье. Спасибо.
  • –24
    мне казалось, что у деления больше приоритет, чем у умножения
    • +16
      еще скажите, что у вычитания больший приоритет, чем у сложения
    • +2
      Одинаковый.
    • +9
      Ну и кто еще будет спорить, что высшее образование программисту не нужно?%sarcasm%
      • +23
        Высшее? Я думаю, класс 3й где-то;)
    • –2
      В некоторых языках — таки да. Но обычно — одинаковый.
      • 0
        Стало интересно, поковырял вопрос, но ничего такого не нашел.

        Пару ссылок к информации по которым сводится все, что я нашел.

        Приоритет операции:
        ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8
        Ассоциативность:
        ru.wikipedia.org/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D1%81%D1%82%D1%8C

        Если не сложно, можете привести пример, где по другому (т.е. операторы одного ранга имеют разный приоритет выполнения)?
        • 0
          По-моему, в каком-то древнем недофортране для GE-200 специально прописывалось, что у деления приоритет выше. Но это скорее так — курьез природы :-). Обычно же приоритет одинаковый.
        • 0
          За вечер вполне можно реализовать нечто примитивное на уровне brainfuck'а с максимальным приоритетом у деления;)
        • +3
    • –1
      какой был бы смысл давать делению больший приоритет? выражения (a*b)/c и a*(b/c) математически эквивалентны.
      • –2
        А c/(a*b) и (c/a)*b уже не эквивалентны.
        • +1
          хорошо, но в приведенном случае: c/a*b == (c/a)*b, то есть порядок могло нарушить увеличение приоритета умножения: c/a*b != c/(a*b).
          сходу не могу придумать, можете ли привести пример, где увеличение приоритета именно деления приведет к результату, отличному от результата с равными приоритетами?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.