Evaluate logic expression contained in a passed in string based on a list of strings

Question

So I am unsure how to word this question properly.

If you look below lets say I have a list of options (PG , PA, PM, TK, TD) that a customer has ordered. Now lets say I have some expression I need evaluate against the customers ordered options such as: PA OR PB where evaluates to customers list of options contains either option PA or PB. Seems simple enough but these expressions could grow quite a bit. Below in the code are some good examples of what I would like to accomplish.

I by no means claim to have knowledge about string parsing and comparing logical operations. I am looking for some general direction or what my options are. I saw some things about dynamic linq, rule engines, expression trees, etc. Its just a whole lot to absorb and am looking for some direction on which would accomplish what I want?

I am open to just about any approach. Any answers are appreciated!

Code:

class Program
{
    static void Main(string[] args)
    {
        //Reprsents what the customer selected
        List<string> CustomerSelectedOptins = new List<string> { "PG", "PA", "PM", "TK", "TD" };

        string LogicOperation =  "PA OR (PB AND PC)"; //Evaluates true since customer list contains PA
        string LogicOperation2 = "PF OR (NOT PB AND PM)"; //Evaluates true since customer list does not contain PB but contain PM
        string LogicOperation3 = "NOT PG AND NOT(PL AND TZ)"; //Evaluates false since the customer does have PG selected


    }
}

Answer 1

There are a few different approaches you can take. One common one is to replace the option checks with true or false and then use one of the built-in expression evaluators to evaluate the resulting expression. Note: XOR is not available for these.

public static class Evaluator {
    static Regex wordRE = new Regex(@"[A-Z]+", RegexOptions.Compiled);
    static HashSet<string> Operators = new[] { "AND", "OR", "NOT" }.ToHashSet(StringComparer.OrdinalIgnoreCase);
    public static bool Evaluate(this List<string> options, string op) {
        var opListOfOptions = wordRE.Matches(op).Select(m => m.Value).Where(w => !Operators.Contains(w));

        foreach (var option in opListOfOptions) {
            var value = options.Contains(option).ToString();
            op = op.Replace(option, value);
        }

        //return DTEval(op) == 1;
        return CompEval(op);
        //return XEval(op);
    }

    static double DTEval(string expression) {
        var dt = new DataTable();
        var loDataColumn = new DataColumn("Eval", typeof(double), expression);
        dt.Columns.Add(loDataColumn);
        dt.Rows.Add(0);
        return (double)(dt.Rows[0]["Eval"]);
    }

    static DataTable cDT = new DataTable();
    static bool CompEval(string expression) {
        return (bool)cDT.Compute(expression, "");
    }

    public static bool XEval(string expression) {
        expression = new System.Text.RegularExpressions.Regex(@"not +(true|false)").Replace(expression.ToLower(), " not(${1}) ");
        expression = new System.Text.RegularExpressions.Regex(@"(true|false)").Replace(expression, " ${1}() ");

        return (bool)new System.Xml.XPath.XPathDocument(new System.IO.StringReader("<r/>")).CreateNavigator()
                .Evaluate(String.Format("boolean({0})", expression));
    }
}

The Evaluate method comments show the different options you could use.

Alternatively, you could write your own expression evaluator. A simple one is a recursive descent evaluator that parses a simple grammar. This one uses C# precedence rules, having OR/XOR/AND binding left to right.

public class Evaluator {
    // recursive descent boolean expression evaluator
    // grammer:
    //    primary  = id
    //    primary = ( expr )
    //    unop = primary
    //    unop = not unop
    //    andop = unop [ and unop ]*
    //    xorop = andop [ xor andop ]*
    //    orop = xorop [ or xorop ]*
    //    expr = orop

    public class TokenList {
        List<string> tokens;
        int curTokenNum;

        static Regex tokenRE = new Regex(@"\w+|[()]", RegexOptions.Compiled);
        public TokenList(string expr) {
            curTokenNum = 0;
            tokens = tokenRE.Matches(expr).Select(m => m.Value).ToList();
        }

        public string CurToken => curTokenNum < tokens.Count ? tokens[curTokenNum] : String.Empty;
        public void MoveNext() => ++curTokenNum;
        public bool MoreTokens => curTokenNum < tokens.Count;

        public void NextToken() {
            MoveNext();
            if (!MoreTokens)
                throw new InvalidExpressionException("Expected token");
        }
    }

    static List<string> OperatorStrings = new[] { "AND", "OR", "XOR", "NOT" }.ToList();
    enum Operators { and, or, xor, not };
    static List<string> ParenStrings = new[] { "(", ")" }.ToList();
    enum Parens { open, close };

    TokenList tokens;
    List<string> trueOptions;

    public Evaluator(List<string> trueOptions) {
        this.trueOptions = trueOptions;
    }

    string curToken => tokens.CurToken;
    bool curTokenValue => trueOptions.Contains(curToken);

    bool isOperator => OperatorStrings.FindIndex(s => s.Equals(curToken, StringComparison.OrdinalIgnoreCase)) != -1;
    Operators curOp => (Operators)OperatorStrings.FindIndex(s => s.Equals(curToken, StringComparison.OrdinalIgnoreCase));

    bool isParen => ParenStrings.Contains(curToken);
    Parens curParen => (Parens)(ParenStrings.IndexOf(curToken));

    public bool id() {
        if (isOperator)
            throw new InvalidExpressionException("missing operand");
        else {
            var ans = curTokenValue;
            tokens.MoveNext();
            return ans;
        }
    }

    bool primary() {
        if (isParen)
            if (curParen == Parens.open) {
                tokens.NextToken();
                var ans = expr();
                if (!isParen || curParen != Parens.close)
                    throw new InvalidExpressionException($"missing ) at {curToken}");
                else
                    tokens.MoveNext();
                return ans;
            }
            else
                throw new InvalidExpressionException("Invalid )");
        else
            return id();
    }

    bool unop() {
        if (isOperator && curOp == Operators.not) {
            tokens.NextToken();
            return !unop();
        }
        else
            return primary();
    }

    bool andop() {
        var ans = unop();
        while (tokens.MoreTokens && isOperator && curOp == Operators.and) {
            tokens.NextToken();
            ans = ans & unop();
        }
        return ans;
    }

    bool xorop() {
        var ans = andop();
        while (tokens.MoreTokens && isOperator && curOp == Operators.xor) {
            tokens.NextToken();
            ans = ans ^ andop();
        }
        return ans;
    }

    bool orop() {
        var ans = xorop();
        while (tokens.MoreTokens && isOperator && curOp == Operators.or) {
            tokens.NextToken();
            ans = ans | xorop();
        }
        return ans;
    }

    bool expr() => orop();

    public bool Value(string exp) {
        tokens = new TokenList(exp);

        var ans = expr();
        if (tokens.MoreTokens)
            throw new InvalidExpressionException($"Unrecognized token {curToken} after expression");
        return ans;
    }
}

You can call it by creating an Evaluator and passing it an expression to evaluate:

var eval = new Evaluator(CustomerSelectedOptions);
var ans =  eval.Value(LogicOperation);