Come determinare la profondità di un albero di espressione C# Iterativly?

Question

Sto cercando di capire se c'è un buon modo per capire la profondità di un particolare albero di espressione C# usando un approccio iterativo. Usiamo le espressioni per alcune valutazioni dinamiche e in rare condizioni (di errore), il sistema può provare a elaborare un albero delle espressioni che è così grande da far esplodere lo stack. Sto cercando di capire un modo per controllare la profondità dell'albero prima di consentire la valutazione dell'albero.

Answer 1

Il ExpressionVisitor che è incluso in NET è ricorsiva, ma utilizzando un trucco, è possibile trasformarlo in un iterativo.

Fondamentalmente, si sta elaborando una coda di nodi. Per ciascun nodo della coda, utilizzare base.Visit() per visitare tutti i relativi elementi secondari, ma aggiungere tali figli nella coda anziché elaborarli in modo ricorsivo immediatamente.

In questo modo, non è necessario scrivere codice specifico per ogni sottotipo Expression, ma si aggira anche la natura ricorsiva di 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

Piuttosto che cercare di risolvere specificamente il problema per gli alberi di espressione, permettetemi di descrivere alcune tecniche generali per gestire gli alberi mal funzionanti.

Si potrebbe voler iniziare leggendo la mia serie di articoli sulla soluzione del problema che si pongono: come determinare la profondità di un albero senza ricorrere alla ricorsione?

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

Tali articoli sono stati scritti indietro quando stavo lavorando su JScript, quindi gli esempi sono in JScript. Non è troppo difficile vedere come applicare questi concetti a C# però.

Lasciatemi fare un piccolo esempio di esempio in C# su come eseguire un'operazione su una struttura dati ricorsiva senza eseguire una ricorsione completa. Supponiamo di avere la seguente albero binario: (Supponiamo WOLOG che i nodi della struttura binari sono o zero o due figli, non esattamente un.)

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, "-"); 

Così abbiamo l'albero p4:

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

e ci auguriamo di stampare p4 come un'espressione tra parentesi

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

La soluzione ricorsiva è semplice:

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(")"); 
     } 
} 

Ora supponiamo di sapere che l'albero è probabilmente "profondo" a sinistra, ma "poco profondo" a destra. Possiamo eliminare la ricorsione a sinistra?

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(")"); 
     } 
    } 
} 

La recurse-on-the-destra unica versione è, naturalmente, molto più difficile da leggere e molto più difficile ragionare su, ma non soffia la pila.

Esaminiamo il nostro esempio.

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. 

E cosa produciamo? (((1+2)*3)-(4+5)), come desiderato.

Quindi hai visto qui che posso passare da due ricorsi a uno. Possiamo usare tecniche simili per passare da una ricorsione a nessuna. Rendere questo algoritmo completamente iterativo, in modo che non ricorra né a sinistra né a destra, viene lasciato come esercizio.

(E per inciso: Posso fare una variante di questo problema come una questione intervista, quindi se mai intervistato da me, ora avete un vantaggio sleale!)

Answer 3

Invece di utilizzare la ricorsione per iterare un albero si può sempre usare una struttura esplicita nella memoria. Se vuoi imitare da vicino il comportamento ricorsivo, puoi anche usare un esplicito Stack.Dato che questo sta memorizzando tutte le informazioni sui nodi ancora da elaborare nell'heap, ci vorrà molto di più per esaurirle.

Ecco un metodo per scopi generali che attraversa una struttura ad albero (in modo iterativo, non in modo ricorsivo) e restituisce una sequenza appiattita di tutti gli elementi insieme alla profondità di quell'elemento.

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)); 
     } 
    } 
} 

Ora per utilizzare questo tutto quello che dobbiamo fare è passare il nodo principale (s), una funzione che mappa ogni elemento ai suoi figli diretti, e quindi siamo in grado di prendere il massimo della profondità. A causa dell'esecuzione posticipata, ogni elemento reso dalla funzione trasversale non verrà mantenuto in memoria da Max, quindi gli unici elementi conservati in memoria sono i nodi che non sono stati elaborati, ma che hanno avuto un genitore che è stato elaborato.

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