Парсинг формул в 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
    
    Поделиться публикацией

    Похожие публикации

    Комментарии 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).
                                  сходу не могу придумать, можете ли привести пример, где увеличение приоритета именно деления приведет к результату, отличному от результата с равными приоритетами?

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

                            Самое читаемое