Thread: Digital Logic + trees=getting crazy! :)

1. Digital Logic + trees=getting crazy! :)

Hello everybody!
I put a lot of effort trying to understand what was wrong in this program but still cannot find the problem.
The aim is to emulate a digital logic network composed by AND OR and NOT gates. The network has to be represented as a tree. I supposed that all the doors can have a maximum of 2-inputs so the node of the tree is:

Code:
```struct gate
{
void *leftPtr;
void *rightPtr;
int input1,input2,output;
int (*function)(int,int);
};

typedef struct gate Gate;
typedef Gate * GatePtr;```
I suppose that an input to the gate is represented by a node with output set to 1 or 0 during the initialization, while all the gates have the input initially set to -2.

These are the functions the pointer points to:

Code:
```int and (int input1, int input2)
{
printf("AND IN1:&#37;d IN2:%d\n",input1,input2);
if (input1&input2) return 1;
return 0;
}
int or (int input1,int input2)
{

printf("OR IN1:%d IN2:%d\n",input1,input2);
if (input1|input2) return 1;
return 0;
}

int not (int input1, int input2)
{

printf("NOT IN1:%d\n",input1);
if (input1==0)
return 1;
return 0;
}```
In the main I initialize the network like this:

Code:
```int main ()
{
GatePtr rootPtr = NULL;

GatePtr gate[4],input[4];
int i;

for (i=0;i<4;i++)
{
gate[i]=(GatePtr) malloc (sizeof(Gate));
if (gate[i]==NULL)
{
printf("Out of memory\n");
return 1;
}

input[i]=(GatePtr) malloc (sizeof(Gate));
if (input[i]==NULL)
{
printf("Out of memory\n");
return 1;
}
}
rootPtr=gate[0];
gate[0]->function=or;
gate[0]->leftPtr=gate[1];
gate[0]->rightPtr=gate[3];
gate[0]->output=-2;
printf("p0 %p\n",gate[0]);

gate[1]->function=not;
gate[1]->leftPtr=gate[2];
gate[1]->rightPtr=NULL;
gate[1]->output=-2;
printf("p1 %p\n",gate[1]);

gate[2]->function=and;
gate[2]->leftPtr=input[0];
gate[2]->rightPtr=input[1];
gate[2]->output=-2;
printf("p2 %p\n",gate[2]);
gate[3]->function=and;
gate[3]->leftPtr=input[2];
gate[3]->rightPtr=input[3];
gate[3]->output=-2;
printf("p3 %p\n",gate[3]);
input[0]->function=NULL;
input[0]->output=1;
input[0]->leftPtr=NULL;
input[0]->rightPtr=NULL;
printf("i0 %p\n",input[0]);
input[1]->function=NULL;
input[1]->output=1;
input[1]->leftPtr=NULL;
input[1]->rightPtr=NULL;
printf("i1 %p\n",input[1]);
input[2]->function=NULL;
input[2]->output=1;
input[2]->leftPtr=NULL;
input[2]->rightPtr=NULL;
printf("i2 %p\n",input[2]);
input[3]->function=NULL;
input[3]->output=1;
input[3]->leftPtr=NULL;
input[3]->rightPtr=NULL;
printf("i3 %p\n",input[3]);
printf("PREORDER: \n");
preorder(rootPtr);
printf("\n");
int exit=gateExit(&rootPtr);
printf("***EXIT***:%d\n",exit);
for (i=0;i<4;i++)
{
free (input[i]);
free (gate[i]);
}
return 0;
}```
In brief,
input 0 and input 1 go into an AND gate represented by gate2, whose output goes into gate1 (a NOT gate) and on the other side the inputs 2 and 3 go into the AND gate3. The output of gates 1 and 3 is ORed in gate 0 whose output represents the output of the network.
Finally, this is the function which should explore the tree and evaluate the exits:

