Парсинг формул с функциями

в 16:59, , рубрики: алгоритм, Алгоритмы, Обратная польская запись, функции

Доброго времени суток!

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

В интернете много решений, но все не то, или не так. Или без формул, или без переменных или простейшие возможности типа «1+(2-3)/4». Зато большинство ответов были в сторону лексического анализа и обратной польской нотации. Вот их я и применил, взяв примеры с разных источников.

Сначала разберем лексический анализ. Потому что простой анализ формулы по символам с поиском в ней функций, операторов, переменных и прочего получился бы крайне нечитабельный.

Реализацию алгоритмов можно взять в интернете и подредактировать под свои нужды.

Для лексического анализа внес небольшие изменения:

  • загрузка списка переменных. В конструкторе происходит замена переменных их значениями;
  • замена разделителей целой-дробной части числа на тот что используется в системе;
  • добавил унарный минус;
  • удалил лишние для меня лексемы.

Вот что получилось. Ниже будет ссылка на исходники.

Список доступных лексем

enum LexemType
    {
        Plus,
        Minus,
        Multiply,
        Divide,
        UnarMinus,

        Equals,
        NotEquals,
        Greater,
        Lower,
        GreaterEquals,
        LowerEquals,

        And,
        Or,

        LBracket,
        RBracket,

        Semicolon,
        Identifier,
        Number
    }

Определение лексем

static class LexemDefinitions
    {
        public static StaticLexemDefinition[] Statics = new[]
        {
            new StaticLexemDefinition("+", LexemType.Plus),
            new StaticLexemDefinition("-", LexemType.Minus),
            new StaticLexemDefinition("*", LexemType.Multiply),
            new StaticLexemDefinition("/", LexemType.Divide),
            new StaticLexemDefinition("%", LexemType.UnarMinus),
 
            new StaticLexemDefinition("==", LexemType.Equals),
            new StaticLexemDefinition("!=", LexemType.NotEquals),
            new StaticLexemDefinition(">=", LexemType.GreaterEquals),
            new StaticLexemDefinition("<=", LexemType.LowerEquals),
            new StaticLexemDefinition(">", LexemType.Greater),
            new StaticLexemDefinition("<", LexemType.Lower),
 
            new StaticLexemDefinition("&&", LexemType.And),
            new StaticLexemDefinition("||", LexemType.Or),
 
            new StaticLexemDefinition("(", LexemType.LBracket),
            new StaticLexemDefinition(")", LexemType.RBracket),
            new StaticLexemDefinition(";", LexemType.Semicolon),
        };

        public static DynamicLexemDefinition[] Dynamics = new[]
        {
            new DynamicLexemDefinition("[a-zA-Z_][a-zA-Z0-9_]*", LexemType.Identifier),
            new DynamicLexemDefinition(@"([0-9]*.?[0-9]+)", LexemType.Number),
        };
    }

Поиск и замена унарного минуса и плюса

private string ReplaceUnarOperator(String src)
        {
            return Regex.Replace(Regex.Replace(Regex.Replace(Regex.Replace(src, @"((+)", "("), @"(A[+]{1})", ""), @"((-)", "(%"), @"(A[-]{1})", "%");
        }

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

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

Преобразование к ОПЗ
private static Lexem[] ConvertToPostfixNotation(List<Lexem> _lexems)
        {
            List<Lexem> outputSeparated = new List<Lexem>();
            Stack<Lexem> stack = new Stack<Lexem>();
            foreach (Lexem c in _lexems)
            {
                if (operators.Contains(c.Type))
                {
                    if ((stack.Count > 0) && (c.Type != LexemType.LBracket))
                    {
                        if (c.Type == LexemType.RBracket)
                        {
                            Lexem s = stack.Pop();
                            while (s.Type != LexemType.LBracket)
                            {
                                outputSeparated.Add(s);
                                s = stack.Pop();
                            }
                        }
                        else
                        {
                            if (GetPriority(c.Type) > GetPriority(stack.Peek().Type))
                            {
                                stack.Push(c);
                            }
                            else
                            {
                                while (stack.Count > 0 && GetPriority(c.Type) <= GetPriority(stack.Peek().Type)) outputSeparated.Add(stack.Pop());
                                stack.Push(c);
                            }
                        }
                    }
                    else
                        stack.Push(c);
                }
                else
                    outputSeparated.Add(c);
            }
            if (stack.Count > 0)
                foreach (Lexem c in stack)
                    outputSeparated.Add(c);
            return outputSeparated.ToArray();
        }

