Pull to refresh

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

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

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

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

$(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 с полным кодом
Tags:
Hubs:
+5
Comments 22
Comments Comments 22

Articles