用C#表达式树优雅的计算24点

你的名字 2022-08-13 19:47 116阅读 0赞

原文：[http://www.2cto.com/kf/201410/343836.html][http_www.2cto.com_kf_201410_343836.html]

思路：一共4个数字，共需要3个运算符，可以构造一个二叉树，没有子节点的节点的为值，有叶子节点的为运算符

例如数字\{1, 2, 3, 4\}，其中一种解的二叉树形式如下所示：

因此可以遍历所有二叉树可能的形式，4个数的全排列，从4种运算符中挑选3种运算符（运算符可以重复）

核心步骤1：需要遍历所有二叉树的可能，参考Eric Lippert的方法

class Node
    {
        public Node Left { get; private set; }
        public Node Right { get; private set; }
        public Node(Node left, Node right)
        {
            this.Left = left;
            this.Right = right;
        }
    }

static IEnumerable<Node> AllBinaryTrees(int size)
    {
        if (size == 0)
            return new Node[] { null };
        return from i in Enumerable.Range(0, size)
                from left in AllBinaryTrees(i)
                from right in AllBinaryTrees(size - 1 - i)
                select new Node(left, right);
    }

核心步骤2：对于任意一个二叉树，构造表达式树

static Expression Build(Node node, List<double> numbers, List<Func<Expression, Expression, BinaryExpression>> operators)
    {
        var iNum = 0;
        var iOprt = 0;
     
        Func<Node, Expression> f = null;
        f = n =>
        {
            Expression exp;
            if (n == null)
                exp = Expression.Constant(numbers[iNum++]);
            else
            {
                var left = f(n.Left);
                var right = f(n.Right);
                exp = operators[iOprt++](left, right);
            }
            return exp;
        };
        return f(node);
    }

核心步骤3：遍历4个数字的全排列，全排列参考这里

static IEnumerable<List<T>> FullPermute<T>(List<T> elements)
    {
        if (elements.Count == 1)
            return EnumerableOfOneElement(elements);
     
        IEnumerable<List<T>> result = null;
        foreach (T first in elements)
        {
            List<T> remaining = elements.ToArray().ToList();
            remaining.Remove(first);
            IEnumerable<List<T>> fullPermuteOfRemaining = FullPermute(remaining);
     
            foreach (List<T> permute in fullPermuteOfRemaining)
            {
                var arr = new List<T> { first };
                arr.AddRange(permute);
     
                var seq = EnumerableOfOneElement(arr);
                if (result == null)
                    result = seq;
                else
                    result = result.Union(seq);
            }
        }
        return result;
    }
     
    static IEnumerable<T> EnumerableOfOneElement<T>(T element)
    {
        yield return element;
    }

例如有四个数字\{1, 2, 3, 4\}，它的全排列如下：

1, 2, 3, 4
    1, 2, 4, 3
    1, 3, 2, 4
    1, 3, 4, 2
    1, 4, 2, 3
    1, 4, 3, 2
    2, 1, 3, 4
    2, 1, 4, 3
    2, 3, 1, 4
    2, 3, 4, 1
    2, 4, 1, 3
    2, 4, 3, 1
    3, 1, 2, 4
    3, 1, 4, 2
    3, 2, 1, 4
    3, 2, 4, 1
    3, 4, 1, 2
    3, 4, 2, 1
    4, 1, 2, 3
    4, 1, 3, 2
    4, 2, 1, 3
    4, 2, 3, 1
    4, 3, 1, 2
    4, 3, 2, 1

核心步骤4：从4种运算符中挑选3个运算符

static IEnumerable<IEnumerable<Func<Expression, Expression, BinaryExpression>>> OperatorPermute(List<Func<Expression, Expression, BinaryExpression>> operators)
    {
        return from operator1 in operators
                from operator2 in operators
                from operator3 in operators
                select new[] { operator1, operator2, operator3 };
    }

最后是Main函数：

static void Main(string[] args)
    {
        List<double> numbers = new List<double> { 1, 2, 3, 4 };
        var operators = new List<Func<Expression, Expression, BinaryExpression>> {
            Expression.Add,Expression.Subtract,Expression.Multiply,Expression.Divide 
        };
     
        foreach (var operatorCombination in OperatorPermute(operators))
        {
            foreach (Node node in AllBinaryTrees(3))
            {
                foreach (List<double> permuteOfNumbers in FullPermute(numbers))
                {
                    Expression expression = Build(node, permuteOfNumbers, operatorCombination.ToList());
                    Func<double> compiled = Expression.Lambda<Func<double>>(expression).Compile();
                    try
                    {
                        var value = compiled();
                        if (Math.Abs(value - 24) < 0.01)
                            Console.WriteLine("{0} = {1}", expression, value);
                    }
                    catch (DivideByZeroException) { }
                }
            }
        }
        Console.Read();
    }

计算结果：

(4 * (1 + (2 + 3))) = 24
    (4 * (1 + (3 + 2))) = 24
    (4 * (2 + (1 + 3))) = 24
    (4 * (2 + (3 + 1))) = 24
    (4 * (3 + (1 + 2))) = 24
    (4 * (3 + (2 + 1))) = 24
    (4 * ((1 + 2) + 3)) = 24
    (4 * ((1 + 3) + 2)) = 24
    (4 * ((2 + 1) + 3)) = 24
    (4 * ((2 + 3) + 1)) = 24
    (4 * ((3 + 1) + 2)) = 24
    (4 * ((3 + 2) + 1)) = 24
    ((1 + 3) * (2 + 4)) = 24
    ((1 + 3) * (4 + 2)) = 24
    ((2 + 4) * (1 + 3)) = 24
    ((2 + 4) * (3 + 1)) = 24
    ((3 + 1) * (2 + 4)) = 24
    ((3 + 1) * (4 + 2)) = 24
    ((4 + 2) * (1 + 3)) = 24
    ((4 + 2) * (3 + 1)) = 24
    ((1 + (2 + 3)) * 4) = 24
    ((1 + (3 + 2)) * 4) = 24
    ((2 + (1 + 3)) * 4) = 24
    ((2 + (3 + 1)) * 4) = 24
    ((3 + (1 + 2)) * 4) = 24
    ((3 + (2 + 1)) * 4) = 24
    (((1 + 2) + 3) * 4) = 24
    (((1 + 3) + 2) * 4) = 24
    (((2 + 1) + 3) * 4) = 24
    (((2 + 3) + 1) * 4) = 24
    (((3 + 1) + 2) * 4) = 24
    (((3 + 2) + 1) * 4) = 24
    (1 * (2 * (3 * 4))) = 24
    (1 * (2 * (4 * 3))) = 24
    (1 * (3 * (2 * 4))) = 24
    (1 * (3 * (4 * 2))) = 24
    (1 * (4 * (2 * 3))) = 24
    (1 * (4 * (3 * 2))) = 24
    (2 * (1 * (3 * 4))) = 24
    (2 * (1 * (4 * 3))) = 24
    (2 * (3 * (1 * 4))) = 24
    (2 * (3 * (4 * 1))) = 24
    (2 * (4 * (1 * 3))) = 24
    (2 * (4 * (3 * 1))) = 24
    (3 * (1 * (2 * 4))) = 24
    (3 * (1 * (4 * 2))) = 24
    (3 * (2 * (1 * 4))) = 24
    (3 * (2 * (4 * 1))) = 24
    (3 * (4 * (1 * 2))) = 24
    (3 * (4 * (2 * 1))) = 24
    (4 * (1 * (2 * 3))) = 24
    (4 * (1 * (3 * 2))) = 24
    (4 * (2 * (1 * 3))) = 24
    (4 * (2 * (3 * 1))) = 24
    (4 * (3 * (1 * 2))) = 24
    (4 * (3 * (2 * 1))) = 24
    (1 * ((2 * 3) * 4)) = 24
    (1 * ((2 * 4) * 3)) = 24
    (1 * ((3 * 2) * 4)) = 24
    (1 * ((3 * 4) * 2)) = 24
    (1 * ((4 * 2) * 3)) = 24
    (1 * ((4 * 3) * 2)) = 24
    (2 * ((1 * 3) * 4)) = 24
    (2 * ((1 * 4) * 3)) = 24
    (2 * ((3 * 1) * 4)) = 24
    (2 * ((3 * 4) * 1)) = 24
    (2 * ((4 * 1) * 3)) = 24
    (2 * ((4 * 3) * 1)) = 24
    (3 * ((1 * 2) * 4)) = 24
    (3 * ((1 * 4) * 2)) = 24
    (3 * ((2 * 1) * 4)) = 24
    (3 * ((2 * 4) * 1)) = 24
    (3 * ((4 * 1) * 2)) = 24
    (3 * ((4 * 2) * 1)) = 24
    (4 * ((1 * 2) * 3)) = 24
    (4 * ((1 * 3) * 2)) = 24
    (4 * ((2 * 1) * 3)) = 24
    (4 * ((2 * 3) * 1)) = 24
    (4 * ((3 * 1) * 2)) = 24
    (4 * ((3 * 2) * 1)) = 24
    ((1 * 2) * (3 * 4)) = 24
    ((1 * 2) * (4 * 3)) = 24
    ((1 * 3) * (2 * 4)) = 24
    ((1 * 3) * (4 * 2)) = 24
    ((1 * 4) * (2 * 3)) = 24
    ((1 * 4) * (3 * 2)) = 24
    ((2 * 1) * (3 * 4)) = 24
    ((2 * 1) * (4 * 3)) = 24
    ((2 * 3) * (1 * 4)) = 24
    ((2 * 3) * (4 * 1)) = 24
    ((2 * 4) * (1 * 3)) = 24
    ((2 * 4) * (3 * 1)) = 24
    ((3 * 1) * (2 * 4)) = 24
    ((3 * 1) * (4 * 2)) = 24
    ((3 * 2) * (1 * 4)) = 24
    ((3 * 2) * (4 * 1)) = 24
    ((3 * 4) * (1 * 2)) = 24
    ((3 * 4) * (2 * 1)) = 24
    ((4 * 1) * (2 * 3)) = 24
    ((4 * 1) * (3 * 2)) = 24
    ((4 * 2) * (1 * 3)) = 24
    ((4 * 2) * (3 * 1)) = 24
    ((4 * 3) * (1 * 2)) = 24
    ((4 * 3) * (2 * 1)) = 24
    ((1 * (2 * 3)) * 4) = 24
    ((1 * (2 * 4)) * 3) = 24
    ((1 * (3 * 2)) * 4) = 24
    ((1 * (3 * 4)) * 2) = 24
    ((1 * (4 * 2)) * 3) = 24
    ((1 * (4 * 3)) * 2) = 24
    ((2 * (1 * 3)) * 4) = 24
    ((2 * (1 * 4)) * 3) = 24
    ((2 * (3 * 1)) * 4) = 24
    ((2 * (3 * 4)) * 1) = 24
    ((2 * (4 * 1)) * 3) = 24
    ((2 * (4 * 3)) * 1) = 24
    ((3 * (1 * 2)) * 4) = 24
    ((3 * (1 * 4)) * 2) = 24
    ((3 * (2 * 1)) * 4) = 24
    ((3 * (2 * 4)) * 1) = 24
    ((3 * (4 * 1)) * 2) = 24
    ((3 * (4 * 2)) * 1) = 24
    ((4 * (1 * 2)) * 3) = 24
    ((4 * (1 * 3)) * 2) = 24
    ((4 * (2 * 1)) * 3) = 24
    ((4 * (2 * 3)) * 1) = 24
    ((4 * (3 * 1)) * 2) = 24
    ((4 * (3 * 2)) * 1) = 24
    (((1 * 2) * 3) * 4) = 24
    (((1 * 2) * 4) * 3) = 24
    (((1 * 3) * 2) * 4) = 24
    (((1 * 3) * 4) * 2) = 24
    (((1 * 4) * 2) * 3) = 24
    (((1 * 4) * 3) * 2) = 24
    (((2 * 1) * 3) * 4) = 24
    (((2 * 1) * 4) * 3) = 24
    (((2 * 3) * 1) * 4) = 24
    (((2 * 3) * 4) * 1) = 24
    (((2 * 4) * 1) * 3) = 24
    (((2 * 4) * 3) * 1) = 24
    (((3 * 1) * 2) * 4) = 24
    (((3 * 1) * 4) * 2) = 24
    (((3 * 2) * 1) * 4) = 24
    (((3 * 2) * 4) * 1) = 24
    (((3 * 4) * 1) * 2) = 24
    (((3 * 4) * 2) * 1) = 24
    (((4 * 1) * 2) * 3) = 24
    (((4 * 1) * 3) * 2) = 24
    (((4 * 2) * 1) * 3) = 24
    (((4 * 2) * 3) * 1) = 24
    (((4 * 3) * 1) * 2) = 24
    (((4 * 3) * 2) * 1) = 24
    ((2 * (3 * 4)) / 1) = 24
    ((2 * (4 * 3)) / 1) = 24
    ((3 * (2 * 4)) / 1) = 24
    ((3 * (4 * 2)) / 1) = 24
    ((4 * (2 * 3)) / 1) = 24
    ((4 * (3 * 2)) / 1) = 24
    (((2 * 3) * 4) / 1) = 24
    (((2 * 4) * 3) / 1) = 24
    (((3 * 2) * 4) / 1) = 24
    (((3 * 4) * 2) / 1) = 24
    (((4 * 2) * 3) / 1) = 24
    (((4 * 3) * 2) / 1) = 24
    (2 * ((3 * 4) / 1)) = 24
    (2 * ((4 * 3) / 1)) = 24
    (3 * ((2 * 4) / 1)) = 24
    (3 * ((4 * 2) / 1)) = 24
    (4 * ((2 * 3) / 1)) = 24
    (4 * ((3 * 2) / 1)) = 24
    ((2 * 3) * (4 / 1)) = 24
    ((2 * 4) * (3 / 1)) = 24
    ((3 * 2) * (4 / 1)) = 24
    ((3 * 4) * (2 / 1)) = 24
    ((4 * 2) * (3 / 1)) = 24
    ((4 * 3) * (2 / 1)) = 24
    (((2 * 3) / 1) * 4) = 24
    (((2 * 4) / 1) * 3) = 24
    (((3 * 2) / 1) * 4) = 24
    (((3 * 4) / 1) * 2) = 24
    (((4 * 2) / 1) * 3) = 24
    (((4 * 3) / 1) * 2) = 24
    (2 / (1 / (3 * 4))) = 24
    (2 / (1 / (4 * 3))) = 24
    (3 / (1 / (2 * 4))) = 24
    (3 / (1 / (4 * 2))) = 24
    (4 / (1 / (2 * 3))) = 24
    (4 / (1 / (3 * 2))) = 24
    ((2 * 3) / (1 / 4)) = 24
    ((2 * 4) / (1 / 3)) = 24
    ((3 * 2) / (1 / 4)) = 24
    ((3 * 4) / (1 / 2)) = 24
    ((4 * 2) / (1 / 3)) = 24
    ((4 * 3) / (1 / 2)) = 24
    (2 * (3 * (4 / 1))) = 24
    (2 * (4 * (3 / 1))) = 24
    (3 * (2 * (4 / 1))) = 24
    (3 * (4 * (2 / 1))) = 24
    (4 * (2 * (3 / 1))) = 24
    (4 * (3 * (2 / 1))) = 24
    (2 * ((3 / 1) * 4)) = 24
    (2 * ((4 / 1) * 3)) = 24
    (3 * ((2 / 1) * 4)) = 24
    (3 * ((4 / 1) * 2)) = 24
    (4 * ((2 / 1) * 3)) = 24
    (4 * ((3 / 1) * 2)) = 24
    ((2 / 1) * (3 * 4)) = 24
    ((2 / 1) * (4 * 3)) = 24
    ((3 / 1) * (2 * 4)) = 24
    ((3 / 1) * (4 * 2)) = 24
    ((4 / 1) * (2 * 3)) = 24
    ((4 / 1) * (3 * 2)) = 24
    ((2 * (3 / 1)) * 4) = 24
    ((2 * (4 / 1)) * 3) = 24
    ((3 * (2 / 1)) * 4) = 24
    ((3 * (4 / 1)) * 2) = 24
    ((4 * (2 / 1)) * 3) = 24
    ((4 * (3 / 1)) * 2) = 24
    (((2 / 1) * 3) * 4) = 24
    (((2 / 1) * 4) * 3) = 24
    (((3 / 1) * 2) * 4) = 24
    (((3 / 1) * 4) * 2) = 24
    (((4 / 1) * 2) * 3) = 24
    (((4 / 1) * 3) * 2) = 24
    (2 * (3 / (1 / 4))) = 24
    (2 * (4 / (1 / 3))) = 24
    (3 * (2 / (1 / 4))) = 24
    (3 * (4 / (1 / 2))) = 24
    (4 * (2 / (1 / 3))) = 24
    (4 * (3 / (1 / 2))) = 24
    ((2 / (1 / 3)) * 4) = 24
    ((2 / (1 / 4)) * 3) = 24
    ((3 / (1 / 2)) * 4) = 24
    ((3 / (1 / 4)) * 2) = 24
    ((4 / (1 / 2)) * 3) = 24
    ((4 / (1 / 3)) * 2) = 24
    (2 / ((1 / 3) / 4)) = 24
    (2 / ((1 / 4) / 3)) = 24
    (3 / ((1 / 2) / 4)) = 24
    (3 / ((1 / 4) / 2)) = 24
    (4 / ((1 / 2) / 3)) = 24
    (4 / ((1 / 3) / 2)) = 24

[http_www.2cto.com_kf_201410_343836.html]: http://www.2cto.com/kf/201410/343836.html