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.