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

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.

• Is your initial method actually right? It seems like nodes with a type of AND_OPERATOR would always return false. Commented Jan 29, 2015 at 11:03
• @BenAaronson : you are right about this, I edited question. Thanks for spotting it. Commented Jan 29, 2015 at 11:08

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:

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:

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;
}
``````
• So a `queue` would be more appropriate for this ? Commented Jan 29, 2015 at 11:00
• Yes. Using a stack you will end up with a Depth-first search: en.wikipedia.org/wiki/Depth-first_search#Pseudocode Commented Jan 29, 2015 at 11:02
• How is it breadth-first? Commented Jan 29, 2015 at 11:05
• @BenAaronson You are right, I mixed it up. Commented Jan 29, 2015 at 12:15
• 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 Commented Jan 29, 2015 at 12:18

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
• 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;
}
``````
• Interesting. I made a C# conversion and it works. There was a few mistakes however. Most of them involving using `node` directly instead of `context.node` but the rest was fine. I have put the C# version there: pastebin.com/4bzGdFzi Commented Jan 31, 2015 at 16:43
• Great! Can I replace my version with yours? Commented Jan 31, 2015 at 23:58
• Yes of course, that would be nice. Commented Feb 1, 2015 at 12:31

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.

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