DDD.rar_数据结构 重言式_重言式

#include"StackTree.h" #define MAX 100 char aOPND[6]={'|','&','~','(',')','#'};//运算符 int flag[MAX];//组合数的值 char letter[MAX];//变量的字符 int In(char a){//查看运算符的位置 int i; for(i=0;i<5;i++) if(a==aOPND[i]) break; else continue; if(i==5) return 0; else return i+1; } char Priority[6][6]={//运算符的优先级 {'>','<','<','<','>','>'}, {'>','>','<','<','>','>'}, {'>','>','>','<','>','>'}, {'<','<','<','<','=',' '}, {'>','>','>',' ','>','>'}, {'<','<','<','<',' ','='} }; char Precede(char letter1,char letter2){//获取运算符的优先级 return Priority[In(letter1)-1][In(letter2)-1]; } void FindLetter(char *s,int &n){//该函数用于找出输入串中的字母数，并将它们存储在letter[]中 int i; char *p; p=s; n=0; while(*p!='\0'){ if(!In(*p)) if(n==0) { letter[0]=*p; n++; }//if 填第一个字母 else { for(i=0;i<n;i++) if(letter[i]==*p) break;//是否已经有了该字母 if(i==n){ letter[n]=*p; n++; } }//else //if(!In(*p) p++; }//while } void CreateTree(char s[],BiTree &T){ SqStack OPTR;//运算符栈 SqStack OPND;//运算数栈 BiTree variable,logic,theta,firstin,e,a,b,bracket; InitStack(OPTR); InitStack(OPND); firstin=(BiTree)malloc(sizeof(BtNode)); if(!firstin){ printf("Tree malloc error in func CreateTree\n"); exit(1); } firstin->data='#';//推入标志符 Push(OPTR,firstin); while(*s!=NULL){ if(*s>='A'&&*s<='Z'){//若该符号为变量的情况 variable=(BiTree)malloc(sizeof(BtNode)); variable->data=*s; Push(OPND,variable); } else if(*s<'A'||*s>'Z'){//该符号为运算符 GetTop(OPTR,e); switch(Precede(*s,e->data)){ case '<'://运算符优先级低进栈 logic=(BiTree)malloc(sizeof(BtNode)); logic->data=*s; Push(OPTR,logic); break; case '='://为括号的情况 Pop(OPTR,bracket);break; case '>':Pop(OPTR,theta); Pop(OPND,a); b=NULL; if(theta->data!='~') Pop(OPND,b); Create(theta,b,a); Push(OPND,theta); if(*s!='#'&&*s!=')'){ logic=(BiTree)malloc(sizeof(BtNode)); logic->data=*s; Push(OPTR,logic); } else s=s-1; break; } } s++; } T=theta; } int GetValue(char a){ int i; for(i=0;i<MAX;i++) if(a==letter[i]) return flag[i];//返回一个组合值 else continue; printf("error in GetValue\n"); exit(1); } int ValueTree(BiTree T){ if(!T) return 0; else if(T->data!='&'&&T->data!='|'&&T->data!='~')//非运算符则返回变量在组合函数中的值 return GetValue(T->data); else if(T->data<'A'||T->data>'Z'){ switch(T->data){ case '|':return ValueTree(T->lchild)||ValueTree(T->rchild);break; case '&':return ValueTree(T->lchild)&&ValueTree(T->rchild);break; case '~':return (!ValueTree(T->lchild));break;//标记一下，该处可能为T->rchild } } } void CreateCombine(int n){//软计数器实现，flag 1代表有该数，0代表无该数 long i,j,tmp,m=1; for(i=1;i<=n;i++) m=m*2; for(i=1;i<=m;i++){ tmp=i; for(j=1;j<=n;j++){ flag[j]=tmp%2; tmp=tmp/2; } } } void Info(){ printf("输入一个表达式\n"); printf("如果恒为真则输出True forever,恒为假输出False forever,否则输出Satisfactible\n"); } int main(){ int n,j,valueflag=-1;//n代表不同的变量数,valueflag用于判断重言式是哪一种类型 BiTree T; char str[MAX];//str用于获取输入串 Info(); gets(str); FindLetter(str,n);//将str中的不同的变量数存于数组letter中，并且算出变量个数n CreateTree(str,T); for(j=0;j<n;j++){ CreateCombine(j);//产生组合数 if(ValueTree(T)==0&&(valueflag==-1||valueflag==0)) valueflag=0;//valueflag=0代表重言式值为假 if(ValueTree(T)==1&&(valueflag==-1||valueflag==1)) valueflag=1;//valueflag=0代表重言式值为真 else break; } if(j<n) printf("Satisfactible\n"); else if(j==n&&valueflag==0) printf("False forever\n"); else if(j==n&&valueflag==1) printf("True forever\n"); else printf("Unkown value need to test\n"); return 0; }