Multi-level logic gates for begginers

[Pinkysuavo]

Hello. I have to do a multi-level logic gates simulation. Without graphics, it should just read the information about the circuit from for example text file, and then show every gate's logic output. For example: (numbers may be just the inputs (true of false (1 or 0)), or a gate number - and then, there should be it's type (and/or/xor/not), and at the end the inputs numbers.
001 TRUE
002 AND 1 3
003 FALSE
Program should show all gates outputs, so in this simple case, 002 would have output ,,0" (cause TRUE and FALSE is connected), and 001 and 003 would stay same of course.
The thing is this program should work on many levels. I don't know how to get to work. And the worse thing is that I'm new to C and this is hard for me. I've been learning C for 3 months now at uni but I don't know much (I admit I didn't do much at home, just lessons, but it's nothing comparised to this in my opinion), I'm learning it as much as I can at home now to get enough skills to finish this project. Does anyone have ideas for this? Then I'll try on learning more on the stuff that I'll need. Is there any way to solve this with basics? (I don't want full code, I really want to learn, write and understand this, I'm just on low level atm. We had stuff like loops, ifs, pointers, structures, linked lists, some file operations (like reading or writing text), mallocs, arrays, I don't know what else. Just basics I guess, although I need to practice on few of these.
My idea on this program (but NO IDEA is it even possible or how to do it) is like it would check all the numbers, and let's say it gets on 001, so it would check what's standing next to it - there's a TRUE, so it remembers 001's logic value ,,TRUE". After that, it gets to 002 AND 1 3, then it calculates logic value of 1 AND 3 (it would find 3 as FALSE in next line). After calculating it, it would ascribe the 1 AND 3 value (FALSE) to the 002 gate, in case it would be needed somewhere in future
like for example 013 AND 2 11. While discussing projects, my teacher told me to use arrays to store the gates/values(?), but I don't know how would it practicaly look like. Is it possible to solve it on low-level skills? I have a little less than 2 weeks for that and I'm determined to learn as much and write this program. I'm currently reading and watching about C to learn more, but can't really start this project already.

[Matticus]

For starters, notice that the operation dictated by 002 requires the value associated with 003. This implies, to me at least, that your program should first load all of the information before operating on any of it, as it will have to be able to know information further down the list.

A sequential numbering system ... what does that remind you of?

Different kinds of information (data or operations) that may need to be stored in the same type of variable ... does that make you think of anything?

[Nominal Animal]

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:

• The logic gate definitions -- reading and verification
  
  The initial post stated that gates are defined one per line, using format
  
  output type [ input ... ]
  where output and input are gate numbers in decimal, and type is the gate type.
  
  Some gate types like AND, OR, NAND, NOR can have two or more inputs, whereas NOT and NOT-NOT need exactly one, TRUE/HIGH and FALSE/LOW have no inputs, and XOR should have an even number of inputs. If the number of inputs does not make sense for the logic gate, the program should complain (preferably with a line number) about it.
  
  If you have, or can set, definite limits on the number of inputs per gate, this simplifies the gate definitions.
  
  This requires basic string handling (tokenization, parsing), and you can easily develop the parsing in a separate program first, before incorporating it into the main program. I would be particularly careful about detecting invalid inputs. In the main program, you can define the gates in your main() for testing, until you get the input parsing working robustly.
   
• Implementation of the individual logic gate logic
   
  Initially, I thought of implementing each logic gate function as taking the number of inputs, and an array containing those inputs' states. However, that leads to lots of duplicated code.
  
  Instead, I realized that for each gate type, if all the inputs are defined (either low or high), only the count of low and high inputs matter. Thus, my logic gate resolver ended up being a single function,
  

  logic_state  resolve_gate(const logic_gate_type  type, const size_t  high_inputs, const size_t  low_inputs)

  with a not-too-large switch (type) .. in it, with each case containing some if clauses depending on high_inputs and low_inputs only.
   
