I need help in extracting all minimum true condition out of a expression (like where clause in sql)
lets say i have a expression like:
Eg 1:
((A & B ) & (C | D))
output should be:
((A & B) | C)
((A & B) | D)
Eg 2:
((A | B) & (C | D))
output should be:
(A & C)
(A & D)
(B & C)
(B & D)
Eg 3:
(A | B | C)
output should be :
(A)
(B)
(C)
NOTE: '|' represent 'OR' and '&' represent 'AND', so want to break a big condition into all possible smallest true conditions.
Please suggest...
So it seems that what would help you is to have a way of simplifying your expression into a sum of products. By having it in sum of products form you will have a series of different options, each of which will be the only one to be correct if all of the values it contains are true.
One way of dealing with this is to use the composite pattern. We'll start out with our IExpression interface:
public interface IExpression<T>
{
int NumberOfPossibilities();
IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities();
IEnumerable<ValueExpression<T>> GetNthPossibility(int n);
}
The key points here are the first and last methods. We need to be able to know how many possibilities there are for a given expression as well as a simple way of getting the Nth possibility. The convention for the last method is that all of the given values need to be true for the Nth possibility. For the second method the outer enumerable are all expressions to be ORed together, while each of the inner expressions need to be ANDed together.
There will be three implementations. A ValueExpression that represents just one value, an AndExpression that represents ANDing N expressions together, and an OrExpression that represents ORing N expressions together.
The Value is the simplest to implement:
public class ValueExpression<T> : IExpression<T>
{
public T Value { get; set; }
public ValueExpression(T value)
{
Value = value;
}
public int NumberOfPossibilities()
{
return 1;
}
public IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities()
{
return new[] { new[] { this } };
}
public IEnumerable<ValueExpression<T>> GetNthPossibility(int n)
{
return new[] { this };
}
}
The And expression is a tad more involved. The number of possibilities for an AND expression is the product of the number of possibilities being ANDed.
To get the Nth possibility you can think of it as such:
start at 0; for 0 the result requires ANDing together the first possibility of each of the sub-expressions. For the 1st possibility we add one to the first sub-expression. Each time n goes up we increase the permutation we get from the first sub expression. When we pass it's count it goes back to zero and the next sub-expression goes up by one. It's basically like counting, but where each digit represents one of the sub-expressions and where the base of that digit is the count of the possibilities for that sub-expression.
public class AndExpression<T> : IExpression<T>
{
private IList<IExpression<T>> expressions;
public AndExpression(IList<IExpression<T>> expressions)
{
this.expressions = expressions;
}
public int NumberOfPossibilities()
{
return expressions.Aggregate(1,
(acc, expression) => acc * expression.NumberOfPossibilities());
}
IEnumerable<IEnumerable<ValueExpression<T>>> IExpression<T>.Possibilities()
{
return Enumerable.Range(0, NumberOfPossibilities())
.Select(n => GetNthPossibility(n));
}
public IEnumerable<ValueExpression<T>> GetNthPossibility(int n)
{
for (int i = 0; i < expressions.Count; i++)
{
int count = expressions[i].NumberOfPossibilities();
foreach (var value in expressions[i].GetNthPossibility(n % count))
yield return value;
n /= count;
}
}
}
For the OR expression it's similar to, but still distinct from, the AND version.
The number of possibilities is the sum, not the product of the counts of the inner expressions.
To get the nth possibility we only return the items from one of the possibilities of one of the sub expressions, rather than returning one from each as AND does.
public class OrExpression<T> : IExpression<T>
{
private IList<IExpression<T>> expressions;
public OrExpression(IList<IExpression<T>> expressions)
{
this.expressions = expressions;
}
public int NumberOfPossibilities()
{
return expressions.Sum(expression => expression.NumberOfPossibilities());
}
public IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities()
{
return Enumerable.Range(0, NumberOfPossibilities())
.Select(n => GetNthPossibility(n));
}
public IEnumerable<ValueExpression<T>> GetNthPossibility(int n)
{
for (int i = 0; i < expressions.Count; i++)
{
int count = expressions[i].NumberOfPossibilities();
if (n < count)
return expressions[i].GetNthPossibility(n);
else
n -= count;
}
throw new ArgumentOutOfRangeException();
}
}
Here is a simple function to print out an expression as a string:
public static void PrintPossibilities<T>(IExpression<T> expression)
{
Console.WriteLine(string.Join(" + ", expression.Possibilities()
.Select(possibility =>
string.Concat(possibility.Select(value => value.Value)))));
}
Note that this doesn't handle parsing the expression, merely processing it once it's been parsed.
Here is a test of your first example:
var AB = new AndExpression<string>(new[]{
new ValueExpression<string>("A"),
new ValueExpression<string>("B")});
var CD = new OrExpression<string>(new[]{
new ValueExpression<string>("C"),
new ValueExpression<string>("D")});
var exp = new AndExpression<string>(new IExpression<string>[] { AB, CD });
PrintPossibilities(exp);
Which prints:
ABC + ABD
AB changed to be an OR expression (your second example) prints:
AC + BC + AD + BD
Your third option can be represented as:
var third = new OrExpression<string>(new[]{
new ValueExpression<string>("A"),
new ValueExpression<string>("B"),
new ValueExpression<string>("C")});
which when printed results in:
A + B + C