Регулярные выражения и математический парсер

    Когда-то давно мне понадобился парсер математических выражений на C#. Конечно, скачать готовую реализацию — не проблема. Но вот только Интернета у меня в те годы не было. В итоге абсолютно без раздумий и без теоретических основ парсеров, конечных автоматов и прочего он был написан через регулярные выражения. Минут за 10. Стоит отметить, что нужны были только арифметический действия и скобки. Поддержка тригонометрических функций и прочего не требовалась.

    Для начала выделим регулярные выражения для чисел и действий:
    private const string RegexBr = "\\(([1234567890\\.\\+\\-\\*\\/^%]*)\\)";    // Скобки
    private const string RegexNum = "[-]?\\d+\\.?\\d*";                         // Числа
    private const string RegexMulOp = "[\\*\\/^%]";                             // Первоприоритетные числа
    private const string RegexAddOp = "[\\+\\-]";                               // Второприоритетные числа
    

    Теперь метод, который полученную строку разделяет на элементы и рекурсивно их вычисляет:
    public static double Parse(string str)
    {
        // Парсинг скобок
        var matchSk = Regex.Match(str, RegexBr);
        if (matchSk.Groups.Count > 1)
        {
            string inner = matchSk.Groups[0].Value.Substring(1, matchSk.Groups[0].Value.Trim().Length - 2);
            string left = str.Substring(0, matchSk.Index);
            string right = str.Substring(matchSk.Index + matchSk.Length);
    
            return Parse(left + Parse(inner).ToString(CultureInfo.InvariantCulture) + right);
        }
    
        // Парсинг действий
        var matchMulOp = Regex.Match(str, string.Format("({0})\\s?({1})\\s?({2})\\s?", RegexNum, RegexMulOp, RegexNum));
        var matchAddOp = Regex.Match(str, string.Format("({0})\\s?({1})\\s?({2})\\s?", RegexNum, RegexAddOp, RegexNum));
        var match = matchMulOp.Groups.Count > 1 ? matchMulOp : matchAddOp.Groups.Count > 1 ? matchAddOp : null;
        if (match != null)
        {
            string left = str.Substring(0, match.Index);
            string right = str.Substring(match.Index + match.Length);
            return Parse(left + ParseAct(match).ToString(CultureInfo.InvariantCulture) + right);
        }
    
        // Парсинг числа
        try
        {
            return double.Parse(str, CultureInfo.InvariantCulture);
        }
        catch (FormatException)
        {
            throw new FormatException(string.Format("Неверная входная строка '{0}'", str));
        }
    }
    

    И последним напишем метод, который непосредственно вычисляет значение действия:
    private static double ParseAct(Match match)
    {
        double a = double.Parse(match.Groups[1].Value, CultureInfo.InvariantCulture);
        double b = double.Parse(match.Groups[3].Value, CultureInfo.InvariantCulture);
    
        switch (match.Groups[2].Value)
        {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            case "^": return Math.Pow(a, b);
            case "%": return a % b;
            default: throw new FormatException($"Неверная входная строка '{match.Value}'");
        }
    }
    

    Такое вот «ненормальное программирование» у меня было. Исходный текст полностью приводить не вижу никакого смысла — вряд ли это кому-нибудь понадобится. Но в любом случае составить класс из трех кусков — дело пары секунд.

    Спасибо за внимание.
    Share post

    Similar posts

    Comments 16

      0
      Регулярные выражения — это в каком-то смысле и есть конечные автоматы. То есть, регулярка компилируется в конечный автомат, в котором терминальные вершины — как раз «нашлось» и «не нашлось».

      То есть, на самом деле, вы всё по науке сделали.
        0
        Да, согласен. Я имел ввиду, что в то время я и слов таких-то не знал.
          +2
          Ну с наукой вы мягко говоря преувеличили. По науке выражения нужно парсить с помощью кс-парсеров и вычислять на каждом подвыражении промежуточный результат, а в идеале строить граф и обходить его. И не использовать регулярки.
            +5
            Какой отвратительно неверный вывод вы сделали из верной посылки.
            0
            Было бы приятно увидеть примеры.
              –2
              #include <stdio.h>
              #include <stdlib.h>
              double eval(char*&p);
              bool is(char*&p, char c) { return *p == c ? p++, true : false; }
              double un(char*&p) {
               if (is(p, '(')) {
                double r = eval(p);
                if (!is(p, ')')) printf("expected ')'");
                return r;
               } else return strtod(p, &p);
              }
              double muls(char*&p) {
               double r = un(p);
               for (;;) {
                if (is(p, '*')) r *= un(p);
                else if (is(p, '/')) r /= un(p);
                else return r;
               }
              }
              double eval(char*&p) {
               double r = muls(p);
               for (;;) {
                if (is(p, '+')) r += muls(p);
                else if (is(p, '-')) r -= muls(p);
                else return r;
               }
              }
              int main(int argc, char** argv) {
               double r = eval(argv[1]);
               if (*argv[1] == 0) printf("%lf", r);
               else printf("error at %s", argv[1]);
              }
              
                +1
                Ну и? Тут кто-то кроме вас разберется? Был у меня подобный код, через пол года смотришь на него как баран на новые ворота. В итоге подобную задачу (делал скриптовый язык для МК) решил при помощи связки лекс/бизон компиляция в VM, а на микроконтроллере конечный автомат разбора и исполнения простейшей стековой VM, все красиво все понятно.
                  0
                  И моей команде, да и мне самому через 10 лет будет легко разобраться в этом коде,
                  потому что:
                  1. Это классический рекурсивный спуск, описанный в классическом труде Вирта,
                    который, в силу особенностей российской системы образования, знаком каждому прораммисту.
                  2. Этот код, занимающий 30 строк текста, и не имеющий ни одной внешней зависимости,
                    проще в чтении, чем одно определение RegexBr из верхнего примера.
                  3. Этот код является формальной записью BNF разбираемого выражения на языке Си.
                    В самом деле, посмотрите функцию muls, разбирающую операции с приоритетом умножения,
                    и сравните ее с BNF записью (естественно, освобожденной от левой рекурсии):
                    muls ::= unar muls_tail
                    muls_tail ::= ""
                        | '*' unar muls_tail
                        | '/' unar muls_tail
                    


                  Что касается lex/bison. Для полноценного скриптового языка его применение может быть оправдано. Но для вычисления простого выражения — это — как из пушки по воробьям.
                  Стековая машина имеет примерно двукратный оверхед по скорости и полуторакратный оверхед по памяти байткода по сравнению с регистровой машиной. На микроконтроллере это может быть критично.
                  Приведенная мной прямая интерпретация выражения примерно в полтора раза медленнее виртуальной машины и на порядки быстрее парсинга бизоном и исполнения на vm.
                  Если производительность критична, я бы подумал о генерации машинного кода и выбрал микроконтроллер, который умеет исполнять код из RAM.
                    0
                    1. Скорость была не критична,
                    2. Я немного не понял, вы хотите сказать, что код для витруальной машины исполняемой на МК пусть даже стековой, будет медленнее нежели прямой парсинг?
                    Может я не корректно высказался — на VM исполнялся именно байткод.
                      0
                      Если задача — загрузить в МК выражение (в любой форме) и выполнить его вычисление, то ниже — все способы, расположенные от быстрых к медленным:
                      • Фрагмент машинного кода (МК должен уметь исполнять из RAM)
                      • Регистровый байт-код // в 4..8 раз медленнее предыдущего варианта
                      • Стековый байт-код // в 2 раза медленнее предыдущего варианта
                      • Текстовое выражение (парсить моим eval) // в 2 раза медленнее предыдущего варианта
                      • Текстовое выражение (парсить через «автомат разбора и исполнения простейшей стековой VM»)// существенно медленнее предыдущего варианта + память для байт-кода

                0
                С похожим порывом писал в школе парсер на visual basic. Только в те времена регулярные выражения я считал черными ящиками, работающими на магии, потому разбирал руками. Первый вариант искал самую глубокую скобку, а потом лез наверх. Но это оказалось очень медленно (я писал штуку для построения графиков). А вот второй вариант работал примерно тем же образом, но строил цепочку операций которые приводили к вычислению выражения. Фактически — постфиксная запись, обёрнутая в некое подобие виртуальной машины. И вот тогда рисовальщик графиков стал летать.
                  0
                  C# без интернета? Без интернета было много чего, но только не C#
                    +1
                    Почему это? Диск с 2005, кажется, студией в палатке в метро — и поехали.
                      0
                      Я к тому, что ссылаться на недоступность сети Internet в том же 2005 году несколько странно. Не такое уж это дремучее было время.
                        0
                        У кого как.
                          0
                          В 2005 году я лично общался с одноклассниками из поселка Ванавара Тунгусско-Чунского района Эвенкийского Автономного Округа. В который даже продукты доставляют раз в год баржами по весне.
                          Общался через интернет. Так что я примерно представляю у кого как. Хотя неважно это. Пусть не было интернета тогда. Это не оправдание для вычисления арифметических выражений при помощи выражений регулярных.

                  Only users with full accounts can post comments. Log in, please.