Расчет ОПЗ

private static String getResult(List<Lexem> _lexems)
        {
            Stack<Lexem> stack = new Stack<Lexem>();
            Lexem[] postfix = ConvertToPostfixNotation(_lexems);
            Queue<Lexem> queue = new Queue<Lexem>(postfix);
            Lexem str = queue.Dequeue();
            while (queue.Count >= 0)
            {
                if (operators.Contains(str.Type))
                {
                    Lexem result = new Lexem();
                    result.Type = LexemType.Number;
                    try
                    {

                        switch (str.Type)
                        {
                            case LexemType.UnarMinus:
                                {
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    result.Value = (-a).ToString();
                                    break;
                                }
                            case LexemType.Plus:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    result.Value = (a + b).ToString();
                                    break;
                                }
                            case LexemType.Minus:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    result.Value = (a - b).ToString();
                                    break;
                                }
                            case LexemType.Multiply:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    result.Value = (a * b).ToString();
                                    break;
                                }
                            case LexemType.Divide:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    result.Value = (a / b).ToString();
                                    break;
                                }
                            case LexemType.Equals:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    Boolean r = (a == b);
                                    result.Value = (r ? 1 : 0).ToString();
                                    break;
                                }
                            case LexemType.NotEquals:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    Boolean r = (a != b);
                                    result.Value = (r ? 1 : 0).ToString();
                                    break;
                                }
                            case LexemType.Greater:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    Boolean r = (a > b);
                                    result.Value = (r ? 1 : 0).ToString();
                                    break;
                                }
                            case LexemType.GreaterEquals:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    Boolean r = (a >= b);
                                    result.Value = (r ? 1 : 0).ToString();
                                    break;
                                }
                            case LexemType.Lower:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    Boolean r = (a < b);
                                    result.Value = (r ? 1 : 0).ToString();
                                    break;
                                }
                            case LexemType.LowerEquals:
                                {
                                    Double b = Convert.ToDouble(stack.Pop().Value);
                                    Double a = Convert.ToDouble(stack.Pop().Value);
                                    Boolean r = (a <= b);
                                    result.Value = (r ? 1 : 0).ToString();
                                    break;
                                }
                            case LexemType.Or:
                                {
                                    Boolean b = Convert.ToBoolean(Convert.ToDouble(stack.Pop().Value) > 0 ? 1 : 0);
                                    Boolean a = Convert.ToBoolean(Convert.ToDouble(stack.Pop().Value) > 0 ? 1 : 0);
                                    Boolean r = (a || b);
                                    result.Value = (r ? 1 : 0).ToString();
                                    break;
                                }
                            case LexemType.And:
                                {
                                    Boolean b = Convert.ToBoolean(Convert.ToDouble(stack.Pop().Value) > 0 ? 1 : 0);
                                    Boolean a = Convert.ToBoolean(Convert.ToDouble(stack.Pop().Value) > 0 ? 1 : 0);
                                    Boolean r = (a && b);
                                    result.Value = (r ? 1 : 0).ToString();
                                    break;
                                }
                        }
                    }
                    catch (Exception ex)
                    {
                        new InvalidOperationException(ex.Message);
                    }
                    stack.Push(result);
                    if (queue.Count > 0) str = queue.Dequeue(); else break;
                }
                else
                {
                    stack.Push(str);
                    if (queue.Count > 0) { str = queue.Dequeue(); } else break;
                }
            }
            String rValue = stack.Pop().Value;
            return rValue;
        }

