Turn boolean-expression string into the .NET code

Question

I have logic where customer specifies a string and my app tells to the customer if this string presents in the text, something like this:

internal const string GlobalText = "blablabla";

bool PresentInTheText(string searchString)
{
  return GlobalText.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0;
}

Basically if text contains passed string return true otherwise false.

Now I want to make it more complex. Lets say if customer passes a string "foo && bar", and I need to return true if this text contains both "foo" and "bar" substrings, straightforward approach:

bool result;
if (!string.IsNullOrEmpty(passedExpression) && 
passedExpression.Contains(" && "))
{
    var tokens = passedExpression.Split(new[] { " && " }, StringSplitOptions.RemoveEmptyEntries);
    result = true;
    foreach (var token in tokens)
    {
        if (GlobalText.IndexOf(token, StringComparison.OrdinalIgnoreCase) < 0)
        {
            result = false;
        }
    }
}
return result;

It works for expressions like A && B && C. But I want generalize the solution to support all boolean operators. Let's say: ("foo" && "bar") || "baz". What would be the solution?

I would say take passed string, using regex add to all strings .IndexOf(token, StringComparison.OrdinalIgnoreCase) < >= 0 code, it would be like this:

("foo".IndexOf(token, StringComparison.OrdinalIgnoreCase) < >= 0 && 
"bar".IndexOf(token, StringComparison.OrdinalIgnoreCase) < >= 0)) ||
"baz".IndexOf(token, StringComparison.OrdinalIgnoreCase) < >= 0

and then turn this string into a function and execute using Reflections. What would be the best solution?

ETA:

Test cases:

bool Contains(string text, string expressionString);

string text = "Customers: David, Danny, Mike, Luke. Car: BMW"

string str0 = "Luke"
string str1 = "(Danny || Jennifer) && (BMW)"
string str2 = "(Mike && BMW) || Volvo"
string str3 = "(Mike || David) && Ford"
string str4 = "David && !BMW"

bool Contains(string text, string str0);  //True - This text contains "Luke"
bool Contains(string text, string str1);  //True - David and BMW in the text
bool Contains(string text, string str2);  //True - Mike and BMW in the text
bool Contains(string text, string str3);  //False - no Ford in the list
bool Contains(string text, string str4);  //False - BMW in the list

Answer 1

The easiest way to do this would be to parse the input text and build an array of boolean "true" values, so you end up with something like this:

//Dictionary<string,List<string>> members;
members["Car"].Contains("BMW") // evals to True;

Alternatively, if there's no functional difference between any of the input entries (i.e. the variable evaluates to true as long as the word shows up in the input text), you can probably just build a list of strings rather than having to worry about using their classification as the dictionary key.

Then, you parse the equation strings and see if the values are present in the boolean list, if they are, you replace them in the original equation string with a 1. If they are not present, you replace them with a 0.

You end up with something that looks like this:

string str0 = "Luke" // "1"
string str1 = "(Danny || Jennifer) && (BMW)" // "(1 || 0) && (1)"
string str2 = "(Mike && BMW) || Volvo" // "(1 && 1) || 0"
string str3 = "(Mike || David) && Ford" // "(1 || 1) && 0"
string str4 = "David && !BMW" // "1 && !0"

Now, it's just a simple iterative string replace. You loop on the string until the only thing remaining is a 1 or a 0.

while (str.Length > 1)
{
  if (str.Contains("(1 || 1)"))
    str.Replace("(1 || 1)", "1");
  if (str.Contains("(1 || 0)"))
    str.Replace("(1 || 0)", "1");
  // and so on
}

Alternatively, if you can find a C# "eval" method, you can evaluate the expression directly (and you can also use True/False instead of 0/1).

Edit:

Found a simple tokenizer that will probably work for parsing the test equations:

using System;
using System.Text.RegularExpressions;

public static string[] Tokenize(string equation)
{
    Regex RE = new Regex(@"([\(\)\! ])");
    return (RE.Split(equation));
}
//from here: https://www.safaribooksonline.com/library/view/c-cookbook/0596003390/ch08s07.html

Edit 2: Just wrote a sample project that does it.