Code:
```int gateExit (GatePtr *rootPtr)
{
if (*rootPtr!=NULL)
{
printf("GateExit: NODE:%p LEFT:%p RIGHT:%p\n",*rootPtr, (*rootPtr)->leftPtr,(*rootPtr)->rightPtr);

if ( (*rootPtr)->output==-2) //devi calcolare l'output della gate
{
printf("Node with output to be evaluated: Root:%p Left:%p Right:%p\n",*rootPtr, (*rootPtr)->leftPtr,(*rootPtr)->rightPtr);

if ((*rootPtr)->leftPtr!=NULL)
{
printf("Invoke GateExit with root (Left) %p:\n",(*rootPtr)->leftPtr);
(*rootPtr)->input1=gateExit( (*rootPtr)->leftPtr );
}

if ((*rootPtr)->rightPtr!=NULL)
{

printf("Invoke GateExit with root (Right) %p:\n",(*rootPtr)->rightPtr);
(*rootPtr)->input2=gateExit((*rootPtr)->rightPtr);
}
else
(*rootPtr)->input2=-1;

(*rootPtr)->output=((*rootPtr)->function)((*rootPtr)->input1,(*rootPtr)->input2);
}
printf("EXIT OF GATE: %p = %d\n",*rootPtr,(*rootPtr)->output);
return (*rootPtr)->output;
}
return -2;

}```
When I run the program I get this output:

Code:
```p0 0x804a008
p1 0x804a048
p2 0x804a088
p3 0x804a0c8
i0 0x804a028
i1 0x804a068
i2 0x804a0a8
i3 0x804a0e8
PREORDER:
0x804a008 ] IN1 0 IN2 0 OUT -2
0x804a048 ] IN1 0 IN2 0 OUT -2
0x804a088 ] IN1 0 IN2 0 OUT -2
0x804a028 ] IN1 0 IN2 0 OUT 1
0x804a068 ] IN1 0 IN2 0 OUT 1
0x804a0c8 ] IN1 0 IN2 0 OUT -2
0x804a0a8 ] IN1 0 IN2 0 OUT 1
0x804a0e8 ] IN1 0 IN2 0 OUT 1

GateExit: NODE:0x804a008 LEFT:0x804a048 RIGHT:0x804a0c8
Node with output to be evaluated: Root:0x804a008 Left:0x804a048 Right:0x804a0c8
Invoke GateExit with root (Left) 0x804a048:
GateExit: NODE:0x804a088 LEFT:0x804a028 RIGHT:0x804a068
Node with output to be evaluated: Root:0x804a088 Left:0x804a028 Right:0x804a068
Invoke GateExit with root (Left) 0x804a028:
Invoke GateExit with root (Right) 0x804a068:
AND IN1:-2 IN2:-2
EXIT OF GATE: 0x804a088 = 1
Invoke GateExit with root (Right) 0x804a0c8:
GateExit: NODE:0x804a0a8 LEFT:(nil) RIGHT:(nil)
EXIT OF GATE: 0x804a0a8 = 1
OR IN1:1 IN2:1
EXIT OF GATE: 0x804a008 = 1
***EXIT***:1```
In my mind the gateExit should perform a PREorder visit to nodes, but if you read the output it's like if gate 1 is not explored:
Code:
```...GateExit: NODE:0x804a008 LEFT:0x804a048 RIGHT:0x804a0c8
Node with output to be evaluated: Root:0x804a008 Left:0x804a048 Right:0x804a0c8
Invoke GateExit with root (Left) 0x804a048:
GateExit: NODE:0x804a088 LEFT:0x804a028 RIGHT:0x804a068...```
May you help me in understanding what is wrong with my program please?
THANKS!

2. nobody can help me please?

3. Does your tree have only one node to start from? IE:
Code:
```	preorder(rootPtr);
printf("\n");
int exit=gateExit(&rootPtr);```
Makes it look as if you are starting from one node and recuring out via linked nodes. The way I see it is that this should not work for most sets of logic gates. For example a set of gates such as:
Code:
```AND
\
OR--->
/
AND```
You would need to determine the o/p of both AND gates before you evaluate the OR gate. Maybe your preorder function is meant to handle this, but as I dont know the code I cant tell.

4. Originally Posted by mike_g
Does your tree have only one node to start from? IE:
Code:
```	preorder(rootPtr);
printf("\n");
int exit=gateExit(&rootPtr);```
Makes it look as if you are starting from one node and recuring out via linked nodes. The way I see it is that this should not work for most sets of logic gates. For example a set of gates such as:
Code:
```AND
\
OR--->
/
AND```
You would need to determine the o/p of both AND gates before you evaluate the OR gate. Maybe your preorder function is meant to handle this, but as I dont know the code I cant tell.
the code of preorder is very easy
Code:
```void preorder(GatePtr sPtr)
{
if (sPtr!=NULL)
{
printf("%p ] IN1 %d IN2 %d OUT %d\n",sPtr,sPtr->input1,sPtr->input2,sPtr->output);
preorder(sPtr->leftPtr);
preorder (sPtr->rightPtr);
}
}```
and I just inserted it to get this output:

