算法转换表达式树到多项式形式

本文关键字:多项式 转换 表达式 算法 | 更新日期: 2023-09-27 18:13:56

我试着用不同的关键词搜索,但没有找到任何有用的东西。我甚至不确定"多项式"在这里是正确的,请告诉我。

我试图找到递归算法(理想情况下c#)转换/扩展我的表达式树简化标准(多项式,我猜)形式。例如:

输入:

(X1 + X2 + X3 * X4) * X5和X6

输出:

X1*X5 + X2*X5 + X3*X4*X5 + X6

我有一组源类:

public abstract class Expr
{ 
    public static Op Op(string operatorName, params Expr[] children)
    {
        var res = new Op() { Operator = operatorName };
        res.Children.AddRange(children);
        return res;
    }
    public static Var Var(string valName)
    {
        var res = new Var(){ Name = valName};
        return res;
    }
}
public class Op:Expr
{
    public string Operator { get; set; }
    public List<Expr> Children = new List<Expr>();
}
public class Var:Expr
{
    public string Name { get; set; }
}

我需要实现以下方法:

public static IEnumerable<IEnumerable<Var>> SimplifyToPolynom(Expr expression)
{
    throw new NotImplementedException();
}
//USE CASE:
public static void Test()
{
    //(X1+X2+X3*X4)*X5+X6
    var inputExpression =
        Expr.Op("+",
            Expr.Op("*"
                , Expr.Op("+"
                    , Expr.Var("X1")
                    , Expr.Var("X2")
                    , Expr.Op("*"
                        , Expr.Var("X3")
                        , Expr.Var("X4")
                            )
                          )
                , Expr.Var("X5")
                    )
            , Expr.Var("X6")
        );
    var output = SimplifyToPolynom(inputExpression);
    // Exected result [[X1,X5],[X2,X5], [X3,X4,X5], [X6]]
}

算法转换表达式树到多项式形式

遍历树。

当您发现包含"+"节点的"*"节点时,将该子树替换为展开的形式。

取"+"节点的子节点列表,并将"*"节点替换为新的"+",其中每个子节点都是原始"*"节点的所有其他子节点和"+"节点的一个子节点之间的"*"。

因为无论何时展开,你都将"*"节点向下推,它最终会结束,因为你的树是有限的。

您可以扩展该算法以获取您想要的任何其他类似的展开