//this parses out the string input, does not use the classifications
List<string> members = new List<string>();
string input = "Customers: David, Danny, Mike, Luke. Car: BMW";
string[] t1 = input.Split(new string[] {". "},         StringSplitOptions.RemoveEmptyEntries);
foreach (String t in t1)
{
  string[] t2 = t.Split(new string[] { ": " }, StringSplitOptions.RemoveEmptyEntries);
  string[] t3 = t2[1].Split(new string[] { "," }, StringSplitOptions.RemoveEmptyEntries);
  foreach (String s in t3)
  {
    members.Add(s.Trim());
  }
}

This tokenizes the equation and replaces with 1 and 0.

string eq = "(Danny || Jennifer) && (!BMW)";
Regex RE = new Regex(@"([\(\)\! ])");
string[] tokens = RE.Split(eq);
string eqOutput = String.Empty;
string[] operators = new string[] { "&&", "||", "!", ")", "("};
foreach (string tok in tokens)
{
  if (tok.Trim() == String.Empty)
    continue;
  if (operators.Contains(tok))
  {
    eqOutput += tok;
  }
  else if (members.Contains(tok))
  {
    eqOutput += "1";
  }
  else 
  {
    eqOutput += "0";
  }
}

At this point, the equation "(Danny || Jennifer) && (!BMW)" looks like "(1||0)&&(!1)".

Now reduce the equation to a 1 or 0.

while (eqOutput.Length > 1)
{
  if (eqOutput.Contains("!1"))
    eqOutput = eqOutput.Replace("!1", "0");
  else if (eqOutput.Contains("!0"))
    eqOutput = eqOutput.Replace("!0", "1");
  else if (eqOutput.Contains("1&&1"))
    eqOutput = eqOutput.Replace("1&&1", "1");
  else if (eqOutput.Contains("1&&0"))
    eqOutput = eqOutput.Replace("1&&0", "0");
  else if (eqOutput.Contains("0&&1"))
    eqOutput = eqOutput.Replace("0&&1", "0");
  else if (eqOutput.Contains("0&&0"))
    eqOutput = eqOutput.Replace("0&&0", "0");
  else if (eqOutput.Contains("1||1"))
    eqOutput = eqOutput.Replace("1||1", "1");
  else if (eqOutput.Contains("1||0"))
    eqOutput = eqOutput.Replace("1||0", "1");
  else if (eqOutput.Contains("0||1"))
    eqOutput = eqOutput.Replace("0||1", "1");
  else if (eqOutput.Contains("0||0"))
    eqOutput = eqOutput.Replace("0||0", "0");
  else if (eqOutput.Contains("(1)"))
    eqOutput = eqOutput.Replace("(1)", "1");
  else if (eqOutput.Contains("(0)"))
    eqOutput = eqOutput.Replace("(0)", "0");
}

Now you should have a string that contains only a 1 or a 0 indicating true or false, respectively.

Answer 2

With the help of DynamicExpresso you can easily do this in 10 lines. Let's say the text and the user input are like this:

var text = "Bob and Tom are in the same class.";
var input = "(Bob || Alice) && Tom";

You can consider "Bob" "Alice" "Tom" are variables whose type is bool in C#, the user input string becomes a valid C# expression, evaulate it using DynamicExpresso and get a bool result.

var variables = input.Split(new[] { "(", "||", "&&", ")", " " }, 
    StringSplitOptions.RemoveEmptyEntries);

var interpreter = new Interpreter();

foreach (var variable in variables)
{
    interpreter.SetVariable(variable, text.Contains(variable));
}

var result = (bool)interpreter.Parse(input).Invoke();

Answer 3

You can solve this universally in the same way that a calculator, or a compiler, evaluates an expression:

1. Tokenize the string and identify each token as an operator (OP) or an operand (A, B, C, etc).
2. Convert the token sequence from infix (A OP B) to postfix (A B OP).
3. Evaluate the postfix token sequence.

Each of these steps can be done with a well known stack based algorithm, in linear time and space. Plus, if you use this method, it automatically extends to any binary operators you'd like to add later (addition, subtraction, fuzzy string match, etc etc).

To convert from infix to postfix: http://scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/

To evaluate the postfix: http://scriptasylum.com/tutorials/infix_postfix/algorithms/postfix-evaluation/