Parsing formulas with functions
Good day!
It took a small project. In the project analysis and calculation of mathematical formulas.
Requirements: nested functions, unlimited nesting depth and external variables.
There are many solutions on the Internet, but it’s all wrong or wrong. Or without formulas, or without variables, or the simplest features like “1+ (2-3) / 4”. But most of the answers were in the direction of lexical analysis and reverse Polish notation. So I applied them, taking examples from different sources.
First, let's analyze the lexical analysis. Because a simple analysis of the formula by symbols with a search for functions, operators, variables and other things in it would be extremely unreadable.
The implementation of the algorithms can be taken on the Internet and edited to fit your needs.
For lexical analysis made small changes:
Here's what happened. Below is a link to the source.
Replacing the unary plus and minus could be more beautifully implemented, but writing regular expressions is not my talent. With pleasure I will use your option.
Next, I redid the implementation of the reverse Polish entry taken from the wiki. It was necessary to transfer to the input no longer a string but a list of tokens. This fact slightly simplified the algorithm.
The peculiarity of logical operations is that if the number is greater than zero, then it becomes True , otherwise False .
Actually, at this stage the formulas are completely considered. There is no feature support.
At first, I wanted to implement functions through a separate token. But something went wrong ... I took the path of least resistance. In the lexical analysis of the formula, all variables that have been replaced with numerical values become numbers, and everything else that has not been replaced becomes functions. A little not logical, but it works.
Further, according to the algorithm, we find and place all our tokens with newly minted functions in the list of functions.
A function may contain other functions. Everything is entered into the operands of the function, and if there is a function there, then a new function is added recursively to its list. Of course, the depth of investments is not limited by anything.
Actually, a recursive algorithm for calculating function values and replacing it with the result:
All the functions used are implemented here. Add something of your own does not seem difficult.
For example, I will give a solution to the quadratic equation:
Of course, solving quadratic equations is not a good example. There is no way to get multiple answers in the results, and then, if there are no roots, this formula will return zero. But to demonstrate the possibilities will do.
[ Link to the project ]
There are enough places in the project for optimization. For example, there is a repeating code and the results of all branches of the condition are calculated. And you never know what can be optimized. The main thing is to stop on time.
PS: While writing, I added a function to get values from the graph.
It took a small project. In the project analysis and calculation of mathematical formulas.
Requirements: nested functions, unlimited nesting depth and external variables.
There are many solutions on the Internet, but it’s all wrong or wrong. Or without formulas, or without variables, or the simplest features like “1+ (2-3) / 4”. But most of the answers were in the direction of lexical analysis and reverse Polish notation. So I applied them, taking examples from different sources.
First, let's analyze the lexical analysis. Because a simple analysis of the formula by symbols with a search for functions, operators, variables and other things in it would be extremely unreadable.
The implementation of the algorithms can be taken on the Internet and edited to fit your needs.
For lexical analysis made small changes:
- loading a list of variables. In the constructor, variables are replaced with their values;
- replacement of separators of the integer-fractional part of the number with the one used in the system;
- added a unary minus;
- deleted superfluous tokens for me.
Here's what happened. Below is a link to the source.
List of available tokens
enum LexemType
{
Plus,
Minus,
Multiply,
Divide,
UnarMinus,
Equals,
NotEquals,
Greater,
Lower,
GreaterEquals,
LowerEquals,
And,
Or,
LBracket,
RBracket,
Semicolon,
Identifier,
Number
}
Token Definition
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),
};
}
Search and replace unary minus and plus
private string ReplaceUnarOperator(String src)
{
return Regex.Replace(Regex.Replace(Regex.Replace(Regex.Replace(src, @"(\(\+)", "("), @"(\A[\+]{1})", ""), @"(\(-)", "(%"), @"(\A[-]{1})", "%");
}
Replacing the unary plus and minus could be more beautifully implemented, but writing regular expressions is not my talent. With pleasure I will use your option.
Next, I redid the implementation of the reverse Polish entry taken from the wiki. It was necessary to transfer to the input no longer a string but a list of tokens. This fact slightly simplified the algorithm.
Convert to SCF
private static Lexem[] ConvertToPostfixNotation(List _lexems)
{
List outputSeparated = new List();
Stack stack = new Stack();
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();
}
SCR calculation
private static String getResult(List _lexems)
{
Stack stack = new Stack();
Lexem[] postfix = ConvertToPostfixNotation(_lexems);
Queue queue = new Queue(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;
}
The peculiarity of logical operations is that if the number is greater than zero, then it becomes True , otherwise False .
Actually, at this stage the formulas are completely considered. There is no feature support.
At first, I wanted to implement functions through a separate token. But something went wrong ... I took the path of least resistance. In the lexical analysis of the formula, all variables that have been replaced with numerical values become numbers, and everything else that has not been replaced becomes functions. A little not logical, but it works.
Further, according to the algorithm, we find and place all our tokens with newly minted functions in the list of functions.
Function class implementation
internal class Functions
{
public List FunctionList = new List();
public List> operands = new List>();
public Functions(Queue queue)
{
Queue lexems = new Queue();
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 operand = new List();
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();
}
else
{
operand.Add(currLextm);
}
}
operand.Remove(operand.Last());
operands.Add(operand);
}
}
A function may contain other functions. Everything is entered into the operands of the function, and if there is a function there, then a new function is added recursively to its list. Of course, the depth of investments is not limited by anything.
Actually, a recursive algorithm for calculating function values and replacing it with the result:
Constructor and recursive replacement of a function with calculation results
public static Dictionary NTDs = new Dictionary();
public static Dictionary variables = new Dictionary();
private List FunctionList = new List();
private List> operands = new List>();
private static List operators = new List()
{
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 queue = new Queue(new Lexer(formula, variables).Lexems);
Lexem currLextm = null;
Queue lexems = new Queue();
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 operand = new List();
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();
}
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 Calc(List fList, List> lOps)
{
List res = new List();
if (fList.Count == 0)
{
foreach (List op in lOps)
{
String resOp = getResult(op);
res.Add(resOp);
}
}
else
{
foreach (List 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 funcRes = Calc(func.FunctionList, func.operands);
List rList = new List();
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;
}
All the functions used are implemented here. Add something of your own does not seem difficult.
For example, I will give a solution to the quadratic equation:
Calculation Example
Dictionary variables = new Dictionary();
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";
Output result
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
Of course, solving quadratic equations is not a good example. There is no way to get multiple answers in the results, and then, if there are no roots, this formula will return zero. But to demonstrate the possibilities will do.
[ Link to the project ]
There are enough places in the project for optimization. For example, there is a repeating code and the results of all branches of the condition are calculated. And you never know what can be optimized. The main thing is to stop on time.
PS: While writing, I added a function to get values from the graph.
Graph function
public class NTDClass
{
public String Name;
public Dictionary Graph;
public NTDClass(String name, DataTable table)
{
Graph = new Dictionary();
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;
}
}
Function call
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;
}
.....
.....
.....