Code:
```PREORDER:
0x804a008 ] IN1 0 IN2 0 OUT -2
0x804a048 ] IN1 0 IN2 0 OUT -2
0x804a088 ] IN1 0 IN2 0 OUT -2
0x804a028 ] IN1 0 IN2 0 OUT 1
0x804a068 ] IN1 0 IN2 0 OUT 1
0x804a0c8 ] IN1 0 IN2 0 OUT -2
0x804a0a8 ] IN1 0 IN2 0 OUT 1
0x804a0e8 ] IN1 0 IN2 0 OUT 1```
yes i imagined that the network has only 1 exit which is the root and is explored backward towards the inputs...
the core of the problem is in the gateExit function...

5. Actually your recursion should reach out to all the leaf nodes then evaluate correctly, but this is assuming that you have only one exit gate.

You would however get more coherent output if you printed the line that starts with:
printf("Node with output to be evaluated:
After you call the recurring functions

Could you maybe create a simplified compiliable prog demonstrating your problem? It would probably make it easier for other people to help you with this.

6. Since this seemed like something fun to code I had a go at creating my own version, which as far as I can tell so far seems to work.

The way I did it was to shove all the nodes on a list. Then repeatedly run over the list until all gates have been evaluated. Evaluation is only performed once both inputs are set.

Code:
```void eval_gates(Gate* head)
{
int todo=1, inputs;
while(todo)
{
todo = 0;
while(node)
{
inputs =  (node->one)?(node->one->result != -1)?1:0:1;
inputs += (node->two)?(node->two->result != -1)?1:0:1;

if(inputs != 2)
todo++;
//if both inputs are set calculate output if not done so already
else if(node->result == -1);
{
// if a or b != -1 then it is a leaf node
if(node->a == -1) node->a = node->one->result;
if(node->b == -1) node->b = node->two->result;
node->result = (node->func)(node->a, node->b);
}
node=node->next;
}
}
}```

7. this is my version:

Code:
```#include <stdio.h>
#include <stdlib.h>

int and (int input1, int input2);
int or (int input1,int input2);
int not (int input1, int input2);

struct gate
{
void *leftPtr;
void *rightPtr;
int input1,input2,output;
int (*function)(int,int);
};

typedef struct gate Gate;
typedef Gate * GatePtr;
void preorder(GatePtr sPtr)
{
if (sPtr!=NULL)
{
printf("%p ] IN1 %d IN2 %d OUT %d\n",sPtr,sPtr->input1,sPtr->input2,sPtr->output);
preorder(sPtr->leftPtr);
preorder (sPtr->rightPtr);
}
}

int gateExit (GatePtr *rootPtr)
{
if (*rootPtr!=NULL)
{
printf("GateExit: NODE:%p LEFT:%p RIGHT:%p\n",*rootPtr, (*rootPtr)->leftPtr,(*rootPtr)->rightPtr);

if ( (*rootPtr)->output==-2) //devi calcolare l'output della gate
{
printf("Node with output to be evaluated: Root:%p Left:%p Right:%p\n",*rootPtr, (*rootPtr)->leftPtr,(*rootPtr)->rightPtr);

if ((*rootPtr)->leftPtr!=NULL)
{
printf("Invoke GateExit with root (Left) %p:\n",(*rootPtr)->leftPtr);
(*rootPtr)->input1=gateExit( (*rootPtr)->leftPtr );
}

if ((*rootPtr)->rightPtr!=NULL)
{

printf("Invoke GateExit with root (Right) %p:\n",(*rootPtr)->rightPtr);
(*rootPtr)->input2=gateExit((*rootPtr)->rightPtr);
}
else
(*rootPtr)->input2=-1;

(*rootPtr)->output=((*rootPtr)->function)((*rootPtr)->input1,(*rootPtr)->input2);
}
printf("EXIT OF GATE: %p = %d\n",*rootPtr,(*rootPtr)->output);
return (*rootPtr)->output;
}
return -2;

}

int and (int input1, int input2)
{
printf("AND IN1:%d IN2:%d\n",input1,input2);
if (input1&input2) return 1;
return 0;
}
int or (int input1,int input2)
{

printf("OR IN1:%d IN2:%d\n",input1,input2);
if (input1|input2) return 1;
return 0;
}

int not (int input1, int input2)
{

printf("NOT IN1:%d\n",input1);
if (input1==0)
return 1;
return 0;
}

int main ()
{
GatePtr rootPtr = NULL;

GatePtr gate[4],input[4];
int i;

for (i=0;i<4;i++)
{
gate[i]=(GatePtr) malloc (sizeof(Gate));
if (gate[i]==NULL)
{
printf("Out of memory\n");
return 1;
}

input[i]=(GatePtr) malloc (sizeof(Gate));
if (input[i]==NULL)
{
printf("Out of memory\n");
return 1;
}
}
rootPtr=gate[0];
gate[0]->function=or;
gate[0]->leftPtr=gate[1];
gate[0]->rightPtr=gate[3];
gate[0]->output=-2;
printf("p0 %p\n",gate[0]);

gate[1]->function=not;
gate[1]->leftPtr=gate[2];
gate[1]->rightPtr=NULL;
gate[1]->output=-2;
printf("p1 %p\n",gate[1]);

gate[2]->function=and;
gate[2]->leftPtr=input[0];
gate[2]->rightPtr=input[1];
gate[2]->output=-2;
printf("p2 %p\n",gate[2]);
gate[3]->function=and;
gate[3]->leftPtr=input[2];
gate[3]->rightPtr=input[3];
gate[3]->output=-2;
printf("p3 %p\n",gate[3]);
input[0]->function=NULL;
input[0]->output=1;
input[0]->leftPtr=NULL;
input[0]->rightPtr=NULL;
printf("i0 %p\n",input[0]);
input[1]->function=NULL;
input[1]->output=1;
input[1]->leftPtr=NULL;
input[1]->rightPtr=NULL;
printf("i1 %p\n",input[1]);
input[2]->function=NULL;
input[2]->output=1;
input[2]->leftPtr=NULL;
input[2]->rightPtr=NULL;
printf("i2 %p\n",input[2]);
input[3]->function=NULL;
input[3]->output=1;
input[3]->leftPtr=NULL;
input[3]->rightPtr=NULL;
printf("i3 %p\n",input[3]);
printf("PREORDER: \n");
preorder(rootPtr);
printf("\n");
int exit=gateExit(&rootPtr);
printf("***EXIT***:%d\n",exit);
for (i=0;i<4;i++)
{
free (input[i]);
free (gate[i]);
}
return 0;
}```

8. Originally Posted by mike_g
Since this seemed like something fun to code I had a go at creating my own version, which as far as I can tell so far seems to work.

The way I did it was to shove all the nodes on a list. Then repeatedly run over the list until all gates have been evaluated. Evaluation is only performed once both inputs are set.

Code:
```void eval_gates(Gate* head)
{
int todo=1, inputs;
while(todo)
{
todo = 0;
while(node)
{
inputs =  (node->one)?(node->one->result != -1)?1:0:1;
inputs += (node->two)?(node->two->result != -1)?1:0:1;

if(inputs != 2)
todo++;
//if both inputs are set calculate output if not done so already
else if(node->result == -1);
{
// if a or b != -1 then it is a leaf node
if(node->a == -1) node->a = node->one->result;
if(node->b == -1) node->b = node->two->result;
node->result = (node->func)(node->a, node->b);
}
node=node->next;
}
}
}```
i've some problems to understand your code...

9. Well I think the recursive approach will become very complicated when you have to deal with circuits that may look something like:
Code:
```AND-
\
|
+-NOT-->
|
+-AND-->
/
/
OR-```
Also, you could remove some redundant code by making a constructor-like function for you gates.

Edit:
i've some problems to understand your code...
Yeah, sorry about that its probably not all that easy to follow. The basic concept is to add each gate to a linked list, or for your version you could just work with the array.

Then you repeatedly loop over the list or array.
If both inputs are set, then you can you are ready to evaluate the result for the gate; otherwise you ignore the gate for the time being until the inputs are set.
Eventually all the gates will have results, so then you can break out of the loop.

Hope that makes sense.