Come convertire la seguente procedura di valutazione del nodo in una soluzione non ricorsiva?

Stai facendo una ricerca in ampiezza. C'è tipicamente un modo per avvicinarsi a questo: ricorsivo e non ricorsivo. Qui puoi trovare uno pseudo codice per un algoritmo non ricorsivo:

link

Ovviamente dovrai personalizzarlo per le tue esigenze, ma in realtà non cambierà il principio.

Aggiorna

Ben Aaronson ha ragione (commento sotto). Questo non è prima di tutto. È il primo in profondità:

link

Ci scusiamo per la confusione.

UPDATE 2

I think this also doesn't really address OP's problem, which is that what to do with each node depends on its parent, so you can't just push the individual nodes to the stack Ben Aaronson

Non sono d'accordo. L'attraversamento dell'albero e la valutazione possono essere separati l'uno dall'altro. Ecco come lo fai:

IEnumerable<Node> PostOrderDFS(Node root)
{
  ...
}

Nota che in DFS post ordine i bambini precedono direttamente il genitore. Una possibile implementazione è qui:

link

L'unica cosa che devi modificare qui è il tipo di ritorno e creare un yield return invece di Console.Write .

La valutazione sarebbe simile a questa:

bool Evaluate(Node root)
{
  List<Tuple<Node, bool>> traverseList = PostOrderDFS(root).Select(n => Tuple.Create(n, false)).ToList();
  for(int i = 0; i < traverseList.Count; ++i)
  {
    Tuple<Node, bool> tuple = traverseList[i];
    Node node = tuple.Item1;
    switch(node.Type)
    {
    case AND_OPERATOR:
        tuple.Item2 = true;
        foreach(int j = 1; j <= node.Childrens.Count; ++j)
        {
            bool childresult = traverseList[i-j].Item2;
            tuple.Item2 = tuple.Item2 && childresult;
        }
    case OR_OPERATOR:
        tuple.Item2 = false;
        foreach(int j = 1; j <= node.Childrens.Count; ++j)
        {
            bool childresult = traverseList[i-j].Item2;
            tuple.Item2 = tuple.Item2 || childresult;
        }
    case VALUE:
        tuple.Item2 = node.Value;
    }
  }

  return traverseList.Last().Item2;
}

Voglio provare a dare una risposta generale. Poiché la ricorsione è , infatti, utilizzando uno stack (lo stack di chiamate), qualsiasi funzione ricorsiva può essere convertita in una iterativa usando una pila in modo diretto. Puoi semplicemente simulare lo stack di chiamate:

Lo stack di chiamate contiene:

• gli argomenti
• l'indirizzo di ritorno
• e le variabili locali.

Crea una struttura per questi:

struct Context {
    Arguments args;
    LocalVars lvars;
    ExecutionState state;
}

Arguments è semplice: gli argomenti sono impostati sui valori degli argomenti per la chiamata ricorsiva.

La parte difficile è "l'indirizzo di ritorno" o come ho chiamato qui ExecutionState e LocalVars .

ExecutionState dovrebbe tenere traccia di dove è stata effettuata la chiamata, per riprendere l'esecuzione dopo il ritorno della "chiamata ricorsiva". Nel tuo esempio, ci sono 3 possibili stati:

• valutare
• restituito dalla prima chiamata
• restituito dalla seconda chiamata

LocalVars include result e Children ciclo iteratore. Poiché una chiamata viene effettuata all'interno del ciclo, deve essere interrotta e ripresa in seguito, quindi anche l'iteratore del ciclo deve essere in pila.

Aggiornamento: qui ho scritto una versione pseudocodice C ++ / # non testata. L'OP (@tigrou) ha corretto alcuni errori e ha creato una versione C # funzionante, che mi ha permesso di includere qui:

enum ExecutionState
{
    S_EVAL,
    S_CALL1,
    S_CALL2 
};

enum NodeType
{
    AND_OPERATOR,
    OR_OPERATOR,
    VALUE   
};

class LocalVars 
{
    public IEnumerator<Node> Enumerator;
    public bool Result;
}

class Context
{
    public Node Node;       
    public LocalVars LocalVariables;        
    public ExecutionState State;

    public Context(Node node, ExecutionState state)
    {
        this.Node = node;
        this.State = state;
        this.LocalVariables = new LocalVars();
    }
};

class Node
{
    public bool Value;          
    public NodeType Type;
    public List<Node> Childrens;
};

