Best approach to parse the expression - Multiple variables

Question

I have a situation where i need to parse multiple n number of related fields (Do not want to evaluate):

    string exp1 = "10";
    string exp2 = "20";
    string exp3= "exp1 + exp2 + 30";
    string exp4 = "exp5 - exp3"; 
    string exp5 = "exp3 / 10";

    Dictionary<string,string> expressions = new Dictionary<string,string>();
    expressions.Add("exp1", exp1);
    expressions.Add("exp2", exp2);
    expressions.Add("exp3", exp3);
    expressions.Add("exp4", exp3);
    expressions.Add("exp5", exp5);

Now we want to loop through all the expression fields and parse the expression with the actual values (Bodmas should also be applied) .So, after parsing, We want below as output:

exp1 = "10";
exp2 = "20";
exp3= "10 + 20 + 30";
exp4 = "((10 + 20 + 30 )/10) - (10+ 20 + 30)";
exp5 = "(10 + 29 + 30)/ 10";

What would be the data structure I should use here to parse it using a generic way? Would it be Binary Tree, graphs, ExpressionTrees?

I'd use recursion and also use a dictionary instead of a list. — Mark Cilia Vincenti, Apr 12 '20 at 07:28
@Program : I do not want to evaluate, I just need to resolve the expression with actual values. There is n level of relationship between expression. — Sahil, Apr 12 '20 at 07:49
@MarkCiliaVincenti: Yes, recursion would work. Also, I have updated the question to use dictionary. Is there another generic approach? — Sahil, Apr 12 '20 at 07:50
@MarkCiliaVincenti recursion would have a problem at "exp4" because it has "exp5" in it which was not yet been evaluated. I mean what would you do when you hit "exp4"? **EDIT** if you can change the order so that "exp5" will parse "exp4" you can just parse them sequently — styx, Apr 12 '20 at 07:56
@styx: I cannot change the order as I do not know in which expression we can have what other expressions. As the expressions can be changed anytime by UI. So we can't do anything for ordering. That is the issue and reason I am asking this question. — Sahil, Apr 12 '20 at 08:03
Other options could be https://github.com/StefH/System.Linq.Dynamic.Core or https://eval-expression.net/ — Stef Heyenrath, Apr 12 '20 at 08:21
stack can be used. if a stack is not empty, then expression is not valid expression — Gauravsa, Apr 12 '20 at 08:26
You might simply replace the expressions using `String.Replace()`, imho, no need for parsing, based on the requirement. — Martin Staufcik, Apr 12 '20 at 08:42
@MartinStaufcik : What if I have 5 level of nested expression, Would String.Replace() be efficient way of resolving it? — Sahil, Apr 12 '20 at 08:54
@StefHeyenrath: i am not getting it. What should i check in that repo? — Sahil, Apr 12 '20 at 08:54
@Gauravsa: agreed. But what if we have 5 levels of nested expression in 200 expressions? — Sahil, Apr 12 '20 at 09:02
@UweKeim mind checking this [meta post](https://meta.stackoverflow.com/q/396552/578411). Your close vote (and that of the others) is disputed. — rene, Apr 12 '20 at 13:25
@UweKeim: How it is related to the linked one? I mentioned that I do not want to evaluate the expression. I just need to resolve n level mapping between expression to resolve each expression. And I wanted to know the best possible traversing data structure for this. — Sahil, Apr 12 '20 at 13:32

Pradeep Kumar · Answer 1 · 2020-04-12T13:37:50.263

The Code

using System.Collections.Generic;
using Microsoft.VisualBasic;    //the code was written in VB and converted. make appropriate changes if you don't want to use this namespace

class Exp
{
    private Dictionary<string, string> AllExpressions = new Dictionary<string, string>();

    public void Add(string name, string value)
    {
        AllExpressions.Add(name, value);
    }

    public string ValueOf(string name)
    {
        var parts = Strings.Split(AllExpressions[name]);
        for (int i = 0; i <= parts.Length - 1; i++)
        {
            if (AllExpressions.ContainsKey(parts[i]))
            {
                var partVal = ValueOf(parts[i]);
                parts[i] =  Information.IsNumeric(partVal) ? partVal : $"({partVal})";
            }
        }
        return Strings.Join(parts);
    }
}

Usage

Exp myExp = new Exp();
myExp.Add("exp1", "10");
myExp.Add("exp2", "20");
myExp.Add("exp3", "exp1 + exp2 + 30");
myExp.Add("exp4", "exp5 - exp3");
myExp.Add("exp5", "exp3 / 10");

// Test to see if we can get correct values 
Console.WriteLine(myExp.ValueOf("exp1"));
Console.WriteLine(myExp.ValueOf("exp2"));
Console.WriteLine(myExp.ValueOf("exp3"));
Console.WriteLine(myExp.ValueOf("exp4"));
Console.WriteLine(myExp.ValueOf("exp5"));

The Result

10
20
10 + 20 + 30
((10 + 20 + 30) / 10) - (10 + 20 + 30)
(10 + 20 + 30) / 10

In real scenario, these expressions will come from database not like these hard-coded variables. Second and important thing is you are changing the order of expressions to make it easy. Bur the ordering cannot be changed and there and n level sum expression in an expression. I have already commented about it in the previous comments. — Sahil, Apr 12 '20 at 12:38
OK, I got the point. I have made changes to my reply based on your comments. — Pradeep Kumar, Apr 12 '20 at 13:38

score 0 · Answer 2 · answered Apr 12 '20 at 08:34

Well, not the most elegant solution, but I think it works

            string exp1 = "10";
            string exp2 = "20";
            string exp3 = "exp1 + exp2 + 30";
            string exp4 = "exp5 - exp3";
            string exp5 = "exp3 / 10";         

            var dic = new Dictionary<String, String>();
            dic.Add("exp1", exp1);
            dic.Add("exp2", exp2);
            dic.Add("exp3", exp3);
            dic.Add("exp4", exp4);
            dic.Add("exp5", exp5);


            for (int i = 0; i < dic.Count; i++)          
            {
                var dicItem = dic.ElementAt(i);
                var splitted = dicItem.Value.Split(' ');
                var sb = new StringBuilder();
                foreach (var splittedItem in splitted)
                {                

                    if(dic.ContainsKey(splittedItem))
                    {
                        sb.Append(dic[splittedItem]);

                    }
                    else
                    {
                        sb.Append(splittedItem);
                    }
                    sb.Append(" ");

                }
                var parsed = sb.ToString();
                if (parsed.Contains("exp"))
                    i--; //go back and try to evaluate it again

                dic.Remove(dicItem.Key);
                dic.Add(dicItem.Key, sb.ToString());

            }

and not to make it more readable you can use DynamicExpression

            var p = Expression.Parameter(typeof(String));
            foreach (var exp in dic.Values)
            {
                var e = System.Linq.Dynamic.DynamicExpression.ParseLambda(new[] { p }, null, exp);
                System.Diagnostics.Trace.WriteLine(e.Body);
            }

OUTPUT

10

20

((10 + 20) + 30)

(((((10 + 20) + (30 / 10)) - 10) + 20) + 30)

((10 + 20) + (30 / 10))

What about if i have 200+ expressions in one object? Would it be the optimized solution? — Sahil, Apr 12 '20 at 08:47

score 0 · Answer 3 · answered Apr 12 '20 at 09:32

This solution only replaces the variables:

var results = expressions.ToDictionary(x => x.Key, x => x.Value);

bool expanded;
do
{
    expanded = false;

    foreach (var key in expressions.Keys)
    {
        foreach (var kvpReplaceWith in expressions)
        {
            if (key == kvpReplaceWith.Key)
            {
                continue;
            }

            var lengthBefore = results[key].Length;
            results[key] = results[key].Replace(kvpReplaceWith.Key, "(" + kvpReplaceWith.Value + ")");
            var lengthAfter = results[key].Length;
            expanded = expanded || lengthBefore != lengthAfter;
        }

    }
}
while (expanded);

It will give me the result but the complexity is too high for this solution. for just 5 elements it goes to 15 times in the first foreach loop. — Sahil, Apr 12 '20 at 10:19

score 0 · Accepted Answer · answered Apr 12 '20 at 10:49

String replacement is unavoidable, but we can decrease the number of loops and replace operations by having a class to represent our expressions. When we have our arithmetic expressions wrapped in a reference type, we can add features and use them later:

public class ArithmeticExpression
{
    public string Value;
    public bool IsLiteral;
    public bool IsFinalized;

    public string ArithmeticSafeValue { get { return IsLiteral ? Value : "(" + Value + ")"; } }

    public ArithmeticExpression(string value)
    {
        Value = value;
        int dummy;
        IsFinalized = IsLiteral = int.TryParse(value, out dummy);
    }
}

And here is the methods to evaluate the final versions of our expressions, changing them to literals:

private static void Resolve(Dictionary<string, ArithmeticExpression> expressions)
{
    foreach (string expressionKey in expressions.Keys.ToArray())
    {
        Resolve(expressionKey, expressions);
    }
}

private static void Resolve(string expressionKey, Dictionary<string, ArithmeticExpression> expressions)
{
    ArithmeticExpression expression = expressions[expressionKey];

    if (expression.IsFinalized) return;

    List<string> containedExpressions = expressions.Keys.Where(x => expression.Value.Contains(x)).ToList();
    if (containedExpressions.Count > 0)
    {
        containedExpressions.ForEach((x) => Resolve(x, expressions));
        containedExpressions.ForEach((x) => expression.Value = expression.Value.Replace(x, expressions[x].ArithmeticSafeValue));
        expression.IsFinalized = true;
    }
}

And here is how to use it:

public static void Main()
{
    string exp1 = "10";
    string exp2 = "20";
    string exp3 = "exp1 + exp2 + 30";
    string exp4 = "exp5 - exp3";
    string exp5 = "exp3 / 10";

    Dictionary<string, ArithmeticExpression> expressions = new Dictionary<string, ArithmeticExpression>();
    expressions.Add("exp1", new ArithmeticExpression(exp1));
    expressions.Add("exp2", new ArithmeticExpression(exp2));
    expressions.Add("exp3", new ArithmeticExpression(exp3));
    expressions.Add("exp4", new ArithmeticExpression(exp4));
    expressions.Add("exp5", new ArithmeticExpression(exp5));

    Resolve(expressions);
    expressions.Keys.ToList().ForEach
    (
        (x) => Console.WriteLine("{0}: {1}", x, expressions[x].Value)
    );
}

Hope this helps.

It is perfectly fine to properly parse expressions first into abstract syntax tree of some sort and than render with values. Stating that "replace is the only way" makes this not an answer to a question about "parse" expression. Note that you could have edited the question to match an answer - so this post (and the other "answer") would answer the question and it would be easier to dispute duplicate and avoid all the controversy of "the best". — Alexei Levenkov, Apr 13 '20 at 16:37
Hi @AlexeiLevenkov, I think the verb "parsing" has kind of made us language barrier victims. I included. Because as my mind translates it, evaluating `string exp4 = "exp5 - exp3"; ` includes parsing. That, and "replacement is unavoidable" are my bad. But really, I read all the answers in the duplicate and none of the answers could help this (probably) very young person here. What could it achieve was to change the question to, "Ok, I know there is this and this to parse and calculate expressions, but.. How can I get each token on the way and display them as a single arithmetic formula?". — Oguz Ozgul, Apr 13 '20 at 17:38
And by the way. None of the voters did mind to change the title of this question either, and may be it is not their responsibility. It seems like on Meta, I was the victim of searching by title (not going into detail and not putting forth the required effort), while the "title" again was the main reason for this question to be marked as duplicate. I don't know, and it really does not matter. — Oguz Ozgul, Apr 13 '20 at 17:44

Best approach to parse the expression - Multiple variables

4 Answers4