我试着用不同的关键字搜索,但没有发现任何有用的东西。我甚至不确定“多项式”在这里是否正确,请告知。
我正在尝试寻找递归算法(理想情况下在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]]
}
最佳答案
穿过树。
只要找到包含“+”节点的“*”节点,就用展开的形式替换该子树。
获取“+”节点的子节点列表,并将“*”节点替换为新的“+”,其中每个子节点在原始“*”节点的所有其他子节点和“+”节点的一个子节点之间都是“*”。
因为无论何时展开,都会将“*”节点向下推到树上,因为树是有限的,所以它最终会结束。
您可以扩展该算法以获取任何其他类似的扩展。