用c语言做命题公式真值表（仅支持交，并，非三种运算符）

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<malloc.h> typedef struct Node //二叉树节点结构体 { char data; //存节点字符 struct Node *leftchild;//左孩子指针 struct Node *rightchild;//右孩子指针 int temp;//判断该节点前是否有特别的字符类型 }BeTreeNode; /*typedef struct { char stack[30]; int top; }SeqStack;//账的结构体*/ void print_char(BeTreeNode *root); void prints(BeTreeNode *p); char str[30]; //输入的字符串 char S[16]; //仅存是字母的字符串 int w,length,x=1; //分辨取哪一种真值赋值 //SeqStack mystack;//定义一个栈 BeTreeNode *pt[30];//定义指针数组 int **S_num; //二维数组存真值的多种赋值情况 int L=0; /*void StackInitiate(SeqStack *S) //初始化 { S->top=0; } int StackNotEmpty(SeqStack S) //非空否 { if(S.top<=0)return 0; else return 1; } int StackPush(SeqStack *S,char x)//入栈 { if(S->top>=16) { printf("堆栈已满无法插入!\n"); return 0; } else { S->stack[S->top]=x; S->top++; return 1; } } */ BeTreeNode *MakeTree(int a,int b) //建立二叉树 { int i,j=0,k=0,a1[10],b1[10]; int L=0; BeTreeNode *p[10]; BeTreeNode *pp,*sign=NULL; for(i=a;i<=b;i++)//若有括号的先渐入括号的最内层 { if(str[i]=='(') { //if(mystack.top==0) if(L==0) a1[j]=i; L++; } if(str[i]==')') { L--; if(L==0){b1[j]=i;p[j]=MakeTree(a1[j]+1,b1[j]-1);j++;} } } j=0; for(i=a;i<=b;i++,k++)//用指针来存储二叉树的每个节点 { if(str[i]=='!') { if(str[i+1]=='(') { pt[k]=p[j]; pt[k]->temp=2; i=b1[j]; j=j+1; } else {pt[k]=(BeTreeNode *)malloc(sizeof(BeTreeNode)); pt[k]->data=str[i+1]; pt[k]->leftchild=NULL; pt[k]->rightchild=NULL; pt[k]->temp=-1; i=i+1; } } else if(str[i]=='(') { pt[k]=p[j]; pt[k]->temp=1; i=b1[j]; j=j+1; } else { pt[k]=(BeTreeNode *)malloc(sizeof(BeTreeNode)); pt[k]->data=str[i]; pt[k]->leftchild=NULL; pt[k]->rightchild=NULL; pt[k]->temp=0; } } pp=pt[0]; for(i=1;i<k;i=i+2)//把各个二叉树的节点连接起来 { if(pt[i]->data=='|') {pt[i]->leftchild=pp; pt[i]->rightchild=pt[i+1]; pp=pt[i]; } else { if(sign!=NULL) {pt[i]->leftchild=sign; sign->rightchild=pp; pp=pt[i]; sign=NULL; } else {pt[i]->leftchild=pp; pp=pt[i]; } if(i+2<k) { if(pt[i+2]->data=='|') {pp=pt[i+1]; sign=pt[i]; } else { pp->rightchild=pt[i+1]; } } } } if(sign!=NULL) {sign->rightchild=pp;pp=sign;} else pp->rightchild=pt[k-1]; return pp; } void prints(BeTreeNode *p)//根据各个节点前的标记符的赋值确定应该要输出哪种字符 { if(p->temp==2) {printf("!("); print_char(p); printf(")"); } else if(p->temp==1) {printf("("); print_char(p); printf(")"); } else if(p->temp==-1) {printf("!"); print_char(p); } else print_char(p); } void print_char(BeTreeNode *root)//输出某个节点下的树 { if(root->leftchild==NULL&&root->rightchild==NULL) { printf("%c",root->data); } else { prints(root->leftchild); printf("%c",root->data); prints(root->rightchild); } } void print(BeTreeNode *root)//利用二重循环来进行从最内层的子树开始输出，直到输出整棵树 { if(root->leftchild->leftchild!=NULL) print(root->leftchild); if(root->rightchild->leftchild!=NULL) print(root->rightchild); if(root->leftchild->temp==-1) printf("!%c ",root->leftchild->data); if(root->rightchild->temp==-1) printf("!%c ",root->rightchild->data); print_char(root); if(root->temp==2) {printf(" ");prints(root);} printf(" "); } int numre(char c)//输出叶节点 { int i; for(i=0;i<length;i++) { if(S[i]==c)return S_num[w][i]; } } int Judge(int num1,char c,int num2)//判断最简单的表达式的返回值 { if(c=='&') { if(num1==num2&&num1==1)return 1; else return 0; } if(c=='|') { if(num1==num2&&num1==0)return 0; else return 1; } } int print_num(BeTreeNode *root)//从最内层开始输出返回值 { int num1,num2,num,i; char c; if(root->leftchild==NULL&&root->rightchild==NULL) { num=numre(root->data); } else { num1=print_num(root->leftchild); c=root->data; num2=print_num(root->rightchild); if((root->leftchild->temp==2)||(root->leftchild->temp==-1)) { for(i=0;i<x;i++) printf(" "); printf(" %d",num1); } if((root->rightchild->temp==2)||(root->rightchild->temp==-1)) { for(i=0;i<x;i++) printf(" "); printf(" %d",num2); } num=Judge(num1,c,num2); for(i=0;i<x;i++) printf(" "); printf(" %d",num); x=x+3; } if((root->temp==2)||(root->temp==-1)) { if(num==1)num=0; else num=1; } return num; } int fac(int t)//计算出2的n次方的结果 { if(t==0)return 1; if(t==1)return 2; return 2*fac(t-1); } void S_numf(int n)//开辟一个二维数组存储真值表的各种赋值情况 { int row,col,i,j,k,p; row=fac(n); col=n; S_num=(int *)malloc(sizeof(int)*row); for(i=0;i<row;i++) { S_num[i]=(int *)malloc(sizeof(int)*col); } for(i=0;i<row;i++) for(j=0;j<col;j++) S_num[i][j]=0; for(i=0;i<col;i++) for(k=0,j=fac(i);k<fac(i);j++,k++) {for(p=col-1;p>col-1-i;p--) S_num[j][p]=S_num[k][p]; S_num[j][p]=1; } } main() { int i,j,LEN,t=0,temp=1; BeTreeNode *root;//定义根节点 //StackInitiate(&mystack); printf("请输入一个符合命题公式(仅支持 非'!',析取'|',合取'&',优先级：!,|,&)\n："); gets(str); LEN=strlen(str); for(i=0;i<LEN;i++) { for(j=0;j<t;j++) if(S[j]==str[i])temp=0; if((str[i]>='a'&&str[i]<='z'||str[i]>='A'&&str[i]<='Z')&&temp){S[j]=str[i];t++;} temp=1; } length=strlen(S); S_numf(length); root=MakeTree(0,LEN-1); printf("该复合命题公式的真值表是：\n"); for(i=0;i<length;i++) printf("%c ",S[i]); print(root); printf("\n"); for(w=0;w<fac(length);w++) { for(i=0;i<length;i++) printf("%d ",S_num[w][i]); print_num(root); printf("\n"); x=1; } }