From b0d5501f1f23aa46a217497ed899ec51aa571f1f Mon Sep 17 00:00:00 2001 From: jwansek Date: Sat, 28 Nov 2020 16:19:19 +0000 Subject: began work on merging terms in turn --- Makefile | 4 +- qm.c | 122 ------------------------------------ qm.h | 27 -------- src/qm.c | 212 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/qm.h | 39 ++++++++++++ 5 files changed, 253 insertions(+), 151 deletions(-) delete mode 100644 qm.c delete mode 100644 qm.h create mode 100644 src/qm.c create mode 100644 src/qm.h diff --git a/Makefile b/Makefile index dd56f43..2688893 100644 --- a/Makefile +++ b/Makefile @@ -1,5 +1,5 @@ -./quineMcCluskey : qm.c - gcc qm.c -o ./quineMcCluskey +./quineMcCluskey : src/qm.c + gcc src/qm.c -o ./quineMcCluskey clean : rm -f ./quineMcCluskey diff --git a/qm.c b/qm.c deleted file mode 100644 index 9c66f8a..0000000 --- a/qm.c +++ /dev/null @@ -1,122 +0,0 @@ -#include -#include -#include -#include -#include -#include "qm.h" - -#define VALID_VARIABLES "ABCDEFGHIJKLMNOPQRSTUVXYZ" - -int main(int argc, char* argv[]) { - if (argc != 2) { - fprintf(stderr, "Incorrect number of arguments provided.\n"); - } - - parseDNFStr(argv[1]); -} - -DNF parseDNFStr(const char* inpStr) { - //remove whitespace - char inpBfr[strlen(inpStr)]; - int i = 0, j = 0; - while (inpStr[i] != '\0') { - if (inpStr[i] != ' ') { - inpBfr[j++] = inpStr[i]; - } - i++; - } - inpBfr[j] = '\0'; - - DNF dnf; - dnf.numTerms = strcnt(inpBfr, '+') + 1; - - //split up, by '+'s - const char* delim = "+"; - char* subStr = strtok(inpBfr, delim); - i = 0; - while (subStr != NULL) { - dnf.terms[i++] = parseDNFTerm(subStr); - // printf("term %i: '%s'\n", i, subStr); - subStr = strtok(NULL, delim); - } - - // printf("%i terms\n", dnf.numTerms); - printForm(dnf); - printForm2(dnf); - return dnf; -} - -DNFTerm parseDNFTerm(const char* termStr) { - DNFTerm term; - term.numVars = 0; - char c; - for (int i = 0; i < INT_MAX; i++) { - c = termStr[i]; - if (c == '\0') { - break; - } - if (strcnt(VALID_VARIABLES, c) == 1) { - term.vars[term.numVars] = (Variable){c, termStr[i - 1] == '-'}; - // printf("%i %c\n", term.numVars, term.vars[term.numVars]); - term.numVars++; - } - } - return term; -} - -// returns an integer of how many times a char was found in a char -// array -unsigned int strcnt(const char* str, const char cnt) { - int count = 0; - for (int i = 0; i < INT_MAX; i++) { - char c = str[i]; - if (c == '\0') { - break; - } - if (c == cnt) { - count++; - } - } - return count; -} - -void printForm(const DNF form) { - for (int i = 0; i < form.numTerms; i++) { - printf("("); - DNFTerm term = form.terms[i]; - - for (int j = 0; j < term.numVars; j++) { - if (term.vars[j].not_) { - printf("¬"); - } - printf("%c", term.vars[j].var); - if (term.numVars - 1 != j) { - printf("∧"); - } - } - - if (form.numTerms - 1 != i) { - printf(") ∨ "); - } - } - printf(")\n"); -} - -void printForm2(const DNF form) { - for (int i = 0; i < form.numTerms; i++) { - DNFTerm term = form.terms[i]; - - for (int j = 0; j < term.numVars; j++) { - printf("%c", term.vars[j].var); - if (term.vars[j].not_) { - printf("'"); - } - } - - if (form.numTerms - 1 != i) { - printf(" + "); - } - } - printf("\n"); -} - diff --git a/qm.h b/qm.h deleted file mode 100644 index 173dd4c..0000000 --- a/qm.h +++ /dev/null @@ -1,27 +0,0 @@ -#ifndef QM_C -#define QM_C - -#include - -typedef struct { - char var; - bool not_; -} Variable; - -typedef struct { - unsigned int numVars; - Variable vars[26]; -} DNFTerm; - -typedef struct { - unsigned int numTerms; - DNFTerm terms[100]; -} DNF; - -unsigned int strcnt(const char* str, const char cnt); -DNF parseDNFStr(const char* inpStr); -DNFTerm parseDNFTerm(const char* termStr); -void printForm(const DNF form); -void printForm2(const DNF form); - -#endif \ No newline at end of file diff --git a/src/qm.c b/src/qm.c new file mode 100644 index 0000000..2b3677a --- /dev/null +++ b/src/qm.c @@ -0,0 +1,212 @@ +#include +#include +#include +#include +#include +#include "qm.h" + +#define VALID_VARIABLES "ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz" + +int main(int argc, char* argv[]) { + if (argc != 2) { + fprintf(stderr, "Incorrect number of arguments provided.\n"); + } + + DNF startDNF = parseDNFStr(argv[1]); + SimplifiedTableItem simplifiedTable[startDNF.numTerms]; + unsigned int simplifiedTableLength = startDNF.numTerms; + setupMergeTable(simplifiedTable, &startDNF); + + mergeTermsInTurn(simplifiedTable, &startDNF.numTerms); +} + +void setupMergeTable(SimplifiedTableItem simplifiedTable[], DNF* dnf) { + for (int i = 0; i < dnf->numTerms; i++) { + simplifiedTable[i].term = dnf->terms[i]; + simplifiedTable[i].simplifiedIndexes[0] = i; + simplifiedTable[i].numIndexes = 1; + } +} + +void mergeTermsInTurn(SimplifiedTableItem simplifiedTable[], unsigned int* length) { + SimplifiedTableItem nextIteration[*length]; + for (int i = 0; i < *length; i++) { + for (int j = 0; j < *length; j++) { + if (i == j) { + continue; + } + + if (canMergeTerms(&simplifiedTable[i].term, &simplifiedTable[j].term)) { + // printDNFTerm(&simplifiedTable[i].term); + // printf(" + "); + // printDNFTerm(&simplifiedTable[j].term); + // printf(" = "); + DNFTerm mergedTerm = mergeTerms(&simplifiedTable[i].term, &simplifiedTable[j].term); + // printDNFTerm(&mergedTerm); + // printf("\n------\n"); + } + } + } +} + +bool canMergeTerms(const DNFTerm* term1, const DNFTerm* term2) { + unsigned int sameTerms = 0; + for (int i = 0; i < term1->numVars; i++) { + for (int j = 0; j < term2->numVars; j++) { + if (term1->vars[i].not_ == term2->vars[j].not_ && term1->vars[i].var == term2->vars[j].var) { + sameTerms++; + } + } + } + return term1->numVars - sameTerms == 1; +} + +DNFTerm mergeTerms(const DNFTerm* term1, const DNFTerm* term2) { + DNFTerm mergedTerm; + mergedTerm.numVars = 0; + for (int i = 0; i < term1->numVars; i++) { + for (int j = 0; j < term2->numVars; j++) { + if (term1->vars[i].not_ == term2->vars[j].not_ && term1->vars[i].var == term2->vars[j].var) { + mergedTerm.vars[mergedTerm.numVars++] = (Variable){term1->vars[i].var, term1->vars[i].not_}; + } + } + } + return mergedTerm; +} + +bool termInTable(const SimplifiedTableItem simplifiedTable[], const unsigned int* length, const DNFTerm* term) { + for (int i = 0; i < *length; i++) { + if (termsAreEqual(&simplifiedTable[i].term, term)) { + return true; + } + } + return false; +} + +bool termsAreEqual(const DNFTerm* term1, const DNFTerm* term2) { + if (term1->numVars != term2->numVars) { + return false; + } + + //TODO +} + +DNF parseDNFStr(const char* inpStr) { + //remove whitespace + char inpBfr[strlen(inpStr)]; + int i = 0, j = 0; + while (inpStr[i] != '\0') { + if (inpStr[i] != ' ') { + inpBfr[j++] = inpStr[i]; + } + i++; + } + inpBfr[j] = '\0'; + + DNF dnf; + dnf.numTerms = strcnt(inpBfr, '+') + 1; + + char notChar; + int relIndex; + if (strcnt(inpBfr, "'"[0]) > 0) { + dnf.notChar = "'"[0]; + relIndex = 1; + } else if (strcnt(inpBfr, '-') > 0) { + dnf.notChar = '-'; + relIndex = -1; + } + if (strcnt(inpBfr, "'"[0]) > 0 && strcnt(inpBfr, '-') > 0) { + fprintf(stderr, "Inconsistent notation used for not.\n"); + exit(EXIT_FAILURE); + } + + //split up, by '+'s + const char* delim = "+"; + char* subStr = strtok(inpBfr, delim); + i = 0; + while (subStr != NULL) { + dnf.terms[i++] = parseDNFTerm(subStr, dnf.notChar, relIndex); + // printf("term %i: '%s'\n", i, subStr); + subStr = strtok(NULL, delim); + } + + return dnf; +} + +DNFTerm parseDNFTerm(const char* termStr, const char notChar, const int relIndex) { + DNFTerm term; + term.numVars = 0; + char c; + for (int i = 0; i < INT_MAX; i++) { + c = termStr[i]; + if (c == '\0') { + break; + } + if (strcnt(VALID_VARIABLES, c) == 1) { + term.vars[term.numVars++] = (Variable){c, termStr[i + relIndex] == notChar}; + } + } + return term; +} + +unsigned int strcnt(const char* str, const char cnt) { + // returns an integer of how many times a char was found in a char + // array + int count = 0; + for (int i = 0; i < INT_MAX; i++) { + char c = str[i]; + if (c == '\0') { + break; + } + if (c == cnt) { + count++; + } + } + return count; +} + +void printForm(const DNF* form) { + for (int i = 0; i < form->numTerms; i++) { + printf("("); + DNFTerm term = form->terms[i]; + printDNFTerm(&term); + + if (form->numTerms - 1 != i) { + printf(") ∨ "); + } + } + printf(")\n"); +} + +void printDNFTerm(const DNFTerm* term) { + for (int j = 0; j < term->numVars; j++) { + if (term->vars[j].not_) { + printf("¬"); + } + printf("%c", term->vars[j].var); + if (term->numVars - 1 != j) { + printf("∧"); + } + } +} + +void printForm2(const DNF* form) { + for (int i = 0; i < form->numTerms; i++) { + DNFTerm term = form->terms[i]; + + for (int j = 0; j < term.numVars; j++) { + if (term.vars[j].not_ && form->notChar == '-') { + printf("-"); + } + printf("%c", term.vars[j].var); + if (term.vars[j].not_ && form->notChar == "'"[0]) { + printf("'"); + } + } + + if (form->numTerms - 1 != i) { + printf(" + "); + } + } + printf("\n"); +} \ No newline at end of file diff --git a/src/qm.h b/src/qm.h new file mode 100644 index 0000000..2b001bb --- /dev/null +++ b/src/qm.h @@ -0,0 +1,39 @@ +#ifndef QM_C +#define QM_C + +typedef struct { + char var; + bool not_; +} Variable; + +typedef struct { + unsigned int numVars; + Variable vars[26]; +} DNFTerm; + +typedef struct { + unsigned int numTerms; + DNFTerm terms[100]; + char notChar; +} DNF; + +typedef struct { + DNFTerm term; + unsigned int simplifiedIndexes[100]; + unsigned int numIndexes; +} SimplifiedTableItem; + +unsigned int strcnt(const char* str, const char cnt); +void setupMergeTable(SimplifiedTableItem simplifiedTable[], DNF* dnf); +void mergeTermsInTurn(SimplifiedTableItem simplifiedTable[], unsigned int* length); +bool canMergeTerms(const DNFTerm* term1, const DNFTerm* term2); +DNFTerm mergeTerms(const DNFTerm* term1, const DNFTerm* term2); +bool termInTable(const SimplifiedTableItem simplifiedTable[], const unsigned int* length, const DNFTerm* term); +bool termsAreEqual(const DNFTerm* term1, const DNFTerm* term2); +DNF parseDNFStr(const char* inpStr); +DNFTerm parseDNFTerm(const char* termStr, const char notChar, const int relIndex); +void printDNFTerm(const DNFTerm* term); +void printForm(const DNF* form); +void printForm2(const DNF* form); + +#endif \ No newline at end of file -- cgit v1.2.3