用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}，有兴趣的看官口算试试 :)

推荐阅读

match
检查在所有可能的“？”替换中，给定的二进制字符串中是否出现子字符串“10”带 1 或 0

检查在所有可能的“？”替换中，给定的二进制字符串中是否出现子字符串“10”带 1 或 0 ... [详细]

蜡笔小新 2024-11-12 11:35:01
function
在范围[0..n-1]中产生m个不同的随机数 - Generating m distinct random numbers in the range [0..n-1]

Ihavetwomethodsofgeneratingmdistinctrandomnumbersintherange[0..n-1]我有两种方法在范围[0.n-1]中生 ... [详细]

蜡笔小新 2024-11-13 09:49:14
int
提升视觉效果：Unity3D中的HDR与Bloom技术（高动态范围成像与光线散射）

提升视觉效果：Unity3D中的HDR与Bloom技术（高动态范围成像与光线散射） ... [详细]

蜡笔小新 2024-11-10 10:16:00
int
求助：如何使用Pull方法解析标签内容，悬赏50分求完美解决方案

在处理 XML 数据时，如果需要解析 `` 标签的内容，可以采用 Pull 解析方法。Pull 解析是一种高效的 XML 解析方式，适用于流式数据处理。具体实现中，可以通过 Java 的 `XmlPullParser` 或其他类似的库来逐步读取和解析 XML 文档中的 `` 元素。这样不仅能够提高解析效率，还能减少内存占用。本文将详细介绍如何使用 Pull 解析方法来提取 `` 标签的内容，并提供一个示例代码，帮助开发者快速解决问题。 ... [详细]

蜡笔小新 2024-11-09 11:50:14
int
（7）Python爬虫——爬取豆瓣电影Top250

利用python爬取豆瓣电影Top250的相关信息，包括电影详情链接,图片链接,影片中文名,影片外国名,评分,评价数,概况,导演,主演,年份,地区,类别这12项内容，然后将爬取的信息写入Exce ... [详细]

蜡笔小新 2024-11-13 11:35:24
php
c/c++常用代码doc,ppt,xls文件格式转PDF格式[转]

[转]doc,ppt,xls文件格式转PDF格式http:blog.csdn.netlee353086articledetails7920355确实好用。需要注意的是#import ... [详细]

蜡笔小新 2024-11-12 16:19:40
int
实验九：使用SharedPreferences存储简单数据

本实验旨在帮助学生理解和掌握使用SharedPreferences存储和读取简单数据的方法，包括程序参数和用户选项。 ... [详细]

蜡笔小新 2024-11-12 14:21:47
main
JavaAwtSwing笔记之 JComponent JLabel 的 setBorder(Border 边框) 用例

JComponentJLabel的setBorder前言用例2205262241前言setBorder(Border边框)实现自JComponentjava.awt.Insets ... [详细]

蜡笔小新 2024-11-12 13:48:19
int
如何在Java中使用DButils类

这期内容当中小编将会给大家带来有关如何在Java中使用DButils类，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。D ... [详细]

蜡笔小新 2024-11-12 13:46:11
int
大类|电阻器_使用Requests、Etree、BeautifulSoup、Pandas和Path库进行数据抓取与处理 | 将指定区域内容保存为HTML和Excel格式

大类|电阻器_使用Requests、Etree、BeautifulSoup、Pandas和Path库进行数据抓取与处理 | 将指定区域内容保存为HTML和Excel格式 ... [详细]

蜡笔小新 2024-11-11 19:05:59
int
如何将TS文件转换为M3U8直播流：HLS与M3U8格式详解

在视频传输领域，MP4虽然常见，但在直播场景中直接使用MP4格式存在诸多问题。例如，MP4文件的头部信息（如ftyp、moov）较大，导致初始加载时间较长，影响用户体验。相比之下，HLS（HTTP Live Streaming）协议及其M3U8格式更具优势。HLS通过将视频切分成多个小片段，并生成一个M3U8播放列表文件，实现低延迟和高稳定性。本文详细介绍了如何将TS文件转换为M3U8直播流，包括技术原理和具体操作步骤，帮助读者更好地理解和应用这一技术。 ... [详细]

蜡笔小新 2024-11-11 12:12:04
express
Silverlight 实战指南：深入解析用户提交数据的验证与捕获机制

本文深入探讨了Silverlight中用户提交数据的验证与捕获机制，详细分析了四种主要的验证方法：基本异常处理、DataAnnotation注解、IDataErrorInfo客户端同步验证以及自定义验证策略。通过实例解析，帮助开发者更好地理解和应用这些机制，提升应用程序的数据处理能力和用户体验。 ... [详细]

蜡笔小新 2024-11-11 10:04:39
express
如何在C#中通过选择ComboBox项从MySQL数据库中检索数据值

本文探讨了如何在C#应用程序中通过选择ComboBox项从MySQL数据库中检索数据值。具体介绍了在事件处理方法 `comboBox2_SelectedIndexChanged` 中可能出现的常见错误，并提供了详细的解决方案和优化建议，以确保数据能够正确且高效地从数据库中读取并显示在界面上。此外，还讨论了连接字符串的配置、SQL查询语句的编写以及异常处理的最佳实践，帮助开发者避免常见的陷阱并提高代码的健壮性。 ... [详细]

蜡笔小新 2024-11-07 19:18:29
express
SSH集成过程中常见问题及解决方案

在使用SSH框架进行项目开发时，经常会遇到一些常见的问题。例如，在Spring配置文件中配置AOP事务声明后，进行单元测试时可能会出现“No Hibernate Session bound to thread”的错误。本文将详细探讨这一问题的原因，并提供有效的解决方案，帮助开发者顺利解决此类问题。 ... [详细]

蜡笔小新 2024-11-07 03:17:49
express
深入理解 Java 控制结构的全面指南

深入理解 Java 控制结构的全面指南 ... [详细]

蜡笔小新 2024-11-06 16:40:43

谁的板砖在飞

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

Tags | 热门标签

RankList | 热门文章