cys.rar_重言式判定

#include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> char var[20]; char *expr; int zuhe[20],i; struct stack{ char *base; char *top; }; typedef struct bitree{ char data; struct bitree *lchild,*rchild; }*bitreeptr; void initstack(stack &s) { s.base=(char *)malloc(50*sizeof(char)); s.top=s.base; } void gettop(stack s,char &e) { if(s.top==s.base); e=*(s.top-1); } void push(stack &s,char e) { *s.top++=e; } void pop(stack &s,char &e) { if(s.top==s.base); e=*--s.top; } int readch(char s[])//读入表达式的字符串 { int j; char c; c=getchar(); for(j=0;c!='\n';j++) { s[j]=c; c=getchar(); } s[j]='\0'; return j-1; } int compare(char a,char s[]) { int j=0; while(s[j]!='\0'&&a!=s[j]) j++; if(a!=s[j]) return 0; else return j; } char *mid_to_fro(char s[],int m,stack &a)//把中缀转化为前缀表达式 { int g=0,n=0,j=0; char *ch,e; ch=(char *)malloc(50*sizeof(char)); var[0]='\0'; while(s[g]!='\0') { if(s[g]!='('&&s[g]!=')') j++; g++; } ch[j]='\0'; j--; while(m>=0) { if(s[m]==')') push(a,')'); else if(s[m]=='|') { gettop(a,e); while(e=='&'||e=='~'||e=='|') { pop(a,ch[j--]); gettop(a,e); } push(a,'|'); } else if(s[m]=='&') { gettop(a,e); while(e=='&'||e=='~') { pop(a,ch[j--]); gettop(a,e); } push(a,'&'); } else if(s[m]=='~') { gettop(a,e); while(e=='~') { pop(a,ch[j--]); gettop(a,e); } push(a,'~'); } else if(s[m]=='(') { gettop(a,e); while(e!=')') { pop(a,ch[j--]); gettop(a,e); } pop(a,e); } else if((s[m]>64&&s[m]<91)||(s[m]<123&&s[m]>96)) { ch[j--]=s[m]; if(compare(s[m],var)==0) { var[n++]=s[m]; var[n]='\0'; } } m--; } while(a.top!=a.base) pop(a,ch[j--]); return ch; } bitreeptr creatbitree(bitreeptr T) //用所得的前缀表达式先序创建二叉树 { int t;//i=0; T=(bitree *)malloc(sizeof(bitree)); if(expr[i]=='~') { T->data=expr[i++]; creatbitree(T->lchild); T->rchild=NULL; } else if((expr[i]>64&&expr[i]<91)||(expr[i]<123&&expr[i]>96)) { t=compare(expr[i++],var); T->data=zuhe[t]; T->lchild=NULL; T->rchild=NULL; } else { T->data=expr[i++]; creatbitree(T->lchild); creatbitree(T->rchild); } return T; } void creatzuhe(int n) { int t,j,l=0,num=0,temp[20]; t=strlen(var); for(j=0;j<t;j++) zuhe[j]=0; for(;n!=0;n/=2) { num++; temp[l++]=n%2; } l--; num-=t; while(l>=0) zuhe[num++]=temp[l--]; } int value(char c,int a,int b) { switch(c) { case '|': return a||b; case '&': return a&&b; default: break; } } int preorderval(bitreeptr &T)//先序遍历二叉树,以求值. { if(T->rchild!=NULL&&T->lchild!=NULL) return value(T->data,preorderval(T->lchild),preorderval(T->rchild)); else if(T->rchild==NULL&&T->lchild!=NULL) return !(T->lchild->data); else if(T->rchild==NULL&&T->lchild==NULL) return T->data; } void main() { int num1,num2,w,nvar=1,j; int result[100]; char s[50],d[2]; stack st; bitreeptr T; initstack(st); printf("请输入逻辑表达式:"); num1=readch(s); expr=mid_to_fro(s,num1,st); w=strlen(var); for(j=0;j<w;j++) nvar*=2; printf("以下是程序的功能：\n“1”为判别表达式是否为重言式\n“2”为输入变量的值求结果\n"); printf("请输入你的指令:"); scanf("%s",d); if(d[0]=='1')//判断是否为重言式 { for(w=0;w<nvar;w++) { creatzuhe(w); i=0; T=creatbitree(T); result[w]=preorderval(T); } for(w=0;w<(nvar-1)&&result[w]==result[w+1];w++); if(w==nvar) { if(result[0]==1) printf("Ture forever.\n"); else printf("False forever.\n"); } else printf("Satisfactible.\n"); } }