算法转换表达式树到多项式形式
本文关键字:多项式 转换 表达式 算法 | 更新日期: 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]]
}
遍历树。
当您发现包含"+"节点的"*"节点时,将该子树替换为展开的形式。
取"+"节点的子节点列表,并将"*"节点替换为新的"+",其中每个子节点都是原始"*"节点的所有其他子节点和"+"节点的一个子节点之间的"*"。
因为无论何时展开,你都将"*"节点向下推,它最终会结束,因为你的树是有限的。
您可以扩展该算法以获取您想要的任何其他类似的展开