Алгоритм преобразования дерева выражений в полиномиальную форму

Question

Я попытался выполнить поиск с использованием разных ключевых слов, но не нашел ничего полезного. Я даже не уверен, что «Полиномиальный» здесь правильный термин, пожалуйста, сообщите.

Я пытаюсь найти рекурсивный алгоритм (в идеале на C#) для преобразования/расширения моего дерева выражений в упрощенную стандартную (полиномиальную, я думаю) форму. Например:

Входной сигнал:

(Х1 + Х2 + Х3 * Х4) * Х5 + Х6

Выход:

X1 * Х5 + 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]] 
} 

Answer 1

Перейти через дерево.

Всякий раз, когда вы обнаруживаете узел «*», содержащий узел «+», замените это поддерево на расширенную форму.

Вы берете список дочерних узлов узла «+» и заменяете узел «*» новым «+», где каждый ребенок является «*» между всеми другими дочерними элементами исходного «*» узла и одним детей узла «+».

Поскольку всякий раз, когда вы расширяете, вы нажимаете «*» узел вниз по дереву, в конце концов оно заканчивается, так как ваше дерево конечное.

Вы можете расширить алгоритм, чтобы выбрать любое другое подобное расширение, которое вы хотели бы.