aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile4
-rw-r--r--qm.c122
-rw-r--r--qm.h27
-rw-r--r--src/qm.c212
-rw-r--r--src/qm.h39
5 files changed, 253 insertions, 151 deletions
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 <stdio.h>
-#include <stdlib.h>
-#include <limits.h>
-#include <stdbool.h>
-#include <string.h>
-#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 <string.h>
-
-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 <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <stdbool.h>
+#include <string.h>
+#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
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-27 21:26:22 +0000