Доброго времени суток!
Понадобилось сделать небольшой проект. В проекте разбор и вычисление математических формул.
Требования: вложенные функции, неограниченная глубина вложения и внешние переменные.
В интернете много решений, но все не то, или не так. Или без формул, или без переменных или простейшие возможности типа «1+(2-3)/4». Зато большинство ответов были в сторону лексического анализа и обратной польской нотации. Вот их я и применил, взяв примеры с разных источников.
Сначала разберем лексический анализ. Потому что простой анализ формулы по символам с поиском в ней функций, операторов, переменных и прочего получился бы крайне нечитабельный.
Реализацию алгоритмов можно взять в интернете и подредактировать под свои нужды.
Для лексического анализа внес небольшие изменения:
Вот что получилось. Ниже будет ссылка на исходники.
Замена унарного плюса и минуса могло бы быть и покрасивее реализовано, но вот написание регулярных выражений не является моим талантом. С удовольствием воспользуюсь вашим вариантом.
Далее переделал реализацию обратной польской записи взятой с вики. Надо было на вход передавать уже не строку а список лексем. Данный факт слегка упростил алгоритм.
Особенность логических операций в том, что если число больше нуля, то это становится True, иначе False.
Собственно, на этом этапе формулы вполне считаются. Поддержки функций только нет.
Поначалу я хотел реализовать функции через отдельную лексему. Но что-то пошло не так… Пошел по пути наименьшего сопротивления. В лексическом анализе формулы, все переменные, которые были заменены на числовые значения, становятся числами, а все остальное, что не было заменено, становится функциями. Немного не логично, но работает.
Далее по алгоритму все наши лексемы с новоиспеченными функциями находим и помещаем в список функций.
Функция может содержать в себе другие функции. Все заносится в операнды функции и если там попалась функция, то рекурсивно добавляется новая функция в свой список. Разумеется, глубина вложений ничем не ограниченна.
Собственно, рекурсивный алгоритм расчета значений функции и замены ее на результат:
Здесь реализованы все используемые функции. Добавить что-то свое не представляется чем-то сложным.
Для примера приведу решение квадратного уравнения:
Конечно, решение квадратных уравнений — не слишком хороший пример. Нет возможности получить в результатах несколько ответов, и потом, если нет корней, данная формула вернет ноль. Но для демонстрации возможностей пойдет.
[ Ссылка на проект ]
В проекте достаточно мест для оптимизации. Например, есть повторяющийся код и результаты всех ветвей условия рассчитываются. Да и мало ли чего можно наоптимизировать. Главное — вовремя остановиться.
PS: Пока писал, добавил функцию получения значений с графика.
Понадобилось сделать небольшой проект. В проекте разбор и вычисление математических формул.
Требования: вложенные функции, неограниченная глубина вложения и внешние переменные.
В интернете много решений, но все не то, или не так. Или без формул, или без переменных или простейшие возможности типа «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() + "\r\n";
}
textBox1.Text += "--------------\r\n";
// 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 + "\r\n";
textBox1.Text += new PostfixNotationExpression(Formula, variables).Calc() + "\r\n";
Formula = "If((b*b-4-a-c)>0;" + q2 + "; If((b*b-4-a-c)==0; " + q1 + "; 0))";
textBox1.Text += Formula + "\r\n";
textBox1.Text += new PostfixNotationExpression(Formula, variables).Calc() + "\r\n";
Вывод результата
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;
}
.....
.....
.....