我试着用不同的关键字搜索,但没有发现任何有用的东西。我甚至不确定“多项式”在这里是否正确,请告知。
我正在尝试寻找递归算法(理想情况下在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]]
}

最佳答案

穿过树。
只要找到包含“+”节点的“*”节点,就用展开的形式替换该子树。
获取“+”节点的子节点列表,并将“*”节点替换为新的“+”,其中每个子节点在原始“*”节点的所有其他子节点和“+”节点的一个子节点之间都是“*”。
因为无论何时展开,都会将“*”节点向下推到树上,因为树是有限的,所以它最终会结束。
您可以扩展该算法以获取任何其他类似的扩展。

10-06 00:58