static bool EvaluateNode(Node node)
{
    Stack<Context> stack = new Stack<Context>();
    Context context = new Context(node, ExecutionState.S_EVAL);            
    stack.Push(context);

    bool returnresult = false;
    while(stack.Any())
    {
        context = stack.Pop();
        switch(context.State)
        {
            case ExecutionState.S_EVAL:
                switch(context.Node.Type)
                {
                    case NodeType.AND_OPERATOR:
                        if(context.LocalVariables.Enumerator == null) 
                        {
                            context.LocalVariables.Enumerator = context.Node.Childrens.GetEnumerator();
                            context.LocalVariables.Result = true;
                        }

                        if(context.LocalVariables.Enumerator.MoveNext())
                        {
                            context.State = ExecutionState.S_CALL1;
                            stack.Push(context);        // push resume with S_CALL1

                            Context call = new Context(context.LocalVariables.Enumerator.Current, ExecutionState.S_EVAL);                                                  
                            stack.Push(call);           // push call
                        } 
                        else
                        {
                            returnresult = context.LocalVariables.Result;    // no push -> return
                        }
                        break;

                    case NodeType.OR_OPERATOR:
                        if(context.LocalVariables.Enumerator == null) 
                        {
                            context.LocalVariables.Enumerator = context.Node.Childrens.GetEnumerator();
                            context.LocalVariables.Result = false;
                        }

                        if(context.LocalVariables.Enumerator.MoveNext())
                        {
                            context.State = ExecutionState.S_CALL2;
                            stack.Push(context);        // push resume with S_CALL2

                            Context call = new Context(context.LocalVariables.Enumerator.Current, ExecutionState.S_EVAL);                                                  
                            stack.Push(call);           // push call
                        } 
                        else
                        {
                            returnresult = context.LocalVariables.Result;    // no push -> return
                        }
                        break;

                    case NodeType.VALUE:
                        returnresult = context.Node.Value;  // no push -> return
                        break;
                }
                break;

            case ExecutionState.S_CALL1:
                context.LocalVariables.Result = context.LocalVariables.Result && returnresult;
                context.State = ExecutionState.S_EVAL;
                stack.Push(context);                        // continue with S_EVAL
                break;

            case ExecutionState.S_CALL2:
                context.LocalVariables.Result = context.LocalVariables.Result || returnresult;
                context.State = ExecutionState.S_EVAL;
                stack.Push(context);                        // continue with S_EVAL
                break;
        }
    }

    return returnresult;
}

Il problema di valutare le espressioni aritmetiche in modo non ricorsivo è stato risolto e pubblicato per la prima volta oltre 50 anni fa. Stai cercando l'algoritmo Dijkstra di smistamento. L' articolo di Wikipedia ha un'ottima descrizione dell'algoritmo e ci sono decine di migliaia di risultati in Google, tra cui un articolo sui programmi di letteratura fa un buon lavoro di combinazione di descrizione e implementazione.

Ecco la soluzione migliore che ho ricevuto finora. È basato sulla risposta di Gábor Angyal.

È leggermente diverso dalla sua implementazione, quindi lo metto qui nel caso in cui sarebbe utile per qualcuno. Si noti che utilizza ancora la ricorsività, perché è implementato GetNodesDFS (). L'ho fatto in questo modo perché l'implementazione basata su stack per DFS traversal non è banale da scrivere e revisionare il codice (manutenzione).

Alla fine preferisco quella soluzione dall'esempio ricorsivo iniziale in OP, perché la parte ricorsiva è separata dal ciclo principale che si occupa della valutazione del nodo. Il codice reale è molto più complesso di questi esempi, e usando la ricorsività come nell'OP, ho dovuto passare molte variabili per ogni chiamata ricorsiva (che non è un problema qui)

nodesDFS = GetNodesDFS(nodes, x => x.Childrens.Reverse());
foreach(Node node in nodesDFS)
{
    switch(node.Type)
    {
        case AND_OPERATOR:
            result = true;
            for(i = 0 ; i < node.Childrens.Count ; i++)
            {
                result = result && results.Pop();
            }   
            results.Push(result);
        case OR_OPERATOR:
            result = false;
            for(i = 0 ; i < node.Childrens.Count ; i++)
            {
                result = result || results.Pop();
            }    
            results.Push(result);       
        case VALUE:
            results.Push(node.Value); 
    }        
}
finalresult = evaluatedNodes.Pop();

GetNodesDFS () è implementato in questo modo (vedi nota sopra):

GetNodesDFS(source, descendby)
{
   foreach (value in source)
   {
       foreach (child in descendby(value).GetNodesDFS(descendBy))
       {
           yield return child;
       }
       yield return value;
   }
}