• Resolving the state of the gate array
  
  The logic gate array forms a directed graph, where each node is a logic gate, and inputs are the graph edges.
  
  If the graph has cycles, it may not be resolvable. Consider the minimal example
  
  0 HIGH
  1 XOR 0 2
  2 XOR 0 1
  where the states of gates 1 and 2 are unresolvable; cyclically dependent. Such cycles can be extremely large, and hard to detect, and detecting them correctly is pretty important in practice.
  
  This means each gate may have one of three states: LOW, HIGH,or UNKNOWN, with all but HIGH/TRUE and LOW/FALSE gates' states initialized to UNKNOWN initially.
  
  There are two ways of solving the state: iterative, and recursive.
  
  Recursive is fast (it does not do any unnecessary work), but it crashes easily if a loop occurs, or if the dependency chains are too long. The idea is simple: For each gate that is in UNKNOWN state, you check the input gates' states, recursively, until none of the inputs is in unknown state and you can resolve the state of the gate itself. It is a very simple in-order tree traversal.
  
  Iterative is slower (as it does several passes over all gates), but it is deterministic and has no weak spots (except for slowness). You do passes over all gates in UNKNOWN state, resolving them if none of their inputs are in unknown state. You are done when the pass no longer resolves any new gates. If there are gates left in UNKNOWN state, the graph is unresolvable (cyclic).
   
• General implementation decisions
  
  Since the gates are identified by positive integers, probably rather consecutive and dense (as opposed to just being some random numbers), an array is very suitable data structure to hold the gates (as Matticus hinted at).
  
  (If the gate numbers were very large, then a mapping from gate identifiers to actual array indexes and back could be implemented. Not necessarily as part of this program: such mapping is routinely done using tools like awk, if necessary. After berating the person who produced the stupid input files with insane gate numbers in the first place, of course.)

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

#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

#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.

[algorism]

Assuming
* AND, OR, etc all take two inputs (i.e., are binary operators)
* relatively small input size (say 1000 lines max, so no dynamic memory needed)
* no loops in the connection graph
* cursory data validation
you can solve this in under 150 lines.

For each line read it with fgets and then use sscanf on the buffer. sscanf's return value is the number of fields successfully set. So a format of integer, string, integer, integer would return 2 for a value (TRUE, FALSE), 3 for a unary operator (NOT), and 4 for a binary operator (AND, OR, ...). Any other return value indicates a blank or malformed line. (Simply ignoring "bad" lines provides a simple kind of comment since any line beginning (after spaces) with a non-digit is ignored.)

Read the data into an array of structs with the struct defined something like (simplifying nominal's representation based on the foregoing restrictions):

typedef enum GateType {
  GATE_FALSE, GATE_TRUE,        // values
  GATE_NOT,                     // unary ops
  GATE_AND, GATE_OR             // binary ops
} GateType;

typedef struct Gate {
  GateType type;
  int left, right;
} Gate;

For GATE_FALSE, and GATE_TRUE types, left and right are ignored (set them to zero for neatness, though). For GATE_NOT, use left for its connection and ignore right (set to zero). For the binary operators, both left and right are used. (I only put AND and OR above. Add whatever else you need.)

Try writing a readGates routine to read the data file into an array of Gate structs. Print out the gate array after to see if it has been read correctly. The solving routine using recursion is surprisingly easy, so reading in the data is more than half the battle.

[Pinkysuavo]

Looks like I am on lower level than I said. You helped me a little guys, but I don't know what is dynamic memory allocation for example, and many other things... Yeah I can google them, but I dont know if it helps. I can understand basic things but things further than that makes my brain hurt. For example, I've been searching now for what is Makefile etc. I don't know ........ about it, after 1 hour, reading every possible thing. I think I am too dumb for programming

[algorism]

It's not as hard as you think. You don't need dynamic memory. You don't need a makefile. You can do it in one source file of < 150 lines.

What compiler are you using?
Can you use it from the command line?
Can you compile and run a single C source file?

The basic idea is to read lines of the following types (examples):

001  TRUE
002  NOT     3
003  OR      4    5
004  FALSE
005  NOT     1

Every line has an integer followed by a (space-delimited) string.
If the string is "NOT" then it has one extra integer.
If it's "AND", "OR", or any other binary operator, it has two extra integers (I assume it's only two).

