逻辑表达式化简器 - 使用 Prime Implicant 算法
![逻辑表达式化简器 - 使用 Prime Implicant 算法 逻辑表达式化简器 - 使用 Prime Implicant 算法](https://img.cveoy.top/0/60561194595E04C757D981B42ED337BA.webp)
#include <stdio.h> #include <stdlib.h> #include <string.h>
#define MAX_TERMS 16 #define MAX_VARS 26
/* 化简结果 */ struct result { int terms[MAX_TERMS]; int num_terms; };
/* 存储初始表达式 */ struct expression { char input[100]; };
/* 存储化简结果 */ struct equation { int variables[MAX_VARS]; int num_vars; struct result *minimum_terms; };
/* 获取二进制表示中 1 的个数 */ int bitcount(unsigned int bits) { int count = 0; while(bits) { count++; bits &= bits - 1; } return count; }
/* 计算两个二进制表示不同的位数 */ int hamming_distance(unsigned int a, unsigned int b) { return bitcount(a ^ b); }
/* 将两个二进制表示的值合并,如果有不同的地方则为 -1 */ int merge(unsigned int a, unsigned int b) { unsigned int x = a ^ b;
if(bitcount(x) != 1) {
return -1;
}
int i = 0;
while(x) {
i++;
x >>= 1;
}
return i;
}
/* 对一个数值获取其二进制表示中从左至右的某一位的值 */ int get_bit(unsigned int x, int pos) { return (x >> pos) & 1; }
/* 判断两个 term 是否属于同一组 */ int group_has_term(unsigned int group, int num) { return get_bit(group, num); }
/* 根据某个值,寻找它能够合并的 group / struct result find_mergeable(struct result* groups, int num_groups, int val) { int i, j; struct result *res = NULL;
for(i = 0; i < num_groups && !res; i++) {
for(j = 0; j < groups[i].num_terms; j++) {
if(merge(groups[i].terms[j], val) != -1) {
res = &groups[i];
break;
}
}
}
return res;
}
/* 添加一个 term 到某个 group 中 / void add_term(struct result group, int term) { group->terms[group->num_terms++] = term; }
/* 在 groups 中删除掉一个 group */ void drop_group(struct result *groups, int group_num, int num_groups) { int i; for(i = group_num + 1; i < num_groups; i++) { groups[i - 1] = groups[i]; } }
/* 从所有的 term 中找出不相交并且最小的子集,并返回包含这些子集的结果集 / struct result find_minimum_terms(unsigned int *terms, int num_terms) { int i, j, k; int num_groups = num_terms; struct result groups[MAX_TERMS]; struct result *minimum_terms = NULL;
/* 初始化 groups,每个单独的 term 属于一个不同的 group */
for(i = 0; i < num_terms; i++) {
groups[i].terms[0] = terms[i];
groups[i].num_terms = 1;
}
/* 尝试对所有的 group 合并,直至合并不再发生 */
while(num_groups > 1) {
struct result new_groups[MAX_TERMS];
int num_new_groups = 0;
/* 遍历所有的 group */
for(i = 0; i < num_groups; i++) {
for(j = i+1; j < num_groups; j++) {
int m = merge(groups[i].terms[0], groups[j].terms[0]);
/* 如果两个 group 可以合并,则将它们合并 */
if(m != -1) {
struct result *merge_group = &new_groups[num_new_groups++];
merge_group->num_terms = 0;
/* 将两个 group 的 term 合并到一个新的 group 中 */
for(k = 0; k < groups[i].num_terms; k++) {
add_term(merge_group, groups[i].terms[k]);
}
for(k = 0; k < groups[j].num_terms; k++) {
add_term(merge_group, groups[j].terms[k]);
}
/* 标记之前的 groups 已经被合并 */
groups[i].num_terms = groups[j].num_terms = 0;
}
}
}
/* 将未被合并的 groups 添加到新的 groups 中 */
for(i = 0; i < num_groups; i++) {
if(groups[i].num_terms > 0) {
new_groups[num_new_groups++] = groups[i];
}
}
/* 将新的 groups 覆盖到旧的 groups */
memcpy(groups, new_groups, num_new_groups * sizeof(struct result));
num_groups = num_new_groups;
}
/* 将包含最少的 term 的 group 作为最小项 */
minimum_terms = &(groups[0]);
for(i = 1; i < num_groups; i++) {
if(groups[i].num_terms < minimum_terms->num_terms) {
minimum_terms = &(groups[i]);
}
}
return minimum_terms;
}
/* 将表达式中的字符映射为二进制数值 */ unsigned int map_input(char input) { if(input == '-') { return 2; } else if(input >= 'A' && input <= 'Z') { return 1 << (input - 'A'); } else { return 0; } }
/* 获取所有的 term 的二进制表示 */ void generate_terms(unsigned int *terms, int num_terms, char *input) { int i; for(i = 0; i < num_terms; i++) { unsigned int term = 0; int j; for(j = 0; input[j]; j++) { term |= map_input(input[j * num_terms + i]) << j; } terms[i] = term; } }
/* 将某个变量添加到一个 equation 中,如果已经添加过,则返回之前的索引 */ int add_variable(struct equation *eq, int var) { int i; for(i = 0; i < eq->num_vars; i++) { if(eq->variables[i] == var) { return i; } } eq->variables[eq->num_vars++] = var; return i; }
/* 获取某个 term 的字符表示 */ void unmap_term(char *output, int num_vars, unsigned int term) { int i; for(i = 0; i < num_vars; i++) { if(get_bit(term, i) == 1) { output[i] = 'A' + i; } else if(get_bit(term, i) == 0) { output[i] = 'A' + i; output[i + num_vars] = '''; } else { output[i] = '-'; } } output[2 * num_vars] = '\0'; }
/* 对所有的最小项进行 prime implicant 算法 */ void find_prime_implicants(struct result *prime_implicants, int *num_pi, unsigned int *terms, int num_terms, int num_vars) { int i, j;
/* 初始化初始 equation */
struct equation *eq_list = (struct equation*) malloc(num_vars * sizeof(struct equation));
for(i = 0; i < num_vars; i++) {
eq_list[i].num_vars = 0;
eq_list[i].minimum_terms = NULL;
}
/* 获取所有的变量,并插入到对应的 equation 中 */
for(i = 0; i < num_terms; i++) {
for(j = 0; j < num_vars; j++) {
if(get_bit(terms[i], j) != 2) {
int var = add_variable(&eq_list[j], j);
eq_list[j].minimum_terms = find_minimum_terms(terms, num_terms);
add_term(&eq_list[j].minimum_terms[var], i);
}
}
}
/* 递归地求解所有的最小项 */
struct result candidates[MAX_TERMS * 2];
int num_candidates = 0;
for(i = 1; i < num_terms; i++) {
candidates[num_candidates].terms[0] = terms[i - 1];
candidates[num_candidates].terms[1] = terms[i];
candidates[num_candidates].num_terms = 2;
num_candidates++;
}
i = 0;
while(i < num_candidates) {
struct result *ci = &candidates[i];
/* 首先,判断当前的 candidate 是否为 prime implicant,并将之存储到 pi_list 中 */
int is_pi = 0;
for(j = 0; j < num_terms; j++) {
if(hamming_distance(terms[j], ci->terms[0]) == 0) {
is_pi = 1;
break;
}
}
if(is_pi) {
prime_implicants[(*num_pi)++] = *ci;
}
/* 其次,将所有未被包含的最小项添加到当前的 candidate 中 */
for(j = 0; j < num_terms; j++) {
int k;
for(k = 0; k < ci->num_terms; k++) {
if(ci->terms[k] == terms[j]) {
break;
}
}
if(k == ci->num_terms) {
is_pi = 0;
int has_mergeable = 0;
struct result *mergeable = find_mergeable(ci, ci->num_terms, terms[j]);
/* 利用 prime implicant 来尽可能的合并每个 term */
if(mergeable) {
has_mergeable = 1;
for(k = 0; k < mergeable->num_terms; k++) {
if(hamming_distance(mergeable->terms[k], terms[j]) > 1) {
has_mergeable = 0;
}
}
if(has_mergeable) {
mergeable->terms[mergeable->num_terms++] = terms[j];
}
}
/* 如果无法使用 prime implicant 合并,则创建一个新的 candidate */
if(!has_mergeable) {
struct result *new_ci = &candidates[num_candidates++];
new_ci->num_terms = ci->num_terms + 1;
memcpy(new_ci->terms, ci->terms, ci->num_terms * sizeof(int));
new_ci->terms[new_ci->num_terms - 1] = terms[j];
}
}
}
i++;
}
free(eq_list);
}
/* 将两个 result 中都存在的 term 进行合并 */ void merge_terms(unsigned int *output, int *num_terms, struct result *r1, struct result *r2) { int i, j;
for(i = 0; i < r1->num_terms; i++) {
for(j = 0; j < r2->num_terms; j++) {
if(r1->terms[i] == r2->terms[j]) {
output[(*num_terms)++] = r1->terms[i];
}
}
}
}
/* 化简表达式 */ void simplify_expression(struct expression *exp) { int i, j; int num_terms = strlen(exp->input) / 4; unsigned int terms[MAX_TERMS]; int num_vars = strlen(exp->input) / num_terms; struct result minimum_terms; struct result prime_implicants[MAX_TERMS]; int num_pi = 0; unsigned int final_terms[MAX_TERMS]; int num_final_terms = 0; char output_buffer[2 * MAX_VARS + 1];
/* 将表达式中的字符转换成二进制位 */
generate_terms(terms, num_terms, exp->input);
/* 获取所有的最小项 */
minimum_terms = *find_minimum_terms(terms, num_terms);
/* 对最小项进行 prime implicant 分解 */
find_prime_implicants(prime_implicants, &num_pi, terms, num_terms, num_vars);
/* 将 prime implicant 以及未被完全包含的最小项合并成 final terms */
for(i = 0; i < minimum_terms.num_terms; i++) {
int has_match = 0;
for(j = 0; j < num_pi; j++) {
if(group_has_term(&prime_implicants[j], minimum_terms.terms[i])) {
has_match = 1;
break;
}
}
if(!has_match) {
final_terms[num_final_terms++] = minimum_terms.terms[i];
}
}
for(i = 0; i < num_pi; i++) {
struct result *pi = &prime_implicants[i];
for(j = 0; j < minimum_terms.num_terms; j++) {
if(group_has_term(&minimum_terms, pi->terms[j])) {
break;
}
}
if(j == minimum_terms.num_terms) {
merge_terms(final_terms, &num_final_terms, &prime_implicants[i], &minimum_terms);
}
}
/* 对所有的 final terms 进行可化简操作 */
printf("化简后的表达式:");
for(i = 0; i < num_final_terms; i++) {
unmap_term(output_buffer, num_vars, final_terms[i]);
printf("%s", output_buffer);
if(i != num_final_terms - 1) {
printf(" + ");
}
}
printf("\n");
}
int main(void) { struct expression exp;
printf("请输入逻辑表达式(如 AB+AC):");
scanf("%s", exp.input);
simplify_expression(&exp);
return 0;
}
/* 例如,输入为 AB+ABC,则输出结果为: 化简后的表达式:AB */
原文地址: https://cveoy.top/t/topic/nBcE 著作权归作者所有。请勿转载和采集!