Jak określić głębokość drzewa wyrażeń C#?

Question

Próbuję dowiedzieć się, czy istnieje dobry sposób, aby dowiedzieć się głębokości określonego drzewa wyrażeń C# za pomocą iteracyjne podejście. Używamy wyrażeń do oceny dynamicznej iw warunkach rzadkich (błędów), system może spróbować przetworzyć Drzewo Wyrażeń, które jest tak duże, że wydmuchuje stos. Próbuję znaleźć sposób sprawdzenia głębokości drzewa przed zezwoleniem na ocenę drzewa.

Answer 1

The ExpressionVisitor który jest zawarty w .NET jest rekurencyjna, ale stosując podstęp, można przekształcić go w jednej iteracji.

Zasadniczo przetwarzasz kolejkę węzłów. Dla każdego węzła w kolejce użyj base.Visit(), aby odwiedzić wszystkie jego elementy podrzędne, ale dodaj je do kolejki zamiast rekurencyjnie przetwarzaj je od razu.

W ten sposób nie musisz pisać kodu specyficznego dla każdego podtypu Expression, ale także pracujesz nad rekursywną naturą ExpressionVisitor.

class DepthVisitor : ExpressionVisitor 
{ 
    private readonly Queue<Tuple<Expression, int>> m_queue = 
     new Queue<Tuple<Expression, int>>(); 
    private bool m_canRecurse; 
    private int m_depth; 

    public int MeasureDepth(Expression expression) 
    { 
     m_queue.Enqueue(Tuple.Create(expression, 1)); 

     int maxDepth = 0; 

     while (m_queue.Count > 0) 
     { 
      var tuple = m_queue.Dequeue(); 
      m_depth = tuple.Item2; 

      if (m_depth > maxDepth) 
       maxDepth = m_depth; 

      m_canRecurse = true; 

      Visit(tuple.Item1); 
     } 

     return maxDepth; 
    } 

    public override Expression Visit(Expression node) 
    { 
     if (m_canRecurse) 
     { 
      m_canRecurse = false; 
      base.Visit(node); 
     } 
     else 
      m_queue.Enqueue(Tuple.Create(node, m_depth + 1)); 

     return node; 
    } 
} 

Answer 2

Zamiast próbować rozwiązać problem drzewek ekspresji, opiszę kilka ogólnych metod radzenia sobie z źle zachowanymi drzewami.

Możesz zacząć od przeczytania mojej serii artykułów na temat rozwiązania problemu: Jak określić głębokość drzewa bez użycia rekurencji?

http://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx

Artykuły te zostały napisane z powrotem, kiedy pracowałem na JScript, więc przykłady są w JScript. Nie jest jednak trudno zrozumieć, jak zastosować te koncepcje w języku C#.

Pozwól mi dać mały przykład zabawki w języku C#, jak wykonać operację na rekurencyjnej strukturze danych bez wykonywania pełnej rekursji. Załóżmy, że mamy następujące drzewo binarne: (Załóżmy WOLOG że drzewo binarne węzły są zero lub dwoje dzieci, nigdy dokładnie jeden.)

class Node 
{ 
    public Node Left { get; private set; } 
    public Node Right { get; private set; } 
    public string Value { get; private set; } 
    public Node(string value) : this(null, null, value) {} 
    public Node(Node left, Node right, string value) 
    { 
     this.Left = left; 
     this.Right = right; 
     this.Value = value; 
    } 
} 
... 
Node n1 = new Node("1"); 
Node n2 = new Node("2"); 
Node n3 = new Node("3"); 
Node n3 = new Node("4"); 
Node n5 = new Node("5"); 
Node p1 = new Node(n1, n2, "+"); 
Node p2 = new Node(p1, n3, "*"); 
Node p3 = new Node(n4, n5, "+"); 
Node p4 = new Node(p2, p3, "-"); 

Więc mamy P4 drzewa:

   - 
      / \ 
      *  + 
     /\ /\ 
      + 3 4 5 
     /\ 
     1 2 

i chcemy wydrukować P4 jako nawiasy ekspresji

(((1+2)*3)-(4+5)) 

rekurencyjne rozwiązanie jest proste:

static void RecursiveToString(Node node, StringBuilder sb) 
{ 
    // Again, assuming either zero or two children. 
    if (node.Left != null) 
     sb.Append(node.Value); 
    else 
    { 
     sb.Append("("); 
     RecursiveToString(node.Left, sb); 
     sb.Append(node.Value); 
     RecursiveToString(node.Right, sb); 
     sb.Append(")"); 
     } 
} 