Особенность логических операций в том, что если число больше нуля, то это становится True, иначе False.
Собственно, на этом этапе формулы вполне считаются. Поддержки функций только нет.

Поначалу я хотел реализовать функции через отдельную лексему. Но что-то пошло не так… Пошел по пути наименьшего сопротивления. В лексическом анализе формулы, все переменные, которые были заменены на числовые значения, становятся числами, а все остальное, что не было заменено, становится функциями. Немного не логично, но работает.

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

Реализация класса функции

internal class Functions
    {
        public List<Functions> FunctionList = new List<Functions>();
        public List<List<Lexem>> operands = new List<List<Lexem>>();

        public Functions(Queue<Lexem> queue)
        {
            Queue<Lexem> lexems = new Queue<Lexem>();
            Lexem currLextm = queue.Dequeue();
            int brackets = 1;
            while (queue.Count > 0 && brackets > 0)
            {
                currLextm = queue.Dequeue();
                if (currLextm.Type == LexemType.Identifier)
                {
                    currLextm.Value = currLextm.Value + "{" + FunctionList.Count.ToString() + "}";
                    lexems.Enqueue(currLextm);
                    FunctionList.Add(new Functions(queue));
                }
                else
                {
                    if (currLextm.Type == LexemType.LBracket)
                    {
                        brackets++;
                    }
                    if (currLextm.Type == LexemType.RBracket)
                    {
                        brackets--;
                    }
                    lexems.Enqueue(currLextm);
                }
            }
            List<Lexem> operand = new List<Lexem>();
            while (lexems.Count > 0)
            {
                currLextm = lexems.Dequeue();
                if (currLextm.Type == LexemType.LBracket) { brackets++; }
                if (currLextm.Type == LexemType.RBracket) { brackets--; }
                if ((currLextm.Type == LexemType.Semicolon)&&(brackets==0))
                {
                    operands.Add(operand);
                    operand = new List<Lexem>();
                }
                else
                {
                    operand.Add(currLextm);
                }
            }
            operand.Remove(operand.Last());
            operands.Add(operand);
        }
    }

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

Собственно, рекурсивный алгоритм расчета значений функции и замены ее на результат:

Конструктор и рекурсивная замена функции на результаты расчета

