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

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

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

    Получившейся код:
    #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
    
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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