Załóżmy teraz, że wiemy, że drzewo jest prawdopodobnie "głębokie" po lewej, ale "płytkie" po prawej. Czy możemy wyeliminować rekursję po lewej?

static void RightRecursiveToString(Node node, StringBuilder sb) 
{ 
    // Again, assuming either zero or two children. 
    var stack = new Stack<Node>(); 
    stack.Push(node); 
    while(stack.Peek().Left != null) 
    { 
     sb.Append("("); 
     stack.Push(stack.Peek().Left); 
    } 
    while(stack.Count != 0) 
    { 
     Node current = stack.Pop(); 
     sb.Append(current.Value); 
     if (current.Right != null) 
      RightRecursiveToString(current.Right, sb); 
      sb.Append(")"); 
     } 
    } 
} 

recurse-on-the-right tylko wersja jest oczywiście o wiele trudniejsze do odczytania i znacznie trudniejsze do rozumowania na temat, ale nie wieje cały stos.

Przejdźmy przez nasz przykład.

push p4 
push p2 
output (
push p1 
output (
push n1 
output (
loop condition is met 
pop n1 
output 1 
go back to the top of the loop 
pop p1 
output + 
recurse on n2 -- this outputs 2 
output) 
go back to the top of the loop 
pop p2 
output * 
recurse on n3 -- this outputs 3 
output) 
go back to the top of the loop 
pop p4 
output - 
recurse on p3 
    push p3 
    push n4 
    output (
    loop condition is met 
    pop n4 
    output 4 
    go back to the top of the loop 
    pop p3 
    output + 
    recurse on n5 -- this outputs 5 
    output) 
    loop condition is not met; return. 
output) 
loop condition is not met, return. 

Co produkujemy? (((1+2)*3)-(4+5)), zgodnie z potrzebami.

Widziałeś tutaj, że mogę przejść od dwóch rekursji do jednego. Możemy użyć podobnych technik, aby przejść od jednej rekursji do żadnej. Uczynienie tego algorytmu w pełni iteracyjnym - tak, aby nie powtórzyło się ani po lewej, ani po prawej - pozostawia się jako ćwiczenie.

(A nawiasem mówiąc: Pytam odmianę tego problemu jako pytanie wywiad, więc jeśli kiedykolwiek wywiad mnie, teraz mają nieuczciwą przewagę!)

Answer 3

Zamiast używać rekursji do iteracji drzewa cię zawsze może użyć jawnej struktury pamięci. Jeśli chcesz dokładnie naśladować zachowanie rekursywne, możesz użyć jawnego Stack.Ponieważ jest to przechowywanie wszystkich informacji o węzłach, które mają zostać przetworzone w stercie, potrzeba znacznie więcej, aby go zabrakło.

Oto metoda ogólnego przeznaczenia, która przechodzi przez strukturę drzewa (iteracyjnie, nie rekursywnie) i zwraca spłaszczoną sekwencję wszystkich elementów wraz z głębokością tego elementu.

public static IEnumerable<Tuple<T, int>> TraverseWithDepth<T>(IEnumerable<T> items 
    , Func<T, IEnumerable<T>> childSelector) 
{ 
    var stack = new Stack<Tuple<T, int>>(
     items.Select(item => Tuple.Create(item, 0))); 
    while (stack.Any()) 
    { 
     var next = stack.Pop(); 
     yield return next; 
     foreach (var child in childSelector(next.Item1)) 
     { 
      stack.Push(Tuple.Create(child, next.Item2 + 1)); 
     } 
    } 
} 

teraz korzystać z tego wszyscy musimy zrobić, to przejść do węzła głównego (-ych), funkcję, która odwzorowuje każdy element do swoich bezpośrednich dzieci, a potem możemy mieć max głębokości. Z powodu odroczonego wykonania, każdy element uzyskany przez funkcję ciągu nie zostanie zachowany w pamięci przez Max, więc jedynymi elementami przechowywanymi w pamięci są węzły, które nie zostały przetworzone, ale zostały przetworzone przez nadrzędnego.

public static int GetDepth(Expression t) 
{ 
    return TraverseWithDepth(new[] { t }, GetDirectChildren) 
     .Max(pair => pair.Item2); 
}