public static Dictionary<Int32, NTDClass> NTDs = new Dictionary<Int32, NTDClass>();
        public static Dictionary<String, Double> variables = new Dictionary<string,double>();
        private List<Functions> FunctionList = new List<Functions>();
        private List<List<Lexem>> operands = new List<List<Lexem>>();

        private static List<LexemType> operators = new List<LexemType>()
        { 
            LexemType.Multiply, LexemType.Divide, LexemType.Plus, LexemType.Minus, LexemType.UnarMinus, 
            LexemType.And, LexemType.Or, LexemType.Equals, LexemType.NotEquals, LexemType.Greater, LexemType.Lower, LexemType.GreaterEquals, LexemType.LowerEquals,
            LexemType.LBracket, LexemType.RBracket
        };

        public PostfixNotationExpression(String formula)
        {
            Queue<Lexem> queue = new Queue<Lexem>(new Lexer(formula, variables).Lexems);
            Lexem currLextm = null;
            Queue<Lexem> lexems = new Queue<Lexem>();
            while (queue.Count > 0)
            {
                currLextm = queue.Dequeue();
                if (currLextm.Type == LexemType.Identifier)
                {
                    currLextm.Value = currLextm.Value + "{" + FunctionList.Count.ToString() + "}";
                    lexems.Enqueue(currLextm);
                    FunctionList.Add(new Functions(queue));
                }
                else
                {
                    lexems.Enqueue(currLextm);
                }
            }
            List<Lexem> operand = new List<Lexem>();
            Int32 brackets = 0;
            while (lexems.Count > 0)
            {
                currLextm = lexems.Dequeue();
                if (currLextm.Type == LexemType.LBracket) { brackets++; }
                if (currLextm.Type == LexemType.RBracket) { brackets--; }
                if ((currLextm.Type == LexemType.Semicolon) && (brackets == 0))
                {
                    operands.Add(operand);
                    operand = new List<Lexem>();
                }
                else
                {
                    operand.Add(currLextm);
                }
            }
            operands.Add(operand);
        }

        public String Calc()
        {
            String sep = NumberFormatInfo.CurrentInfo.NumberDecimalSeparator;
            String res = Calc(FunctionList, operands).First();
            res = res == null ? "0.0" : res;
            res = res.Replace(".", sep).Replace(",", sep);
            return res;
        }
        private static List<String> Calc(List<Functions> fList, List<List<Lexem>> lOps)
        {
            List<String> res = new List<String>();
            if (fList.Count == 0)
            {
                foreach (List<Lexem> op in lOps)
                {
                    String resOp = getResult(op);
                    res.Add(resOp);
                }
            }
            else
            {
                foreach (List<Lexem> op in lOps)
                {
                    for (int i = 0; i < op.Count; i++)
                    {
                        if (op[i].Type == LexemType.Identifier)
                        {
                            String fName = op[i].Value.Remove(op[i].Value.IndexOf("{"));
                            String fNumStr = op[i].Value.Remove(0, op[i].Value.IndexOf("{") + 1);
                            fNumStr = fNumStr.Remove(fNumStr.IndexOf("}"));
                            Int32 fNum = Int32.Parse(fNumStr);
                            Functions func = fList[fNum];
                            List<String> funcRes = Calc(func.FunctionList, func.operands);
                            List<Double> rList = new List<double>();
                            for (int k = 0; k < funcRes.Count; k++)
                            {
                                rList.Add(Double.Parse(funcRes[k]));
                            }
                            switch (fName)
                            {
                                case "NTD":
                                    {
                                        String val = "0.0";
                                        Int32 key = (Int32)rList[0];
                                        if (NTDs.ContainsKey(key))
                                        {
                                            val = NTDs[key].getValue(rList[1]).ToString();
                                        }
                                        op[i] = new Lexem() 
                                        { 
                                            Type = LexemType.Number, 
                                            Value = val
                                        };
                                        break;
                                    }
                                case "If":
                                    {
                                        op[i] = new Lexem() { Type = LexemType.Number, Value = (rList[0] == 1 ? rList[1] : rList[2]).ToString() };
                                        break;
                                    }
                                case "Sqr":
                                    {
                                        op[i] = new Lexem() { Type = LexemType.Number, Value = (rList[0] * rList[0]).ToString() };
                                        break;
                                    }
                                case "Sqrt":
                                    {
                                        op[i] = new Lexem() { Type = LexemType.Number, Value = (Math.Sqrt(rList[0])).ToString() };
                                        break;
                                    }
                                case "Min":
                                    {
                                        Double Min = Double.MaxValue;
                                        for (int k = 0; k < rList.Count; k++)
                                        {
                                            if (rList[k] < Min) { Min = rList[k]; }
                                        }
                                        op[i] = new Lexem() { Type = LexemType.Number, Value = Min.ToString() };
                                        break;
                                    }
                                case "Max":
                                    {
                                        Double Max = Double.MinValue;
                                        for (int k = 0; k < rList.Count; k++)
                                        {
                                            if (rList[k] > Max) { Max = rList[k]; }
                                        }
                                        op[i] = new Lexem() { Type = LexemType.Number, Value = Max.ToString() };
                                        break;
                                    }
                            }
                        }
                    }
                    String resOp = getResult(op);
                    res.Add(resOp);
                }
            }
            return res;
        }

Здесь реализованы все используемые функции. Добавить что-то свое не представляется чем-то сложным.

Для примера приведу решение квадратного уравнения:

Пример расчета

