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

作者：谁的板砖在飞 | 来源：互联网 | 2023-09-24 17:39

思路：一共4个数字，共需要3个运算符，可以构造一个二叉树，没有子节点的节点的为值，有叶子节点的为运算符例如数字{1,2,3,4}，其中一种解的二叉树形式如下所示：因此可以遍历所有二叉树可能的形式

思路：一共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 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> operators)
{
    var iNum = 0;
    var iOprt = 0;

    Func 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> FullPermute(List elements)
{
    if (elements.Count == 1)
        return EnumerableOfOneElement(elements);

    IEnumerable> result = null;
    foreach (T first in elements)
    {
        List remaining = elements.ToArray().ToList();
        remaining.Remove(first);
        IEnumerable> fullPermuteOfRemaining = FullPermute(remaining);

        foreach (List permute in fullPermuteOfRemaining)
        {
            var arr = new List { first };
            arr.AddRange(permute);

            var seq = EnumerableOfOneElement(arr);
            if (result == null)
                result = seq;
            else
                result = result.Union(seq);
        }
    }
    return result;
}

static IEnumerable EnumerableOfOneElement(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>> OperatorPermute(List> 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> {
        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.Lambdadouble>>(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

对于一些平时口算相对稍难的一些组合也是毫无压力，例如{1, 5, 5, 5}， {3, 3, 7, 7}， {3, 3, 8, 8}，有兴趣的看官口算试试 :)

推荐阅读

format
C#学习教程：在Console中工作但在Windows窗体中不工作的异步代码分享

本文分享了一个关于在C#中使用异步代码的问题，作者在控制台中运行时代码正常工作，但在Windows窗体中却无法正常工作。作者尝试搜索局域网上的主机，但在窗体中计数器没有减少。文章提供了相关的代码和解决思路。 ... [详细]

蜡笔小新 2023-12-14 15:56:00
ip
C# 7.0 新特性：基于Tuple的“多”返回值方法

本文介绍了C# 7.0中基于Tuple的“多”返回值方法的使用。通过对C# 6.0及更早版本的做法进行回顾，提出了问题：如何使一个方法可返回多个返回值。然后详细介绍了C# 7.0中使用Tuple的写法，并给出了示例代码。最后，总结了该新特性的优点。 ... [详细]

蜡笔小新 2023-12-13 19:55:20
get
关于Linq to sql 实现模糊查询 string数组

前景：当UI一个查询条件为多项选择，或录入多个条件的时候，比如查询所有名称里面包含以下动态条件，需要模糊查询里面每一项时比如是这样一个数组条件：newstring[]{兴业银行, ... [详细]

蜡笔小新 2023-12-13 09:34:59
default
Java学习笔记之面向对象编程（OOP）

本文介绍了Java学习笔记中的面向对象编程（OOP）内容，包括OOP的三大特性（封装、继承、多态）和五大原则（单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则）。通过学习OOP，可以提高代码复用性、拓展性和安全性。 ... [详细]

蜡笔小新 2023-12-13 08:44:30
get
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
get
Spring特性实现接口多类的动态调用详解

本文详细介绍了如何使用Spring特性实现接口多类的动态调用。通过对Spring IoC容器的基础类BeanFactory和ApplicationContext的介绍，以及getBeansOfType方法的应用，解决了在实际工作中遇到的接口及多个实现类的问题。同时，文章还提到了SPI使用的不便之处，并介绍了借助ApplicationContext实现需求的方法。阅读本文，你将了解到Spring特性的实现原理和实际应用方式。 ... [详细]

蜡笔小新 2023-12-14 03:24:19
get
关于cuowu类的错误提示和使用AdjustmentListener的问题

本文讨论了一个关于cuowu类的问题，作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案，并给出了两个可能导致错误的原因。 ... [详细]

蜡笔小新 2023-12-13 22:09:56
java
从零学Java（10）之方法详解，喷打野你真的没我6！

本文介绍了从零学Java系列中的第10篇文章，详解了Java中的方法。同时讨论了打野过程中喷打野的影响，以及金色打野刀对经济的增加和线上队友经济的影响。指出喷打野会导致线上经济的消减和影响队伍的团结。 ... [详细]

蜡笔小新 2023-12-13 13:44:16
java
集合的遍历方式及其局限性

本文介绍了Java中集合的遍历方式，重点介绍了for-each语句的用法和优势。同时指出了for-each语句无法引用数组或集合的索引的局限性。通过示例代码展示了for-each语句的使用方法，并提供了改写为for语句版本的方法。 ... [详细]

蜡笔小新 2023-12-12 15:34:14
get
Express App如何提供不需要的静态文件？

本文介绍了如何使用Express App提供静态文件，同时提到了一些不需要使用的文件，如package.json和/.ssh/known_hosts，并解释了为什么app.get('*')无法捕获所有请求以及为什么app.use(express.static(__dirname))可能会提供不需要的文件。 ... [详细]

蜡笔小新 2023-12-12 14:38:07
get
引擎之旅 Chapter.2 线程库

预备知识可参考我整理的博客Windows编程之线程:https:www.cnblogs.comZhuSenlinp16662075.htmlWindows编程之线程同步:https ... [详细]

蜡笔小新 2023-12-12 14:06:39
get
java boolean 大小_java boolean 大小

先看官方文档TheJavaTutorialshavebeenwrittenforJDK8.Examplesandpracticesdescribedinthispagedontta ... [详细]

蜡笔小新 2023-12-12 13:36:56
header
PHP二维数组根据某个字段排序的方法

本文介绍了一种在PHP中对二维数组根据某个字段进行排序的方法，以年龄字段为例，按照倒序的方式进行排序，并给出了具体的代码实现。 ... [详细]

蜡笔小新 2023-12-11 10:56:01
format
C# Word模版打印方案详解

本文详细介绍了使用C#实现Word模版打印的方案。包括添加COM引用、新建Word操作类、开启Word进程、加载模版文件等步骤。通过该方案可以实现C#对Word文档的打印功能。 ... [详细]

蜡笔小新 2023-12-10 14:09:00
get
数组或散列中的正则表达式排序 - Regex in array or hash - sorting

Ihaveaworkfolderdirectory.我有一个工作文件夹目录。holderDir.glob(*)>holder[ProjectOne, ... [详细]

蜡笔小新 2023-12-10 12:41:53

谁的板砖在飞

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章