How to convert the following node evaluation procedure to a non recursive solution?

Question

I have the following recursive method.

It evaluates a node (that represent a logical expression), using deep first search traversal :

EvaluateNode(Node node)
{
    bool result;
    switch(node.Type)
    {
        case AND_OPERATOR:
            result = true;
            foreach(Node nodeChild in node.Childrens)
            {
                childresult = EvaluateNode(nodeChild);
                result = result && childresult;
            }
        case OR_OPERATOR:
            result = false;                
            foreach(Node nodeChild in node.Childrens)
            {
                childresult = EvaluateNode(nodeChild);
                result = result || childresult;
            }
        case VALUE:
            result = node.Value;
    }

    return result;
}

I'd like to convert this to a stack/queue based, non recursive solution. Here is what I tried so far (incomplete) :

bool result;
stack.Push(node);
while(!stack.Empty())
{
    Node node = stack.Pop();
    switch(node.Type)
    {
        case AND_OPERATOR:
            foreach(Node nodeChild in node.Childrens)
            {
                stack.Push(nodeChild);
            }   
        case OR_OPERATOR:
            foreach(Node nodeChild in node.Childrens)
            {
                stack.Push(nodeChild);
            }           
        case VALUE:
            result = node.Value;
    }
}

My guess is that I would need another stack for storing results but I have not been able to figure this out.

Answer 1

You are doing a Breadth-first search. There is typicall two way to approach this: recursive and non-recursive. You can find a pseudo code for a non-recursive algorithm here:

http://en.wikipedia.org/wiki/Breadth-first_search#Algorithm

You will of course need to tailor it for your own needs, but it does not really change the principal.

UPDATE

Ben Aaronson is right (comment bellow). This is not Breadth-first. It is Depth-first:

http://en.wikipedia.org/wiki/Depth-first_search#Pseudocode

Sorry for the confusion.

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

I disagree. The tree traversal and the evaluation can be seperated from each other. Here is how you do it:

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

Note that in post order DFS the children directly precedes the parent. A possible implementation is here:

Link

The only thing you need to change here is the return type, and make a yield return instead of Console.Write.

The evaluation would look like this:

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

Answer 2

I want to try to give a general answer. Because recursion is in fact using a stack (the call stack), any recursive function can be converted to an iterative one using a stack in a straight-forward way. You can just simulate the call stack:

The call stack contains:

• the arguments
• the return address
• and the local variables.

Create a struct for these:

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

Arguments is easy: The arguments are set to the values of the arguments for the recursive call.

The tricky part is the "return address" or as I called it here the ExecutionState, and the LocalVars.

ExecutionState should keep track of where the call was made, to resume execution after the "recursive call" returns. In your example, there are 3 possible states:

• evaluating
• returned from first call
• returned from second call

LocalVars include the result, and the Children loop iterator. Because a call is made inside the loop, it has to be interrupted, and resumed later, so the loop iterator must be on the stack too.

Update: here I had written an untested C++/# pseudocode version. The OP (@tigrou) corrected some errors and made a working C# version, which he allowed me to include here:

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

Answer 3

The problem of evaluating arithmetic expressions in a non-recursive way was solved and first published over 50 years ago. You're looking for Dijkstra's shunting-yard algorithm. The Wikipedia article has a great description of the algorithm, and there are tens of thousands of hits in Google, including a Literate Programs article that does a good job of combining description and implementation.

Answer 4

Here is best solution I come with so far. It is based on Gábor Angyal answer.

It is slightly different from his implementation, so I post it here in case it would be useful for someone. Note that it still use recursivity, because the way GetNodesDFS() is implemented. I did it that way because the stack based implementation for DFS traversal is not trivial to write and code review (maintenance).

In the end I prefer that solution from the initial recursive example in OP, because the recursively part is separated from the main loop that deals with node evaluation. The real code is a lot more complex than these examples, and using recursivity as in the OP, I had to pass lot of variables for each recursive call (which is not a problem here)

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() is implemented this way (see remark above) :

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