How to concat lists with logical ANDs and ORs

Question

Having multiple lists of integers, like e.g.:

var p1 = new[] { 3, 9, 5, 8, 9 };
var p2 = new[] { 12, 1, 18, 27, 103, 99, 4 };
var p3 = new[] { 23, 930, 15 };
// ...

I want to concatenate them with logical AND and OR operations, like e.g.:

var result = p1 AND p2 OR p3 ...

AND should have higher precedence than OR. The result is again a list.

Definitions:

• a OR b should take integers that are present in either list a or in b, resulting in a list.
• a AND b should take only integers that are present both in list a and in b, resulting in a list.

What makes this complicated to solve for me is that the number of lists (and their content) is defined by the user during runtime, as well as the operators on how to concatenate the lists.

I.e. the user might define 5 lists and concatenate them like p1 OR p2 AND p3 AND p4 OR p5 or the user might define 2 lists and concatenate them like p1 AND p2. Or he might as well define 20 list and concatenate them with an arbitrary combination of AND and OR, too.

Solution attempt

My first approach was to get some C# formula parser and introduce my own operator (like AND and OR, or at least overload * as AND and + as OR).

Unfortunately, I couldn't find one; the closest I came across was Mages by Florian Rappl, which seems to not support overloading of operators.

Now, I'm out of ideas. I fear that I possibly have to define my own grammar and have to write a lexer or something other complicated (to me).

My question

I am looking for ideas on how to solve this. Maybe there are completely other ways beside my formular parser idea.

Answer 1

The operations you are looking for are intersect and union which are the equivalent operations of the AND/OR in your example. If you need to handle arbitrary sets with arbitrary operations you will have to build your own parser essentially. Getting the input into something you can work with is the first step. A list of lists for the integers and a list of operations to perform is probably the simplest set up to hold the data. Mapping OR to Union and AND to intersect isn't too difficult. The second step is building the correct order of operations. Start with the first list and operation, then since the ANDs should be evaluated first you need to look ahead to the next operation to determine if the second list is a product of two other lists or the next list provided. If you do this until there are no more operations, the resulting expression should provide the correct list when evaluated.

For example p1 OR p2 AND p3 AND p4 OR p5 would become something like this after parsing it p1.union(p2.intersect(p3).intersect(p4)).union(p5)

Answer 2

The only reason you'd need a parser is if you're letting the user input things like this:

3, 9, 5, 8, 9 AND 12, 1, 18, 27, 103, 99, 4

If the user is typing things like this:

p1 + p2 * p3 * p4 + p5 

Then you're creating a library and your user is a programmer. C# is your parser.

In this case you do need operator overloading.

In either case, since you're using C#, look at Hashset. It has all the logic for unions and intersections done for you. It would be a good collection to back your class with.