Program to Generate Truth Tables From Logic Expressions In C++ Assignment Solution

Instructions

Objective

Write a program that allows users to generate truth tables from logic expressions in C++.

Requirements and Specifications

You will write a program truthtable that reads a file containing a description of a circuit, andprints that circuit’s truth table. The files specify (1) the number and names of each input to thecircuit, (2) the number and names of each output from the circuit, and (3) the logic gates and components that make up the circuit. In order to indicate the connections between gates, each connection is also given a name.

For example, this is a description for a circuit that implements a 3-argument AND gate:

INPUT 3 a b c

OUTPUT 1 d

AND a b x

AND c x d

Note that it contains three inputs (a, b, and c), a single output (d), and two AND gates, each of which has two inputs and one output. The variable x indicates an internal connection between the first AND gate and the second. See section 3 for details on the specification language.

truthtable takes a single argument, which is the name of a file containing a circuit description. The behavior of truthtable is unspecified if it receives no arguments or more than one argument, but you should still check that the number of arguments is correct. (One possibility is to have truthtable read from standard input if no file argument is given.)

Screenshots of output

Source Code

#include #include #include typedef enum { AND, OR, NAND, NOR, XOR, NOT, PASS, DECODER, MULTIPLEXER } kind_t; char *gate_name[9] = {"AND", "OR", "NAND", "NOR", "XOR", "NOT", "PASS", "DECODER", "MULTIPLEXER"}; typedef struct gate { kind_t kind; int size; // indicates size of DECODER and MULTIPLEXER int *params; // length determined by kind and size; // includes inputs and outputs, indicated by variable numbers }Gate; typedef struct variable { char *name; // variable name int value; // current value int out; // flag to indicate if it's an output for a gate or the circuit }Variable; typedef struct circuit { int ninputs; // number of inputs int *inputs; // input variable positions int noutputs; // number of outputs int *outputs; // output variable positions int ngates; // number of gates Gate **gates; // list of gates int nvars; // number of variables Variable **vars; // variables }Circuit; /* Free all the memory allocated by a variable */ void free_variable(Variable *var) { if (var != NULL) { if (var->name != NULL) free(var->name); free(var); } } /* Free all the memory allocated by a gate */ void free_gate(Gate *gate) { if (gate != NULL) { if (gate->params != NULL) free(gate->params); free(gate); } } /* Free all the memory allocated by the circuit */ void free_circuit(Circuit *circ) { int i; if (circ != NULL) { if (circ->ninputs && circ->inputs != NULL) free(circ->inputs); if (circ->noutputs && circ->outputs != NULL) free(circ->outputs); if (circ->vars != NULL) { for (i = 0; i < circ->nvars; i++) free_variable(circ->vars[i]); free(circ->vars); } if (circ->gates != NULL) { for (i = 0; i < circ->ngates; i++) free_gate(circ->gates[i]); free(circ->gates); } free(circ); } } /* Searches a variable in the variable list for the circuit, returns its position or -1 if not found */ int search_variable(char *var, Circuit *circ) { int i, index = -1; for (i = 0; i < circ->nvars && index == -1; i++) { if (!strcmp(var, circ->vars[i]->name)) index = i; } return index; } /* Create a new variable */ Variable *new_variable(char *name, Circuit *circ) { Variable *var = (Variable *) malloc(sizeof(Variable)); if (var == NULL) { printf("ERROR: Out of memory while creating variable\n"); free_circuit(circ); exit(EXIT_FAILURE); } var->name = (char *) malloc(strlen(name) + 1); if (var->name == NULL) { printf("ERROR: Out of memory while creating variable\n"); free(var); free_circuit(circ); exit(EXIT_FAILURE); } strcpy(var->name, name); // save variable name var->value = -1; // undefined var->out = 0; // not out return var; } /* Adds a variable to the variable list in the circuit, returns its position. It avoids adding repeated variable names */ int add_variable(char *var_name, Circuit *circ) { int n; Variable **vars; n = search_variable(var_name, circ); if (n == -1) // if new variable { n = circ->nvars; if (n == 0) vars = (Variable **) malloc(sizeof(Variable *)); else vars = (Variable **) realloc(circ->vars, (n + 1) * sizeof(Variable *)); if (vars == NULL) { printf("ERROR: Out of memory while creating variable\n"); free_circuit(circ); exit(EXIT_FAILURE); } circ->vars = vars; circ->vars[n] = new_variable(var_name, circ); circ->nvars++; // increment number of variables } return n; // return position of variable } /* Create a new circuit */ Circuit *new_circuit() { int i; Circuit *circ = (Circuit *) malloc(sizeof(Circuit)); if (circ == NULL) { printf("ERROR: Out of memory while creating circuit\n"); exit(EXIT_FAILURE); } /* set all entries to zero */ memset(circ, 0, sizeof(Circuit)); i = add_variable("0", circ); // add the zero constant circ->vars[i]->value = 0; // always zero i = add_variable("1", circ); // add the one constant circ->vars[i]->value = 1; // always one add_variable("_", circ); // add the dummy var return circ; } /* Create a new gate of n parameters and given kind */ Gate *new_gate(kind_t kind, int n, int size, Circuit *circ) { Gate *gate = (Gate *) malloc(sizeof(Gate)); if (gate == NULL) { printf("ERROR: Out of memory while creating gate\n"); free_circuit(circ); exit(EXIT_FAILURE); } gate->kind = kind; gate->params = (int *) malloc(n *sizeof(int *)); if (gate->params == NULL) { printf("ERROR: Out of memory while creating gate\n"); free(gate); free_circuit(circ); exit(EXIT_FAILURE); } gate->size = size; return gate; } /* Adds a gate to the gate list in the circuit. */ void add_gate(Gate *gate, Circuit *circ) { int n; n = circ->ngates; Gate **gates; if (n == 0) gates = (Gate **) malloc(sizeof(Gate *)); else gates = (Gate **) realloc(circ->gates, (n + 1) * sizeof(Gate *)); if (gates == NULL) { printf("ERROR: Out of memory while creating gate\n"); free_circuit(circ); exit(EXIT_FAILURE); } circ->gates = gates; circ->gates[n] = gate; // save gate circ->ngates++; // increment number of gates } /* Loads a circuit from the given file and returns it */ Circuit *load_circuit(char *filename) { FILE *f; char buffer[20]; int i, j, n, size; kind_t kind; Circuit *circ; Gate *gate; int outi, nouts; f = fopen(filename, "rt"); // open file as read only text if (f == NULL) // if file was not open { printf("ERROR: Unable to open file: \"%s\"\n", filename); exit(EXIT_FAILURE); // terminate program } // create new circuit circ = new_circuit(); // read input variables, it must be at start fscanf(f, "%16s %d", buffer, &circ->ninputs); // read if (strcmp(buffer, "INPUT")) { printf("ERROR: INPUT was not the first directive in the file\n"); exit(EXIT_FAILURE); } circ->inputs = (int *) malloc(circ->ninputs*sizeof(int)); // allocate space for inputs if (circ->inputs == NULL) { printf("ERROR: Out of memory while creating circuit inputs\n"); free_circuit(circ); exit(EXIT_FAILURE); } // read inputs for (i = 0; i < circ->ninputs; i++) { if (fscanf(f, "%16s", buffer) != 1) // read variable { printf("ERROR: INPUT expected a variable name\n"); free_circuit(circ); exit(EXIT_FAILURE); } n = add_variable(buffer, circ); circ->inputs[i] = n; // save variable position } // read output variables, it must be after input fscanf(f, "%16s %d", buffer, &circ->noutputs); // read if (strcmp(buffer, "OUTPUT")) { printf("ERROR: OUTPUT was not the second directive in the file\n"); free_circuit(circ); exit(EXIT_FAILURE); } circ->outputs = (int *) malloc(circ->noutputs*sizeof(int)); // allocate space for outputs if (circ->outputs == NULL) { printf("ERROR: Out of memory while creating circuit outputs\n"); free_circuit(circ); exit(EXIT_FAILURE); } // read outputs for (i = 0; i < circ->noutputs; i++) { if (fscanf(f, "%16s", buffer) != 1) // read variable { printf("ERROR: OUTPUT expected a variable name\n"); free_circuit(circ); exit(EXIT_FAILURE); } n = add_variable(buffer, circ); circ->outputs[i] = n; // save variable position circ->vars[circ->outputs[i]]->out = 1; } while (!feof(f)) // read all lines in file { if(fscanf(f, "%16s", buffer) == 1) // read directive { outi = 2; nouts = 1; if (!strcmp(buffer, "NOT")) { kind = NOT; size = 0; n = 2; outi = 1; nouts = 1; } if (!strcmp(buffer, "PASS")) { kind = PASS; size = 0; n = 2; outi = 1; nouts = 1; } else if (!strcmp(buffer, "AND")) { kind = AND; size = 0; n = 3; } else if (!strcmp(buffer, "OR")) { kind = OR; size = 0; n = 3; } else if (!strcmp(buffer, "NAND")) { kind = NAND; size = 0; n = 3; } else if (!strcmp(buffer, "NOR")) { kind = NOR; size = 0; n = 3; } else if (!strcmp(buffer, "XOR")) { kind = XOR; size = 0; n = 3; } else if (!strcmp(buffer, "DECODER")) { kind = DECODER; fscanf(f, "%d", &size); // read the size n = size + (1 << size); // n + 2^n parameters outi = size; // start of outputs nouts = 1 << size; // size of outputs } else if (!strcmp(buffer, "MULTIPLEXER")) { kind = MULTIPLEXER; fscanf(f, "%d", &size); // read the size n = size + (1 << size) + 1; // n + 2^n + 1 parameters outi = size + (1 << size); // start of outputs nouts = 1; // size of outputs } // create the gate gate = new_gate(kind, n, size, circ); // read parameters for (i = 0; i < n; i++) { if (fscanf(f, "%16s", buffer) != 1) // read variable { printf("ERROR: %s expected a variable name\n", gate_name[kind]); free_gate(gate); free_circuit(circ); exit(EXIT_FAILURE); } j = add_variable(buffer, circ); gate->params[i] = j; // save variable position if (i >= outi && i <= outi + nouts - 1) circ->vars[j]->out = 1; } add_gate(gate, circ); // add gate to circuit } } fclose(f); return circ; } /* get decimal value from a series of consecutive variables in a gate */ int get_dec_value(int start, int end, Gate *gate, Circuit *circ) { int i, pow2 = 0; int val = 0; for (i = end, pow2 = 0; i >= start && val != -1; i--, pow2++) { if (circ->vars[gate->params[i]]->value == -1) val = -1; else val += circ->vars[gate->params[i]]->value << pow2; } return val; } /* evaluate gate output */ int eval_gate(Gate *gate, Circuit *circ) { int a, b; int i, pos; int output = -1; // cache values for 2 input gates a = circ->vars[gate->params[0]]->value; b = circ->vars[gate->params[1]]->value; switch (gate->kind) { case AND: if (a != -1 && b != -1) output = a & b; circ->vars[gate->params[2]]->value = output; break; case OR: if (a != -1 && b != -1) output = a | b; circ->vars[gate->params[2]]->value = output; break; case NAND: if (a != -1 && b != -1) output = (~(a & b)) & 1; circ->vars[gate->params[2]]->value = output; break; case NOR: if (a != -1 && b != -1) output = (~(a | b)) & 1; circ->vars[gate->params[2]]->value = output; break; case XOR: if (a != -1 && b != -1) output = a ^ b; circ->vars[gate->params[2]]->value = output; break; case NOT: if (a != -1) output = (~a) & 1; circ->vars[gate->params[1]]->value = output; break; case PASS: output = a; circ->vars[gate->params[1]]->value = output; break; case DECODER: pos = get_dec_value(0, gate->size - 1, gate, circ); if (pos == -1) { for (i = 0; i < (1 << gate->size); i++) circ->vars[gate->params[gate->size + i]]->value = -1; } else { for (i = 0; i < (1 << gate->size); i++) circ->vars[gate->params[gate->size + i]]->value = 0; circ->vars[gate->params[gate->size + pos]]->value = 1; output = 1; } break; case MULTIPLEXER: pos = get_dec_value(1 << gate->size, (1 << gate->size) + gate->size - 1, gate, circ); if (pos == -1) circ->vars[gate->params[(1 << gate->size) + gate->size]]->value = -1; else { output = circ->vars[gate->params[pos]]->value; circ->vars[gate->params[(1 << gate->size) + gate->size]]->value = output; } break; } return output; } /* increment input to next value, returns 0 if no error, 1 if all inputs were 1 */ int next_input(Circuit *circ) { int i; int cy = 1; for (i = circ->ninputs - 1; i >= 0 && cy == 1; i--) { if (circ->vars[circ->inputs[i]]->value == 0) { circ->vars[circ->inputs[i]]->value = 1; cy = 0; // don't propagate } else { circ->vars[circ->inputs[i]]->value = 0; cy = 1; // propagate to next } } return cy; } /* print input values */ void print_inputs(Circuit *circ) { int i; for (i = 0; i < circ->ninputs; i++) printf("%d ", circ->vars[circ->inputs[i]]->value); } /* print output values */ void print_outputs(Circuit *circ) { int i; for (i = 0; i < circ->noutputs; i++) printf(" %d", circ->vars[circ->outputs[i]]->value); } /* returns 1 if all outputs are valid */ int valid_outputs(Circuit *circ) { int i; for (i = 0; i < circ->noutputs; i++) if (circ->vars[circ->outputs[i]]->value == -1) return 0; return 1; } /* float all outputs to undefined */ void float_outputs(Circuit *circ) { int i; // float all outputs, ignore the 0, 1 and _ wires for (i = 3; i < circ->nvars; i++) if (circ->vars[i]->out) circ->vars[i]->value = -1; } /* evaluate circuit outputs */ void eval_circuit(Circuit *circ) { int i; int cy = 0; /* set all inputs to zero */ for (i = 0; i < circ->ninputs; i++) circ->vars[circ->inputs[i]]->value = 0; while (!cy) // repeat until there's a carry after incrementing input { print_inputs(circ); /* set all outputs to -1 */ float_outputs(circ); while (!valid_outputs(circ)) // evaluate until all outputs are valid { for (i = 0; i < circ->ngates; i++) // evaluate all gates eval_gate(circ->gates[i], circ); // evaluate gate } printf("|"); print_outputs(circ); printf("\n"); cy = next_input(circ); // get next input state } } int main(int argc, char **argv) { Circuit *circ; if (argc == 1) /* if no input arguments */ { printf("Usage:\n"); printf(" %s \n", argv[0]); return EXIT_SUCCESS; } else if (argc > 2) { printf("Too many arguments\n"); return EXIT_FAILURE; } circ = load_circuit(argv[1]); /* load circuit from argument */ eval_circuit(circ); free_circuit(circ); return EXIT_SUCCESS; }