Just use scanf to read the first integer and the string. Then use if's and strcmp to compare the string to the various names (remembering that strcmp returns 0 when the strings match). If it's one that needs an extra integer or two, read them with another scanf.

As a first step you could make a version that simply prints each line of input back out, having first read it into separate variables. To control a loop with scanf, you test that it read the number of fields you were expecting. So you might start like this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
  char type[256];  // gate type
  int i, a, b;     // index, first value, second value

  while (scanf("%d %255s", &i, type) == 2) {

[Matticus]

Looks like I am on lower level than I said. You helped me a little guys, but I don't know what is dynamic memory allocation for example, and many other things... Yeah I can google them, but I dont know if it helps. I can understand basic things but things further than that makes my brain hurt. For example, I've been searching now for what is Makefile etc. I don't know ........ about it, after 1 hour, reading every possible thing. I think I am too dumb for programming

Nonsense. While some of the advice here might have been over your head, you can certainly do this project yourself based on what you've already learned.

If a programming problem seems too difficult, then you need to break that problem down into smaller manageable pieces and solve them one at a time. Divide and conquer.

It also helps to develop your approach on paper first, before attempting to turn it into code.

When you start coding, build your program up incrementally. Do one little bit, compile, and test it. Make sure it works before moving on to the next piece. See A Development Process.

Perhaps you can start by writing a simple program that reads the information from the text file, line by line in a loop, and prints each line as its read. Get that working before moving on to the next part.

[algorism]

I just coded up an example that, with a few simplifications, seems to solve the problem in about 50 lines. So we've got it from 500, to 150, to 50 in just a few posts. It can't be that difficult!

[Pinkysuavo]

To be clear: my gates must have 2 inputs (1 for NOT) and include only AND, OR, XOR, NOT. Data should be read from text file.

@Matticus I can do a program that reads information from text file and prints it... But I used fgetc for that and that doesn't give me anything.

My problem is I don't really know how it should read data from the text file... I mean if I have for example
001 TRUE
002 AND 1 3
003 FALSE
How I can make my program know what's 001, what's TRUE, what's AND etc, and store it?
I realise it would first detect integer, then string, then if string is AND/OR/XOR (which I can check with strcmp I guess) it should expect 2 more integers
(like in algorism's example)
But let's say it goes like in this example, we have 001 TRUE, so okay, it reads like %d and %s, but what next? How it practically looks like when it comes to next lines? This fscanf should be like looped? Or it's natural that he will search for sequence like %d and %s all the time (unless it gets on the if/strcmp).

@algorism
You wrote something with scanf, but I don't understand why it's equal to 2. Also, I must use fscanf

[Matticus]

algorism has suggested using fscanf (which scans from a file).

I am personally more partial to reading an entire line with "fgets()" and parsing it with sscanf (which scans from a string). That is why I suggested staring with a program that just reads lines from the file and prints them.

Either approach (fscanf or sscanf) should work for your case.

You wrote something with scanf, but I don't understand why it's equal to 2.

The "scanf()" family of functions returns the value of items successfully read. In the case of algorism's example, there are two values expected to be read, so you confirm that it has indeed read two values by checking that the return value is equal to 2.

How I can make my program know what's 001, what's TRUE, what's AND etc, and store it?

Well, the first value is simply a number, and can be stored as such.

What follows is a word. You need to check that word, and set a value depending on what it is. What value do you set? That is up to you. Both algorism and Nominal Animal gave you suggestions on how to represent what the word is as a value.

Depending on that value, you might need also need to store additional numbers (e.g. "TRUE" means no additional numbers are present, "NOT" means one additional number is present, "AND" means two additional numbers are present, etc).

Then you use that value to determine what actions to take.

[Pinkysuavo]

The "scanf()" family of functions returns the value of items successfully read. In the case of algorism's example, there are two values expected to be read, so you confirm that it has indeed read two values by checking that the return value is equal to 2.

I don't get it. Why just 2 values? My text file can have any amount of them. My text file has many words, how my program can know which one is what? If it was always one line of text, for example "001 TRUE" then it's quite clear to me, that I'd set fscanf to read number then string (( for example as fscanf("%d %s",nr,gatetype) )). But there are many more words and lines later and this one is just 2 values. I don't understand this

[laserlight]

Why just 2 values? My text file can have any amount of them.

Hence the loop: you read 2 values at a time, but that doesn't mean you will always read only 2 values.

[Matticus]

But there are many more words and lines later and this one is just 2 values. I don't understand this

That was in relation to algorism's example, which read the number, then the rest of the data into a single string.

scanf("%d %255s", &i, type) == 2

I did it a little bit differently, by trying to read each item separately.

Here's a quick mock-up to illustrate how to read values from a string (each string corresponding to one line in your file):

#include <stdio.h>

int main(void)
{
    int id;
    char word[32];
    int operand_1;
    int operand_2;
    int ret_value;

    const char *input[3] = {
        "001 TRUE",
        "002 NOT 1",
        "003 AND 1 2"
    };

    printf("Scanning \"%s\"...\n", input[0]);
    ret_value = sscanf(input[0], "%d %s %d %d", &id, word, &operand_1, &operand_2);
    printf("> %d items scanned\n", ret_value);
    printf("> id   = %d\n", id);
    printf("> word = %s\n", word);
    putchar('\n');

    printf("Scanning \"%s\"...\n", input[1]);
    ret_value = sscanf(input[1], "%d %s %d %d", &id, word, &operand_1, &operand_2);
    printf("> %d items scanned\n", ret_value);
    printf("> id   = %d\n", id);
    printf("> word = %s\n", word);
    printf("> op 1 = %d\n", operand_1);
    putchar('\n');

    printf("Scanning \"%s\"...\n", input[2]);
    ret_value = sscanf(input[2], "%d %s %d %d", &id, word, &operand_1, &operand_2);
    printf("> %d items scanned\n", ret_value);
    printf("> id   = %d\n", id);
    printf("> word = %s\n", word);
    printf("> op 1 = %d\n", operand_1);
    printf("> op 2 = %d\n", operand_2);
    putchar('\n');

    return 0;
}

Needless to say, this is a very sloppy program, but it should show (1) how the return value of "scanf()" works, and (2) how to separate the information contained on each line.

[algorism]

I don't get it. Why just 2 values? My text file can have any amount of them. My text file has many words, how my program can know which one is what? If it was always one line of text, for example "001 TRUE" then it's quite clear to me, that I'd set fscanf to read number then string (( for example as fscanf("%d %s",nr,gatetype) )). But there are many more words and lines later and this one is just 2 values. I don't understand this

We realize that your input file has many lines of data. We're just trying to get you to read in one line to see if you can/want to do even just that much.

You will actually read the whole file and store each line into an internal format which will be an array of Gate structs, something like this:

#define GATES_SIZE 1000

typedef struct Gate {
  char type;  // use first letter for type code: 'F', 'T', 'N', 'A', 'O', 'X'
  int a, b;
} Gate;

int main() {
  Gate gates[GATES_SIZE];
...

Each line of input has at least an integer and a string.
The first integer tells you what array element to store it in.
The first letter of the string tells you the type code. (This assumes all first letters are distinct, as they are in your problem, and allows us to dispense with the enum.)
If the input type is 'N', then you read another integer into gates[i].a.
If it's 'A', 'O', or 'X', then you read another two integers into gates[i].a and gates[i].b.
Give this a try and write some code!

BTW, where does your input come from? A hard-coded file name? A file name passed in on the command line? I wrote my 50 line version to read from standard input, which is why I used scanf. (To simplify things, I wouldn't bother with fgets on this project, although it is generally a superior technique.)

[Pinkysuavo]

Inputs (and all the circuit description) must come from a textfile