Dictionary<String, Double> variables = new Dictionary<string, double>();
variables.Add("a", 1);
variables.Add("b", 2);
variables.Add("c", -27);
foreach (var ivar in variables)
{
     textBox1.Text += ivar.Key + " = " + ivar.Value.ToString() + "rn";
}
textBox1.Text += "--------------rn";

// a*x2 + bx + c = 0
String q1 = "(-b+Sqrt(Sqr(b)-4*a*c))/(2*a)";
String q2 = "(-b-Sqrt(Sqr(b)-4*a*c))/(2*a)";
String Formula = "If((b*b-4-a-c)>0;" + q1 + "; If((b*b-4-a-c)==0; " + q2 + "; 0))";
textBox1.Text += Formula + "rn";
textBox1.Text += new PostfixNotationExpression(Formula, variables).Calc() + "rn";
Formula = "If((b*b-4-a-c)>0;" + q2 + "; If((b*b-4-a-c)==0; " + q1 + "; 0))";
textBox1.Text += Formula + "rn";
textBox1.Text += new PostfixNotationExpression(Formula, variables).Calc() + "rn";

Вывод результата

a = 1
b = 2
c = -27
--------------
If((b*b-4-a-c)>0;(-b+Sqrt(Sqr(b)-4*a*c))/(2*a); If((b*b-4-a-c)==0; (-b-Sqrt(Sqr(b)-4*a*c))/(2*a); 0))
4.2915026221292
If((b*b-4-a-c)>0;(-b-Sqrt(Sqr(b)-4*a*c))/(2*a); If((b*b-4-a-c)==0; (-b+Sqrt(Sqr(b)-4*a*c))/(2*a); 0))
-6.2915026221292

Конечно, решение квадратных уравнений — не слишком хороший пример. Нет возможности получить в результатах несколько ответов, и потом, если нет корней, данная формула вернет ноль. Но для демонстрации возможностей пойдет.

[ Ссылка на проект ]

В проекте достаточно мест для оптимизации. Например, есть повторяющийся код и результаты всех ветвей условия рассчитываются. Да и мало ли чего можно наоптимизировать. Главное — вовремя остановиться.

PS: Пока писал, добавил функцию получения значений с графика.

Функция графика

public class NTDClass
    {
        public String Name;
        public Dictionary<Double, Double> Graph;

        public NTDClass(String name, DataTable table)
        {
            Graph = new Dictionary<double, double>();
            foreach(DataRow row in table.AsEnumerable())
            {
                Double x = Double.Parse(row["Id"].ToString());
                Double y = Double.Parse(row["VALUE"].ToString());
                if (!Graph.ContainsKey(x)) { Graph.Add(x, y); }
                else 
                {
                    x += 0.00001;
                    Graph.Add(x, y);
                }
            }
        }

        public Double getValue(Double b)
        {
            Double res = Double.NaN;
            var xScale = Graph.Keys.AsEnumerable();
            Double minX = xScale.OrderBy(x => x).Where(x => x <= b).DefaultIfEmpty(xScale.OrderBy(x => x).First()).LastOrDefault();
            Double maxX = xScale.OrderBy(x => x).Where(x => x >= b).DefaultIfEmpty(xScale.OrderBy(x => x).Last()).FirstOrDefault();
            Double minY = Graph[minX];
            Double maxY = Graph[maxX];
            res = (((b - minX) * (maxY - minY)) / (maxX - minX) + minY);
            return res;
        }
    }

Вызов функции

switch (fName)
                            {
                                case "NTD":
                                    {
                                        String val = "0.0";
                                        Int32 key = (Int32)rList[0];
                                        if (NTDs.ContainsKey(key))
                                        {
                                            val = NTDs[key].getValue(rList[1]).ToString();
                                        }
                                        op[i] = new Lexem() 
                                        { 
                                            Type = LexemType.Number, 
                                            Value = val
                                        };
                                        break;
                                    }
.....
.....
.....

Автор: tRaider82

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js