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

I'd take a step back, think about what you're trying to do and if necessary see if anyone has skinned this cat before. — NPSF3000
– NPSF3000, Commented Dec 1, 2016 at 22:54
Have a look at the Interpreter Design Pattern: codeproject.com/articles/186183/interpreter-design-pattern — Fruchtzwerg
– Fruchtzwerg, Commented Dec 1, 2016 at 22:58
@M.kazem Akhgary, my text can not contain anything but letters and numbers, so if I see " && " or " || " in the search string I would assume that it's a boolean-expression and treat it accordingly. — Romz
– Romz, Commented Dec 1, 2016 at 23:36
I would suggest doing this properly and writing a token parser. Especially with the parentheses going on. Like do you have nested booleans, etc? A token parser is easy to write and it will handle all those cases... it will also tell you where/what the parsing error is, whereas your current implementation can't. — SledgeHammer
– SledgeHammer, Commented Dec 2, 2016 at 0:09

ErikE · Accepted Answer · 2016-12-02 02:14:32Z

2

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

Tokenize the string and identify each token as an operator (OP) or an operand (A, B, C, etc).
Convert the token sequence from infix (A OP B) to postfix (A B OP).
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/

edited Dec 2, 2016 at 2:14

ErikE

50.7k23 gold badges157 silver badges201 bronze badges

answered Dec 2, 2016 at 1:56

Nick

13.5k17 gold badges67 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

jpreed00 · Accepted Answer · 2016-12-02 02:26:59Z

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.

edited Dec 2, 2016 at 2:26

answered Dec 2, 2016 at 0:19

jpreed00

8939 silver badges25 bronze badges

7 Comments

ErikE Over a year ago

This is clever and avoids the problem of projecting the logic expressed by the string expression into C# code by projecting instead the presence or absence of such tokens back into the expression. I would suggest that using else may not be as efficient as just performing all the if statements in succession? Also, you don't need any parentheticals besides (1) and (0).

jpreed00 Over a year ago

@ErikE I think you are correct on all counts. I'll edit. I had them listed as if-else because in normal evaluation loops, you have order of operations issues. For example, you evaluate a multiply op, then fall through an evaluate a sum op before a div op (or something) and you get a wrong answer. I don't think that's the case here, though.

ErikE Over a year ago

Wait, there is an order of operations for || and &&: && is supposed to be performed first. I take back what I said about not using if-else (though some thought might allow you to do some looping inside of the loop). I stand by what I said about the parentheses, though. For example, (1||0)&&(1) is NOT equal to 1||0&&1 because that is actually 1||(0&&1).

jpreed00 Over a year ago

@ErikE As long as the appropriate parens were used, it wouldn't have mattered, but I reverted it anyway. :)

ErikE Over a year ago

Better for random internet script kiddies to not misuse our code! I agree with all your edits.

|

Cheng Chen · Accepted Answer · 2016-12-02 02:19:59Z

0

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();

answered Dec 2, 2016 at 2:19

Cheng Chen

43.7k18 gold badges118 silver badges184 bronze badges

Collectives™ on Stack Overflow

Turn boolean-expression string into the .NET code

3 Answers 3

Comments

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related