How to parse the following string

Question

I am trying to generate a formula which could be anything like this, this is just a sample,

A + B + C > D - A

Now, A, B, C, D, etc are Column Names of a sheet (like excel sheet) i will be accessing in memory.

I need to generate a Rule, like the above A + B + C > D - A which will decide what kind of values user can add in a Cell.

Currently this is how i have begun:

string toValidate = "A + B + C > D + E - A";
string lhs = "", rhs = "";
string[] comparisonOperators = new string[] { "=", ">", "<", "<>", "!=" };
char[] arithmeticOperators = { '+', '-', '/', '*' };
toValidate = toValidate.Replace(@" ", "");  
for (int i = 0; i < comparisonOperators.Length; i++)
{
    if (toValidate.Contains(comparisonOperators[i]))
    {
        operatorIndex = toValidate.IndexOf(comparisonOperators[i]);
        break;
    }
}
lhs = toValidate.Substring(0, operatorIndex);
rhs = toValidate.Substring(operatorIndex + 1);
string[] columnLhsList = lhs.Split(arithmeticOperators);
string[] columnRhsList = rhs.Split(arithmeticOperators);

However even though i have the strings as lhs and rhs and even my operator which > in the above code, i am not able to understand how can i apply the formula on the sheet itself. I just need to know which Column has which operator associated.

Since i have the individual column names, but not the operator before them, for e.g,

+ before A - before A in another case.

How do i parse the above please help.

Answer 1

It is, however, a very fun question if you want to make simple formula parsers like this yourself.

I advice you to check out this article, since it is very clearly written and understandable because of it.

Shunting-yard Algorithm

Answer 2

Personally, I would never try/dare to create my own formula expression parser. Instead, I would (and did) use one of the may available ones, e.g. NCalc over at CodePlex.com.

Using these tools, it is as easy as writing

Expression e = new Expression("2 + 3 * 5");
Debug.Assert(17 == e.Evaluate());

to get your formula evaluated.

Usually such libraries are very solid, well tested and have a rich function set. It would take ages (if ever) to do such a high quality library on my own.

To further cite the NCalc website, you can even use variables like e.g.:

Expression e = new Expression("Round(Pow([Pi], 2) + Pow([Pi2], 2) + [X], 2)");

e.Parameters["Pi2"] = new Expression("Pi * [Pi]");
e.Parameters["X"] = 10;

e.EvaluateParameter += 
    delegate(string name, ParameterArgs args)
    {
        if (name == "Pi")
        args.Result = 3.14;
    };

Debug.Assert(117.07 == e.Evaluate());