Нахождение СКНФ

В РГР по математической логике есть задание под номером 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 программа работает через-одно-место (особенно со скобками), поэтому пользоваться ей не рекомендуется :-)

Запись опубликована в рубрике С с метками , , , . Добавьте в закладки постоянную ссылку.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *