c# - 如何从表达式中获取所有最小真实条件

Question

我需要帮助从表达式中提取所有最小真条件(比如 sql 中的 where 子句)

假设我有这样一个表达式:

例1:

((A & B ) & (C | D))
output should be:
((A & B) | C)
((A & B) | D)

例2:

((A | B) & (C | D))
output should be:
(A & C)
(A & D)
(B & C)
(B & D)

示例 3:

(A | B | C)
output should be :

(A)
(B)
(C)

注意:'|'表示'OR'而'&'表示'AND'，所以想把一个大条件分解成所有可能的最小真条件。

请建议...

Answer 1

因此，似乎有一种方法可以帮助您将表达式简化为积的总和。通过以乘积形式求和，您将拥有一系列不同的选项，如果其中包含的所有值都为真，则每个选项都是唯一正确的。

处理这个问题的一种方法是使用复合模式。我们将从 IExpression 开始界面:

public interface IExpression<T>
{
    int NumberOfPossibilities();

    IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities();
    IEnumerable<ValueExpression<T>> GetNthPossibility(int n);
}

这里的重点是第一个和最后一个方法。我们需要能够知道给定表达式有多少种可能性，以及获得第 N 种可能性的简单方法。最后一种方法的约定是，对于第 N 种可能性，所有给定值都必须为真。对于第二种方法，外部可枚举是所有要一起进行“或”运算的表达式，而每个内部表达式都需要一起进行“与”运算。

将有三个实现。 ValueExpression只代表一个值，一个 AndExpression表示 ANDing N 表达式，以及 OrExpression表示对 N 个表达式进行 ORing。

Value 是最容易实现的:

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 };
    }
}

And 表达式有点复杂。 AND 表达式的可能性数是被 AND 运算的可能性数的乘积。

为了获得第 N 种可能性，你可以这样想:

从0开始；对于 0，结果需要将每个子表达式的第一种可能性与在一起。对于第一种可能性，我们将一个添加到第一个子表达式。每次 n 增加时，我们都会增加从第一个子表达式获得的排列。当我们通过它的计数时，它会回到零，下一个子表达式会增加一个。它基本上就像计数，但每个数字代表一个子表达式，而该数字的基数是该子表达式的可能性的计数。

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;
        }
    }
}

对于 OR 表达式，它类似于 AND 版本，但仍然不同。

可能性的数量是总和，而不是内部表达式计数的乘积。

为了获得第 n 种可能性，我们只从子表达式之一的一种可能性中返回项目，而不是像 AND 那样从每种可能性中返回一个项目。

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

这是一个将表达式打印为字符串的简单函数:

public static void PrintPossibilities<T>(IExpression<T> expression)
{
    Console.WriteLine(string.Join(" + ", expression.Possibilities()
            .Select(possibility =>
                string.Concat(possibility.Select(value => value.Value)))));
}

请注意，这不处理解析表达式，只是在解析后处理它。

这是对您的第一个示例的测试:

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

打印:

ABC + ABD

AB 更改为 OR 表达式(您的第二个示例)打印:

AC + BC + AD + BD

您的第三个选项可以表示为:

var third = new OrExpression<string>(new[]{
    new ValueExpression<string>("A"),
    new ValueExpression<string>("B"),
    new ValueExpression<string>("C")});

打印出来的结果是:

A + B + C