Yes, it is definitely solvable using basics.

To find out how complex the problem is, I wrote a 500-line test program to do this for AND, OR, XOR, NOT, NOT-NOT (or copy), NAND, and NOR logic gates.

The general problems I encountered were:

To get you started, consider these enumerated constants, structure, and global variables:

Code:

#include <stdlib.h>
/* Maximum number of inputs per gate */
#define MAX_INPUTS 16
/* Maximum number of gates */
#define MAX_GATES 65536
typedef enum {
LOGIC_UNKNOWN = 0,
LOGIC_LOW = 1,
LOGIC_HIGH = 2,
} logic_state;
typedef enum {
GATE_UNUSED = 0,
GATE_HIGH = 1, /* Always high, no inputs */
GATE_LOW = 2, /* Always low, no inputs */
GATE_NOT = 3, /* Exactly one input */
GATE_NOT_NOT = 4, /* Exactly one input, copies that input */
GATE_AND = 5, /* Two or more inputs */
GATE_OR = 6, /* Two or more inputs */
GATE_XOR = 7, /* Exactly two inputs (or an even number of inputs) */
GATE_NAND = 8, /* Two or more inputs */
GATE_NOR = 9, /* Two or more inputs */
} logic_gate_type;
typedef struct {
logic_gate_type type;
logic_state state;
size_t inputs;
size_t input_gate[MAX_INPUTS];
} logic_gate;
static size_t num_gates = 0; /* Highest gate defined + 1 */
static logic_gate gates[MAX_GATES]; /* Array of logic gates */

You can avoid the arbitrary limits by using dynamic memory allocation, which would change the above into

Code:

#include <stdlib.h>
typedef enum {
LOGIC_UNKNOWN = 0,
LOGIC_LOW = 1,
LOGIC_HIGH = 2,
} logic_state;
typedef enum {
GATE_UNUSED = 0,
GATE_HIGH = 1, /* Always high, no inputs */
GATE_LOW = 2, /* Always low, no inputs */
GATE_NOT = 3, /* Exactly one input */
GATE_NOT_NOT = 4, /* Exactly one input, copies that input */
GATE_AND = 5, /* Two or more inputs */
GATE_OR = 6, /* Two or more inputs */
GATE_XOR = 7, /* Exactly two inputs (or an even number of inputs) */
GATE_NAND = 8, /* Two or more inputs */
GATE_NOR = 9, /* Two or more inputs */
} logic_gate_type;
typedef struct {
logic_gate_type type;
logic_state state;
size_t inputs;
size_t *input_gate;
} logic_gate;
static size_t max_gates = 0; /* Number of gates allocated */
static size_t num_gates = 0; /* Highest gate defined + 1 */
static logic_gate *gates = NULL; /* Dynamically allocated array of gates */

In both cases, gate *g*, 0 <= *g* and *g* < num_gates, has gates[*g*].inputs input gates, the i'th of which is gate gates[*g*].input_gate[*i*]. The state of that gate is gates[gates[*g*].input_gate[*i*]].state, whereas the state of gate *g* is gates[*g*].state.

Feel free to use any other data structures or definitions you prefer. I only listed the above, because I know it works. Who knows, some other approach might even be simpler.