바람이 머문 언덕
퀸 맥클러스키 법칙 본문
퀸 맥클러스키 법칙을 이용해서 논리식 간소화하는 프로그램을 c로 작성해 보았습니다.
퀸 맥클러스키 법칙은 2개의 민터엄이 1개의 변수만 차이가 난다면 그 그변수를 제거하여 문자가 하나 작은항으로 줄일 수있는데 이 과정은 모던 민트미엄에 대해서 철저하게 조사해 마칠 때까지 반복하면 된다.
0000, 0001, 1001, 1010, 1011, 100_ 있으면 0000과 0001은 하나만 다르므로 000_으로 하나가 줄 일 수 있으며 1001과 1011도 10_1로 줄 일 수 있다
이런 식으로 모든항과 새로 생긴항에 대해서도 되풀이 해서 더 이상 제거가 생기지 않을 때 까지 반복 한다.
부울 함수를 퀸 맥클라스키 법칙을 이용해서 간소화하는 직접 작성한 프로그램 소스와 실행 파일을 올려 놓았습니다.
#include ".\qmkey.h"
#include <stdio.h>
#include <string.h>
//#include <iostream>
#define null 0
QMkey::QMkey(void)
{
}
QMkey::~QMkey(void)
{
}
keylist *QMkey::DecimalToKeyList(int val)
{
int i=0, k=skeyvalue.ikeycount;
keylist *temp=MakeNode();
while(--k>=0)
{
temp->buf[k] = (val%2)+'0';
val /=2;
}
if(val) { DelNode(temp); return null; }
return temp;
}
keylist *QMkey::DecimalToKey(char *val)
{
int i, k;
keylist *prev=null, *top=null, *tlist=null, *temp;
for(i=k=0; val[i]!='\0'; i++)
{
if(val[i]==',')
{
if(val[i+1]==',' || val[i+1]=='\0') { if(tlist) DelList(tlist); return null; } //return false;
val[i]='\0';
temp = DecimalToKeyList(atoi(val+k));
if(temp)
{
if(tlist) { prev=top; top=top->next=temp; }
else top=tlist=temp;
}
else { if(tlist) DelList(tlist); return null; }//return false;
k=i+1;
}
else if(val[i]<'0' || val[i]>'9') //return false;
{
if(tlist) DelList(tlist); return null;
}
}
val[i]='\0';
temp = DecimalToKeyList(atoi(val+k));
if(temp)
{
if(tlist) { prev=top; top=top->next=temp; }
else top=tlist=temp;
}
else // 입력 값 초과 에러
{
while(tlist)
{
temp=tlist;
DelList(tlist);
tlist=temp->next;
}
return null;
}
return tlist;
}
bool QMkey::KeyInput(char *buf)
{
int i, k, t;
keylist *temp;
list= NULL;
for( i=0, k=0; buf[i]!='\0'; i++) // 공백 제거
{
if(buf[i]!=' '&& buf[i]!='\r' && buf[i]!='\n') buf[k++]=buf[i]; //
}//*/
buf[k]='\0';
i=SptKey(buf);
if(i==0) return false;
for(k=i, t=1; buf[k]!='\0'; k++)
{
if(buf[k]>='0' && buf[k]<='9') { t=0; break; }
}
if(t) // 논리 문자 이면
{
buf+=i;
//ReMake(buf); // 괄호와 '^' 제거하여 AND, OR, NAND로 만 표시
list=MakeKey( buf);
if(buf[0]=='\0') return false;
if(list) list=MakeInvalToList(list);
else { buf[0]='0'; buf[1]='\0'; return true; }
}
else
{
list=DecimalToKey( buf+=k);
if(!list) return false;
}
list=CkKey(list);
temp=list;
t=2;
k=0;
if(list->next==null) // 논리 값이 '1' 인가 체크
{
t = i = 0;
while(list->buf[i]!='\0')
{
if(list->buf[i]!='_') { t=1; break; }
i++;
}
}
if(t==0) buf[k++]='1'; // '1'이면
else // '1'이 아니면
{
while( list!=NULL )
{
k+=BinToKey(buf+k, list->buf); // 이진값을 논리 값으로 변환
if(list=list->next) buf[k++]='+';
}
}
list=temp;
if(list) DelList(list);
else buf[k++]='0';
buf[k]='\0';
DelChar(skeyvalue.ckeyvalue);
return true;
}
int QMkey::SptKey(char *buf) // 입력 값에서 키 맵 분리
{
int i=2, k;
if((buf[0]!='F')&&(buf[0]!='f')&&(buf[1]!='(')) return 0;
for(k=0; buf[i]!=')' && buf[i]!='\0'; i++)
if((buf[i]>='a'&&buf[i]<='z') || (buf[i]>='A'&&buf[i]<='Z')) k++;
if(!k || buf[i+1]!='=' || buf[i+2]=='\0') return 0; // 논리 문자 키값이 없으면
skeyvalue.ckeyvalue=MakeChar(k);
skeyvalue.ckeyvalue[k]='\0';
skeyvalue.ikeycount=k;
for(i=2, k=0; buf[i]!=')'; i++)
if((buf[i]>='a'&&buf[i]<='z') || (buf[i]>='A'&&buf[i]<='Z')) skeyvalue.ckeyvalue[k++]=buf[i];
return i+2;
}
int QMkey::BinToKey(char *buf,char *val) //이진수를 논리 문자로 변경
{
int i, j;
for( i=j=0; val[i]!='\0'; i++)
{
if((val[i]!='_'))
{
buf[j++]=skeyvalue.ckeyvalue[i];
if(val[i]=='0') buf[j++]='\'';
}
}
buf[j]='\0';
return j;
}
keylist *QMkey::MakeKey( char *val) // 논리식을 분리하여 리스트로 만든다.
{
//val[0]='\0'; 에러 일때
printf("<%s>",val);
int i, k, is;
char *buf=MakeChar(skeyvalue.ikeycount);
for(k=0; k<skeyvalue.ikeycount; k++) buf[k]='_'; buf[k]='\0'; // 돈케어로 초기화
keylist *temp, *top=null, *tlist=null; // , *prev
top = tlist=null;
for(i=0; val[i]!='\0'; i++)
{
if((val[i]>='a'&&val[i]<='z') || (val[i]>='A'&&val[i]<='Z')) // key 값을 위치 정보로 바꾼다.
{
for(k=0, is=1; skeyvalue.ckeyvalue[k]!='\0'; k++)
{
if(val[i]==skeyvalue.ckeyvalue[k])
{
if(val[i+1]=='\'')
{
if(buf[k]!='1') { buf[k]='0'; i++; is=1; }
else is=0;
}
else
{
if(buf[k]!='0') { buf[k]='1'; is=1; }
else is=0;
}
if(is==1) break;
else //if(s==0) // 서로 반대 되는 논리 값이 있어서 0이되면
{
while( val[i]!='\0' && val[i]!='+' ) i++; // 돈케어로 초기화
if(val[i]=='\0') { DelChar(buf); buf=null; return tlist;}
else { for(k=0; k<skeyvalue.ikeycount; k++) buf[k]='_'; buf[k]='\0'; }
is=1; break;
}//*/
}
}
if(is==0) { DelList(tlist); val[0]='\0'; DelChar(buf); return null; }
}
else if(val[i]=='+' )// || val[i+1]=='\0') // 논리 식을 하나의 단위로 나눈다
{
if(i&&(val[i+1]=='+'|| val[i+1]=='\0'))
{
if(tlist) DelList(tlist); val[0]='\0'; // val[0]='\0' 에러
DelChar(buf); return null;
}
temp=MakeNode();
strcpy(temp->buf, buf);
for(k=0; k<skeyvalue.ikeycount; k++) buf[k]='_'; buf[k]='\0';
if(tlist)
{
top->next=temp;
top=temp;
}
else top=tlist=temp;
}
else { DelList(tlist); val[0]='\0'; DelChar(buf); return null; } // val[0]='\0' 에러
//else if(val[i]!=10) return false; // gets 함수로 입력 받을시 들어오는 문자(10)는제외
}
if(buf != null)
{
temp=MakeNode();
strcpy(temp->buf, buf);
if(tlist) top->next=temp;
else top=tlist=temp;
DelChar(buf);
}
return tlist;
}
keylist *QMkey::MakeInvalToList(keylist *blist) // 돈 케오 부분을 이진수로 변환
{
char *buf, *cbuf;
int i, j, k, ik, is;
keylist *temp, *temp2, *tlist=null, *top=null;
buf=MakeChar(skeyvalue.ikeycount);
cbuf=MakeChar(skeyvalue.ikeycount);
if(buf)
{
while(blist)
{
for(ik=i=0; blist->buf[i]!='\0'; i++) { if(blist->buf[i]=='_') ik++; }
buf[ik]='\0'; // 돈케어 갯수에 따라 문자열 종료 위치를 저장한다.
if(ik) // '_' 문자가 하나라도 있어면
{ /////////////////////////////////////
is=ik; // 돈케어 갯수 ik를 is에 저장
for(i=0, k=1; i<ik; i++) k*=2;
for(i=0 ; i<k; i++)
{
j = is;
ik = i;
while(j>0) { buf[--j] = (ik%2)+'0'; ik/=2; } // i의 값을 이진수로 변환
strcpy(cbuf, blist->buf); // 돈케어에 이진 값을 넣기 위해서 cbuf에 카피
for(ik=j=0 ; j<skeyvalue.ikeycount; j++) // 돈케어 부분에 논리 값 넣기
if(cbuf[j]=='_') cbuf[j]=buf[ik++];
temp=tlist;
while(temp) // 같은 값이 존재 하는지 체크
{
if(strcmp(cbuf, temp->buf)==0) break;
temp=temp->next;
}
temp2=blist->next; // 다음에 수행 할 리스트 위치 기억
if(temp==null) // 같은 데이터가 없으면 노드 추가
{
temp= MakeNode(); // 노드 생성
strcpy(temp->buf, cbuf);
if(top) top=top->next=temp;
else top=tlist=temp; ////////puts(temp->buf); //////////////
}
}
}
else //
{
temp2=blist->next; // 다음에 수행 할 리스트 위치 기억
if(top) top=top->next=blist; // 추가
else top=tlist=blist;
}
blist=temp2;
}
}
DelChar(buf);
DelChar(cbuf);
if(top) top->next=null;
return tlist;
}
void QMkey::SamplifyKey(keylist *blist, keylist **tlist, keylist **top)
{
keylist *slist=blist->next, *temp = null, *ltemp;
char *bkey, *tbuf;
bkey = blist->buf;
tbuf = MakeChar(skeyvalue.ikeycount);
tbuf[skeyvalue.ikeycount]='\0';
int lenkey=skeyvalue.ikeycount, ick, i;
while(slist!=null)
{
for(ick=-1, i=0; i<lenkey; i++)
{
if(slist->buf[i]!=bkey[i])
{
if(ick==-1) ick=i; // 처음으로 다른 곳을 만나면 위치 정보를 기억
else { ick=-2; break; } // 두 번째 다른 곳을 만나면
}
}
if(ick==-1) slist->ck=3; // 같으면 리스트에서 제거 && blist!=slist
else if(ick >=0) // 다른 곳이 하나이면
{
blist->ck=slist->ck=true; // 돈 퀘어처리 되었음
ltemp = MakeNode();
strcpy(ltemp->buf, blist->buf);
if(ick>=0) ltemp->buf[ick]='_';
if(*top)
{
ltemp->next=null;
(*top)->next=ltemp; *top=ltemp;
}
else *tlist=*top=ltemp;
}
if(slist==null) break;
slist=slist->next;
}
DelChar(tbuf);
}
keylist *QMkey::CkKey(keylist *slist)
{
keylist *tlist, *temp, *flist=null, *top=null, *ltop;
do
{
ltop = tlist = null;
while(slist)
{
if(slist->ck!=3) SamplifyKey(slist, &tlist, <op); // 리스트에 같은 항목이 실햏하지 안았으면
if(slist->ck!=false) // 돈 퀘어 처리나 같은 항목이 있으면
{
temp=slist;
slist=slist->next;
DelNode(temp);
}
else // 인접한 항목이 없으면
{
if(flist!=null) { top=top->next=slist; }
else top=flist=slist;
slist=slist->next;
}
}
slist=tlist;
}while(tlist);
top->next=null;
return flist;
}
bool QMkey::DelList(keylist *blist) // 리스트 삭제
{
keylist *temp;
while(blist)
{
temp=blist->next;
DelNode(blist);
blist=temp;
}
return true;
}
bool QMkey::DelNode(keylist *temp) // 노드 삭제
{
delete []temp->buf;
delete temp;
return true;
}
keylist* QMkey::MakeNode( ) // 노드 생성
{
int k=skeyvalue.ikeycount;
keylist *temp = new keylist;
temp->ck=false;
temp->next=null;
temp->buf= new char [k+1];
temp->buf[k]='\0';
return temp;
}
char *QMkey::MakeChar(int i)
{
char *buf=new char[i+1];
return buf;
}
void QMkey::DelChar(char* buf)
{
delete []buf;
}
main.exe