В РГР по математической логике есть задание под номером 3: составить программу для нахождения СКНФ.
Так вот, в данном посте содержится программа, которая находит СКНФ введенной формулы.
Формат ввода:
A..Z — вводимые буквы
& — конъюнкция
| — дизъюнкция
> — импликация
= — эквивалентность
— — отрицание
Пример:
Вход: -A&-C|-A|B
Выход: (-A|B|C)&(-A|B|-C)
Листинг программы на C:
//--------------------------------------------------------------------------- #include <stdio.h> #pragma hdrstop #include <tchar.h> #include <stdlib.h> #include <math.h> #include <conio.h> //--------------------------------------------------------------------------- #pragma argsused struct STACK { char el; struct STACK *sled; }; void add_el (struct STACK **p, char element)//добавление элемента в список стека { struct STACK *q; q=(struct STACK *)malloc(sizeof(struct STACK)); q->el=element; q->sled=*p; *p=q; } //рекурсивная обработка стека int pars(int opd2[], char op2[],int pr2[], int z, int *i, int sc) { int t,j,fl=0; j=i[0]; j++; while (j>0 && pr2[j]<=pr2[j-1]) //пока в стеке есть элементы и приоритет операции ниже предыдкщей { switch (op2[j-1]) { case '=': //обработка экваваленции if (opd2[j-1-sc]==opd2[j-sc]) opd2[j-1-sc]=1; else opd2[j-1-sc]=0; break; case '>': //обработка импликации if (opd2[j-1-sc]) opd2[j-1-sc]=0; else opd2[j-1-sc]=1; if (opd2[j-1-sc]||opd2[j-sc]) opd2[j-1-sc]=1; else opd2[j-1-sc]=0; break; case '|': //обработка дизъюнкции if (opd2[j-1-sc]||opd2[j-sc]) opd2[j-1-sc]=1; else opd2[j-1-sc]=0; break; case '&': //обработка конъюнкции if (opd2[j-1-sc]&&opd2[j-sc]) opd2[j-1-sc]=1; else opd2[j-1-sc]=0; break; case '-': //обработка отрицания if (opd2[j-1-sc]) opd2[j-1-sc]=0; else opd2[j-1-sc]=1; fl=-1; break; case '(': //обработка скобок (только для первого вложения?) sc++; pars(opd2, op2, pr2, z, &j,sc); sc--; fl=1; j++; break; case ')': fl=2; sc--; } for (t=j;t<=z;t++) //удаление обработанного из массива { if (fl==0) opd2[t-sc]=opd2[t-sc+1]; if (fl==2) { op2[t-sc-1]=op2[t]; pr2[t-sc-1]=pr2[t]; } else { if (sc==0) { op2[t-sc-1]=op2[t-sc]; pr2[t-sc-1]=pr2[t-sc]; } else { op2[t-sc-1]=op2[t-sc+1]; pr2[t-sc-1]=pr2[t-sc+1]; } } } j=j-1; fl=0; } i[0]=j; return opd2[j]; //возврат результата } int res(struct STACK *op1, struct STACK *opd1, struct STACK *prior,int znach[]) { struct STACK *op; //стек операций struct STACK *opd, *pr; //стек операндов и приоритетов int fl=0,i,j=0,opd2[100],pr2[100],z,t; //указатели массивов char op2[100];//*op2=NULL; for (opd=opd1,i=0;opd!=NULL;opd=opd->sled,i++); //определение количесва операндов //opd2 = (int*)malloc((i+1)*sizeof(int)); //выделение памяти под массив for (j = i,opd=opd1; j>0; j--,opd=opd->sled) { opd2[j-1]=znach[opd->el-'A']; //запись стека в массив с переводом в числа } for (op=op1,i=0;op!=NULL;op=op->sled,i++); //определение количесва операций //op2 = (char*)malloc((i+1)*sizeof(char)); //выделение памяти под массив for (j = i,op=op1; j>0; j--,op=op->sled) { op2[j-1]=op->el; //запись стека в массив } z=i; for (pr=prior,i=0;pr!=NULL;pr=pr->sled,i++); //определение количесва приоритетов //pr2 = (int*)malloc((i+1)*sizeof(int)); //выделение памяти под массив for (j = i,pr=prior; j>0; j--,pr=pr->sled) { pr2[j-1]=pr->el; //запись стека в массив } for (i=0;i<z;i++) { t=pars(opd2,op2,pr2,z,&j,0); //выполнение обработки } return opd2[0]; //возврат результата } int _tmain(int argc, _TCHAR* argv[]) { struct STACK *op, *opd, *prior; //стеки операций, операндов, приоритетов char el; //один символ строки int i,j,max=0,*znach,tmp,fl; FILE *f; f=fopen("out.txt","w"); op=opd=prior=NULL; while((el=getchar())!='\n') //чтение до конца строки { switch (el) { //распределение символов case '=': add_el(&op,el); add_el(&prior,1); break; case '>': add_el(&op,el); add_el(&prior,2); break; case '|': add_el(&op,el); add_el(&prior,3); break; case '&': add_el(&op,el); add_el(&prior,4); break; case '-': add_el(&op,el); add_el(&prior,5); break; case '(': add_el(&op,el); add_el(&prior,10); break; case ')': add_el(&op,el); add_el(&prior,0); break; default: add_el(&opd,el); if (el>max) max=el; } } add_el(&prior,0); j=max-'A'; //число букв znach = (int*)malloc((j+1)*sizeof(int)); //выделение памяти под значения for (i=0;i<pow(2,max-'A'+1);i++) { tmp=i; j=max-'A'; //заполнение масива znach двоичным числом do { znach[2*(max-'A')-j]=tmp%2; tmp=tmp/2; j++; } while (tmp); while(j<=2*(max-'A')) { znach[2*(max-'A')-j]=0; j++; } fprintf(f,"%d %d %d ",znach[0],znach[1],znach[2]); if (res(op,opd,prior,znach)==0) //если результат = 0 { fprintf(f,"%d\n",res(op,opd,prior,znach)); if (fl==1) { putch('&'); } putch('('); for (j=0;j<max-'A'+1;j++) //вывод выражения { if (znach[j]==1) { //добавление отрицания putch('-'); } putch('A'+j); if (j!=max-'A') putch('|'); } putch(')'); fl=1; } } getch(); return 0; } //--------------------------------------------------------------------------- |
PS программа работает через-одно-место (особенно со скобками), поэтому пользоваться ей не рекомендуется 🙂