Простой парсер арифметических операций

    Для учёбы необходимо было написать парсер арифметических операций, который мог бы рассчитывать не только простейшие операции, но и работать со скобками и функциями.

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

    Первая проблема, с которой я столкнулся — скобки. Мало того, что они должны выполняться первыми, так внутри них также могут находиться скобки. И так далее.

    $(2 + 2) * ((2 * 2) + ((2 * 2) * (2 * 2)))$

    Точно такая же история с функциями — в параметрах функции могут находится другие функции и даже целые выражения.

    $sqrt(2 * 2; log(4; 2))$

    Но об этом чуть-чуть позже. Для начала надо спарсить все выражение. Заметим, что у нас могут встретиться или скобка, или число, или операнд(+, -, *, /, ^), или функция, или константа.

    Создадим для всего этого дела списки:

    public static List<string> digits = new List<string>() { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "," };
            public static List<string> operands = new List<string>() {"^", "/", "*", "+", "-"};
            public static List<string> functions = new List<string>() { "sqrt", "sin", "cos", "log", "abs"};
            public static List<string> brackets = new List<string>() { "(", ")" };
            public static List<string> constants = new List<string>() { "pi" };
            public static Dictionary<string, string> constantsValues = new Dictionary<string, string>() { ["pi"] = "3,14159265359" };
    

    И будем проверять по очереди каждый символ. Естественно, если мы встретили знак "+" или "-" не после цифры, значит этот знак обозначает положительность или отрицательность числа, соответственно.

    for (int i = 0; i < expression.Length; i++) {
                    if (brackets.Contains(expression[i].ToString())){
                        if (lastSymbol != ""){
                            symbols.Add(lastSymbol);
                            lastSymbol = "";
                        } // на случай, если до скобки шло число
                        symbols.Add(expression[i].ToString()); // Если встретили скобку - без разбирательств добавляем ее в массив символов
                    }
                    else if (digits.Contains(expression[i].ToString()) || (expression[i] == ',' && lastSymbol.IndexOf(",") == -1)){
                        lastSymbol += expression[i];
                    } // если встретили цифру - добавляем ее в специальную переменную, чтобы не разделять число
                    else if(operands.Contains(expression[i].ToString())) {
                        if (lastSymbol != ""){
                            symbols.Add(lastSymbol);
                            lastSymbol = "";
                        }
    
                        if (symbols.Count > 0 && operands.Contains(symbols[symbols.Count - 1]) || symbols.Count == 0) {
                            string number = "";
                            
                            switch (expression[i].ToString()) {
                                case "-": number += "-"; break;
                                case "+": number += "+"; break;
                            }
    
                            i++;
                            while (i < expression.Length && digits.Contains(expression[i].ToString())){
                                number += expression[i];
                                i++;
                            }
    
                            symbols.Add(number);
                            i--;
                        } // Если встретили "-" или "+", то проверяем - это знак арифметической операции или знак числа                
                        else symbols.Add(expression[i].ToString());
                    }else{
                        lastFunction += expression[i].ToString().ToLower(); // Если ни одно условие не прошло => перед нами функция или константа 
    
                        if (constants.Contains(lastFunction)) {
                            symbols.Add(constantsValues[lastFunction]);
                            lastFunction = "";
                        } // Если перед нами константа - добавляем ее в список символов как значение
                        else if (functions.Contains(lastFunction))
                        {
                            int functionStart = i + 1; // Находим первую скобку
                            int functionEnd = 0;
                            int bracketsSum = 1;
    
                            for (int j = functionStart + 1; j < expression.Length; j++)
                            {
                                if (expression[j].ToString() == "(") bracketsSum++;
                                if (expression[j].ToString() == ")") bracketsSum--;
                                if (bracketsSum == 0)
                                {
                                    functionEnd = j;
                                    i = functionEnd;
                                    break;
                                }
                            } // Находим последнюю скобку. Так сложно сделано из-за того, что функции могут быть вложенными
    
                            char[] buffer = new char[functionEnd - functionStart - 1];
                            expression.CopyTo(functionStart + 1, buffer, 0, functionEnd - functionStart - 1);
                            string functionParametrs = new string(buffer);
    
                            if (lastFunction == "sqrt"){
                                var parametrs = GetParametrs(functionParametrs);
                                symbols.Add(Math.Pow(CalculateExpression(parametrs[0]), 1 / CalculateExpression(parametrs[1])).ToString());
                            }
    
                            if (lastFunction == "log"){
                                var parametrs = GetParametrs(functionParametrs);
                                symbols.Add(Math.Log(CalculateExpression(parametrs[0]), CalculateExpression(parametrs[1])).ToString());
                            }
                            if (lastFunction == "sin") symbols.Add(Math.Sin(CalculateExpression(functionParametrs)).ToString());
                            if (lastFunction == "cos") symbols.Add(Math.Cos(CalculateExpression(functionParametrs)).ToString());
                            if (lastFunction == "abs") symbols.Add(Math.Abs(CalculateExpression(functionParametrs)).ToString());
    // Рассчитываем функцию рекурсивно
                            lastFunction = "";
                        }
                    }
                }
    
                if (lastSymbol != ""){
                    symbols.Add(lastSymbol);
                    lastSymbol = "";
                } // Если последним символом была цифра, не забываем его добавить в список 
    

    В примере проскакивала функция GetParametrs. Она нужна для случаев, когда функция имеет 2 параметра. Дело в том, что нельзя сделать простой Split. У нас может быть такое выражение:

    $sqrt(2 * 2; log(4; 2))$

    public static List<string> GetParametrs(string functionParametrs){
                int bracketsSum = 0;
                int functionEnd = 0;
                for (int j = 0; j < functionParametrs.Length; j++){
                    if (functionParametrs[j].ToString() == "(") bracketsSum++;
                    if (functionParametrs[j].ToString() == ")") bracketsSum--;
                    if (functionParametrs[j].ToString() == ";" && bracketsSum == 0){
                        functionEnd = j;
                        break;
                    }
                }
                var buffer = new char[functionEnd];
                functionParametrs.CopyTo(0, buffer, 0, functionEnd);
                string firstParametr = new string(buffer);
    
                buffer = new char[functionParametrs.Length - functionEnd - 1];
                functionParametrs.CopyTo(functionEnd + 1, buffer, 0, functionParametrs.Length - functionEnd - 1);
                string secondParametr = new string(buffer);
    
                return ( new List<string>() { firstParametr, secondParametr } );
            }
    

    Итак, выражение разбито на более мелкие, и кроме того, значения функций уже вычислены и подставлены в основное выражение как числа.

    Скобки можно обработать по тому же принципу — сразу рассчитывать их и подставлять их как числа:

    while (symbols.Contains("(")) {
                    int bracketsStart = 0;
                    int bracketsEnd = 0;
                    int bracketsSum = 0;
    
                    for (int i = 0; i < symbols.Count; i++) {
                        if (symbols[i] == "(") {
                            bracketsStart = i;
                            bracketsSum = 1;
                            break;
                        }
                    }
    
                    for (int i = bracketsStart + 1; i < symbols.Count; i++) {
                        if (symbols[i] == "(") bracketsSum++;
                        if (symbols[i] == ")") bracketsSum--;
                        if (bracketsSum == 0) {
                            bracketsEnd = i;
                            break;
                        }
                    }
    
                    string bracketsExpression = "";
                    for (int i = bracketsStart + 1; i < bracketsEnd; i++) bracketsExpression += symbols[i];
    
                    symbols[bracketsStart] = CalculateExpression(bracketsExpression).ToString();
                    symbols.RemoveRange(bracketsStart + 1, bracketsEnd - bracketsStart);                
                }
    

    С нахождением индекса закрывающейся скобки опять все немного сложнее. Нельзя просто взять следующую закрывающуюся скобку. Это не сработает для вложенных скобок.

    Основная часть программы написана. Осталось реализовать расчет обычных арифметических выражений. Чтобы не париться с порядком выполнения действий, я решил записывать выражение в польской нотации:

    foreach(var j in operands){ // Порядок выполнения операций зависит от порядка расположения знаков в массиве operands
                    var flagO = true;
                    while (flagO){
                        flagO = false;
                        for (int i = 0; i < symbols.Count; i++){
                            if (symbols[i] == j){
                                symbols[i - 1] = symbols[i - 1] + " " + symbols[i + 1] + " " + j;
                                symbols.RemoveRange(i, 2);
    
                                flagO = true;
                                break;
                            }
                        }
                    }
                }
    

    Ну и наконец, стеком рассчитываем значение выражения:

    List<string> result = new List<string>();
    
                string[] temp = symbols[0].Split(' ');
    
                for (int i = 0; i < temp.Length; i++) {
                    if (operands.Contains(temp[i])) {
                        if (temp[i] == "^") {
                            result[result.Count - 2] = Math.Pow(double.Parse(result[result.Count - 2]), double.Parse(result[result.Count - 1])).ToString();
                            result.RemoveRange(result.Count - 1, 1);
                        }
                        if (temp[i] == "+") {
                            result[result.Count - 2] = (double.Parse(result[result.Count - 2]) + double.Parse(result[result.Count - 1])).ToString();
                            result.RemoveRange(result.Count - 1, 1);
                        }
                        if (temp[i] == "-") {
                            result[result.Count - 2] = (double.Parse(result[result.Count - 2]) - double.Parse(result[result.Count - 1])).ToString();
                            result.RemoveRange(result.Count - 1, 1);
                        }
                        if (temp[i] == "*") {
                            result[result.Count - 2] = (double.Parse(result[result.Count - 2]) * double.Parse(result[result.Count - 1])).ToString();
                            result.RemoveRange(result.Count - 1, 1);
                        }
                        if (temp[i] == "/") {
                            result[result.Count - 2] = (double.Parse(result[result.Count - 2]) / double.Parse(result[result.Count - 1])).ToString();
                            result.RemoveRange(result.Count - 1, 1);
                        }
                    }
                    else result.Add(temp[i]);
                }
    

    Если всё прошло хорошо, в result[0] будет лежать результат.

    Ссылка на GitHub с полным кодом
    Share post

    Comments 21

      +9

      Что-то ваш парсер получился ничуть не простой...


                              char[] buffer = new char[functionEnd - functionStart - 1];
                              expression.CopyTo(functionStart + 1, buffer, 0, functionEnd - functionStart - 1);
                              string functionParametrs = new string(buffer);

      Кто-нибудь, расскажите автору о существовании метода Substring!


                              result.RemoveRange(result.Count - 1, 1);

      И о методе RemoveAt тоже нужно напомнить...

        +1

        Это же C#, да?


        В интернете не нашел готовых и подходящих для меня решений

        Чем вас не устроил Sprache?

          +1
          Боюсь, это не получится сдать в качестве домашней работы)
            +7
            Ваше нормальному преподавателю — тоже сдать не получится.
            Ну можно же погуглить, почитать про рекурсивный спуск или сортировочную станцию, и не изобретать неработающее непонятно что.
          +2
            +2

            Он даже близко не подобрался к его изобретению.

              0
              Shunting-yard это алгоритм для инфиксной нотации. Автор же просто отказался от попытки ее разбора в пользу польской нотации, где порядок выполнения операций определяется их порядком в записи.
              0
              julia> str = "(2 + 2) * ((2 * 2) + ((2 * 2) * (2 * 2)))" # строка с арифметикой
              "(2 + 2) * ((2 * 2) + ((2 * 2) * (2 * 2)))"
              
              julia> Meta.parse(str)
              :((2 + 2) * (2 * 2 + (2 * 2) * (2 * 2)))
              
              julia> eval(ans)
              80
              
              julia> str2 = replace(str, '*' => "+ 2 +")
              "(2 + 2) + 2 + ((2 + 2 + 2) + ((2 + 2 + 2) + 2 + (2 + 2 + 2)))"
              
              julia> str2 |> Meta.parse |> eval # цепочка функций
              26
              
                +2

                Решать через аналог eval можно и в C#. Но все такие решения плохи по нескольким причинам:


                • ты привязан к грамматике своего языка, не можешь её расширить,
                • пользователь может вместо арифметического выражения отправить что-то с побочным эффектом (если eval полноценный).
                +7
                Не смог прочитать ваш код. Впрочем, у меня и свой не всегда получается читать.:-)

                Когда то на меня произвел большое впечатление курс по компиляторам.
                Т.е. как классно и гладко распарсивается синтаксис программы.
                Арифметическое выражение это явно проще чем программа.
                Рекурсивное чтение будет на ура проходить.

                Уверен, в инете много примеров, и если вы хотите сделать действительно красиво — попробуйте посмотреть в эту сторону.
                ((((((((((((((((((И скобки считать не придется...))))))))))))))))))))))
                +3

                Теперь про ошибки в алгоритме.


                1. "Естественно, если мы встретили знак "+" или "-" не после цифры, значит этот знак обозначает положительность или отрицательность числа, соответственно." — нет, не естественно. Смотрите: sin(1) - 2


                2. С каких пор у функции sqrt есть второй аргумент? Напоминаю, что название этой функции — аббревиатура от "square root", что переводится как "квадратный корень"


                3. В польской нотации можно записывать не только "простые" формулы, а вообще любые, и без скобок. Так, ваш пример sqrt(2*2; log(4;2)) может быть записан как 2 2 * 4 2 log sqrt. Отсюда вопрос: зачем вам вообще понадобилась большая часть алгоритма? Зачем все эти поиски парных скобок, нахождение параметров и прочее?


                  +1
                  Спасибо! Обязательно учту Ваши замечания!
                  +3
                  Дорогой дневничок
                  Я смотрю, Хабр растет прям новыми уникальными алгоритмами решения школьных домашних заданий. Надо и мне свой велосипед на рекурсивном разборе и вычисления строки выражения залить сюда что ли, а то на хабре так мало годного контента стало…
                    0
                    Надо бы мне свой курсовичок залить с генератором компиляторов чисто на Qt без внешних зависимостей вроде бизона)
                    А так да, тортовость падает
                    +2
                    Понимаю, что это учебный проект. Однако ведь пользователю интересен не код, а результат. Чтобы проверить выпоняет ли код ожидания пользователя — нужны юнит-тесты. Тогда хоть как-то можно будет понять для каких конкретных случаев этот код работает. А так это черный ящик. С неопределенным количеством багов внутри. От этого есть и побочный положительный эффект для разработчика. Начнете писать тесты — лучше станете понимать логику приложения. Ну и если захотите поменять реализацию — с тестами будет куда проще убедиться что оно все еще делает то что должно.
                      0
                      А чем вас рекурсивный спуск не устроил? Просто и элегантно, если не разбирать гигантские выражения — то и с памятью тоже будет всё в порядке.
                        0

                        Antlr, вроде, как один из самых популярных. И nuget-пакет для него есть даже. Понятно, что любой парсер требует порог вхождения, но поверьте, что самостоятельная обработка ошибок намного сложнее самописного парсера.
                        Я однажды сам попытался написать простой парсер типа вашего. Больше таких глупостей не делаю. )))
                        Как способ посмотреть, насколько это сложное и неблагодарное занятие подходит, но для чего-то в продакшен не пойдёт. Попробуйте добавить хоть одну «переменную» и все придётся переписать.
                        Почитайте что-нибудь по грамматикам.

                          +2
                          Вытеки мои глазоньки… Действительно, решение — «оригинальное» — в том смысле, что второго такого вряд ли найдете. Если целью учебного задания было научить вас работать со строками и стандартными структурами данных в C#, то, наверное, все ок, а если — научиться писать парсер, то так парсер не пишется.

                          Вы допустили несколько ошибок — методологических в основном.

                          1. Любой парсер начинается с юнит-тестов! Для начала хотя бы пары выражений, но в идеале — чем больше, тем лучше. Потратьте полчаса времени придумывая самые извратные варианты — потом это окупится с лихвой.
                          2. За юнит-тестами идет грамматика. Честно говоря, я был удивлен, не увидев её в статье — может, вам её уже дали в условиях задания? Если нет — обязательно нужно описать грамматику и отладить её на юнит-тестах — в инете есть для этого средства, ну или написать свои.
                          3. Далее — лексер. Он разбивает выражение на токены, затем парсер работает уже с ними. Одновременно токенизировать и парсить как минимум неудобно.
                          4. Наконец — сам парсер. Изобретать велосипед — дело, конечно, интересное, но в вопросе парсинга математических выражений — мягко говоря, неблагодарное. Все уже было украдено до нас. Задолго. Просто реализуйте алгоритм рекурсивного спуска или сортировочной станции и радуйтесь результату.
                            +1
                            Ну у нас например на втором курсе был преподаватель, который давал это задание как «желательно сделать», для математических лабораторных с построением графиков. А грамматики были на четвертом.

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