1

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.

3

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)

2
  • Thanks. I'm already having the formula as a list like new object[] {p1, "OR", p2, "AND", p3, "AND", p4, "OR", p5} and solved it now by first finding all a AND b list-tripple entries, calculating them, replacing the 3 entries by the result, repeating until no more ANDs are present. Then doing the same with a OR b. This worked in my examples.
    – Uwe Keim
    Dec 27 '19 at 15:01
  • Does C# not have a Set type (interface with supporting classes)? I would be shocked to discover this, since it’s Dictionary support is quite good Dec 29 '19 at 14:26
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.

2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.