重言式.cpp

用二叉树实现逻辑表达式的基本运算,包括逻辑与,或,非,还可以判别表达式是重言式,还是矛盾式.

#include <stdio.h>
#include <ctype.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_NUM_VARIABLE 20
#define MAX_ALPHA 10
struct node1{
  char *base;
  char *top;
};
typedef struct node1 Stack;
struct node2{
  char data;
  struct node2 *lchild,*rchild;
};
typedef struct node2 Bitree;
char var[MAX_NUM_VARIABLE];  //存储读入的变量
int zuhe[MAX_NUM_VARIABLE];  //用于在存储变量的真值组合。
char *expr;//为由中缀表达式转化为前缀表达式时存放所有表达式中出现的字符变量 的数组的首地址 
int i,k=0;
int readch(char s[])  //读入表达式的字符串
{
  int j;
  char c;
  while((c=getchar())==' '||c=='\t');
  for(j=0;c!='\n';)
  {
    s[j++]=c;
    c=getchar();
  }
  s[j]='\0';
  return j-1;
}
Stack *Initstack()  //初始化栈，存放操作符。以把中缀转化为前缀表达式
{
  Stack *p;
  p=(Stack *)malloc(sizeof(Stack));
  p->base=(char *)malloc(50*sizeof(char));
  p->top=p->base;
  return p;
}
void push(Stack *p,char c)  //将操作符入栈
{
  *(p->top)=c;
  (p->top)++;
}
char pop(Stack *p)  //将操作符出栈
{
  char c;
  if(p->top==p->base)
    printf("error:stack empty.\n");
  else
  {
    c=*(--(p->top));
    return c;
  }
}
char gettop(Stack *p)  //查看出栈顶字符
{
  char e;
  if(p->top==p->base)
  {
    return '#';
  }
  e=*(p->top-1);
  return e;
}
int cmp(char a,char s[])  //对比读入的变量和在var[]中的变量，如读入的变量已在var[]中，则返回该变量在var[]中的位置，否则返回-1
{
  int j;
  for(j=0;s[j]!='\0'&&s[j]!=a;j++);
  if(s[j]!=a)
    return -1;
  else
    return j;
}
char *midtofro(char s[],int m,Stack *a)  //把中缀转化为前缀表达式
{
  int n=0,j=0,g;
  var[0]='\0';
  char *ch;
  ch=(char *)malloc(50*sizeof(char));
  for(g=0;s[g]!='\0';g++)
  {
    if(s[g]=='('||s[g]==')')  //计算存放前缀表达式的数组的大小g
      ;
    else
      j++;
  }
  j--;
  ch[j+1]='\0';
  for(;m>=0;)
  {
    if(s[m]==')')              //遇‘）’入栈
    {
      push(a,')');
      m--;
    }
    else if(isalpha(s[m]))  //变量则写入数组s[]，并依比较结果写入var[]中
    {
      ch[j--]=s[m];
      if(cmp(s[m],var)==-1)
      {
	var[n++]=s[m--];
	var[n]='\0';
      }
      else
	m--;
    }
    else if(s[m]=='|')  //遇运算符，弹出栈顶与该运算符同优先级或比它优先级高的元素。
    {
      while(gettop(a)=='&'||gettop(a)=='~'||gettop(a)=='|')
      {
		 ch[j--]=pop(a);
      }
      push(a,'|');
      m--;
    }
    else if(s[m]=='&')
    {
      while (gettop(a)=='&'||gettop(a)=='~')
	ch[j--]=pop(a);
      push(a,'&');
      m--;
    }
    else if(s[m]=='~')
    {
      while(gettop(a)=='~')
	ch[j--]=pop(a);
      push(a,'~');
      m--;
    }
    else if(s[m]=='(')
    {
      while(gettop(a)!=')')
	ch[j--]=pop(a);
      if(gettop(a)==')')
	pop(a);
      m--;
    }
  }
  if(m<0)
  {
    while(a->top!=a->base)
    {
      ch[j--]=pop(a);
    }
  }
  return ch;
}
Bitree *creatbitree(Bitree *a)  //用所得的前缀表达式先序创建二叉树
{
  int t;
  a=(Bitree *)malloc(sizeof(Bitree));
  if(expr[i]=='~')
  {
    a->data=expr[i++];
    a->lchild=creatbitree(a->lchild);
    a->rchild=NULL;
  }
  else if(isalpha(expr[i]))
  {
    t=cmp(expr[i],var);
    a->data=zuhe[t];
    a->lchild=NULL;
    a->rchild=NULL;
    i++;
  }
  else
  {
    a->data=expr[i++];
    a->lchild=creatbitree(a->lchild);
    a->rchild=creatbitree(a->rchild);
  }
  return a;
}
void creatzuhe(int n)  //创建组合01序列以对表达式变量赋值,进行穷举
{
  int t=0,j,l=0;
  int num=0;
  int e;
  int temp[20];
  while(var[t]!='\0')
    t++;
  for(j=0;j<t;j++)
    zuhe[j]=0;
  for(;n!=0;n/=2)
  {
    num++;
    temp[l++]=n%2;   
  }
  l-=1;
  num=t-num;
  while(l>=0)
  {
    e=temp[l--];
    zuhe[num++]=e;
  }
}
int value(int c,int a,int b)  
{
  switch(c)
  {
    case '|':
      return a||b;
    case '&':
      return a&&b;
    default:
      break;
  }
}
int preorderval(Bitree *p)  //先序遍历二叉树,以求值.
{
  if(p->rchild!=NULL&&p->lchild!=NULL&&(p->lchild->data==0||p->lchild->data==1)&&(p->rchild->data==0||p->rchild->data==1))
    return value(p->data,p->lchild->data,p->rchild->data);//求|或& 
  else if((p->lchild->data==0||p->lchild->data==1)&&(p->rchild==NULL)&&p->lchild!=NULL)
    return !(p->lchild->data);      //求~ 
  else if((p->lchild->data==0||p->lchild->data==1)&&p->rchild!=NULL&&p->lchild!=NULL)
    return value(p->data,p->lchild->data,preorderval(p->rchild));
  else if((p->rchild->data==0||p->rchild->data==1)&&p->lchild!=NULL&&p->rchild!=NULL)
    return value(p->data,preorderval(p->lchild),p->rchild->data);
  else if(p->rchild==NULL&&p->lchild==NULL)
	return p->data;
  else
    return value(p->data,preorderval(p->lchild),preorderval(p->rchild));
}
void mainbody()
{
  int num1,num2,num3;
  int w,nvar=1,total,j;
  int result[100];
  Stack *st;
  char s[50];
  char def[2];
  Bitree *T;
  st=Initstack();
  printf("请输入逻辑表达式:");
  num1=readch(s);
  expr=midtofro(s,num1,st);
  for(w=0;var[w]!='\0';w++);
  for(j=0;j<w;j++)
  nvar*=2;//求得变量的组合数 
  printf("下面为程序的几项功能:\n");
  printf("\n1.判断表达式是重言式或矛盾式或一般表达式.\n");
  printf("2.赋值给变量以求表达式的值.\n");
  printf("3.打印变量序列及其真值表.\n\n");
  printf("请输入你的指令:");
  scanf("%s",def);
  if(def[0]=='1')  //判断是否为重言式
  {
    for(w=0;w<nvar;w++)
    {
      creatzuhe(w);
      i=0;
      T=creatbitree(T);
      result[w]=preorderval(T);
    }
    total=w-1;
    for(w=0;w<total&&result[w]==result[w+1];w++);
    if(w==total)
    {
      if(result[0]==1)
	printf("Ture forever.\n");
      else
	printf("False forever.\n");
    }
    else
      printf("Satisfactible.\n");
  }
  else if(def[0]=='2')  //给变量赋值 
  {
    
      printf("请输入每个变量的值:\n");
      for(num2=w-1;num2>=0;num2--)
      {
	printf("%c=",var[num2]);
	scanf("%d",&zuhe[num2]);
      }
      i=0;
      T=creatbitree(T);
      printf("逻辑表达式的运算结果为:");
      printf("%d\n",preorderval(T));
    
  }
  else if(def[0]=='3')  //进行计算,并打印真值表
  {
    for(num3=w-1;num3>=0;num3--)
	  printf("%c\t",var[num3]);
    printf("表达式结果\n");
    total=w;
    for(w=0;w<nvar;w++)
    {
      creatzuhe(w);
      i=0;
      T=creatbitree(T);
      result[w]=preorderval(T);
      for(num3=0;num3<total;num3++)
		  printf("%d\t",zuhe[num3]);
	  printf("    %d\n",result[w]);
    }
  }
  
  
}


void main(){
    
    char c;
    
    do{
       mainbody();
       c=getchar();
       printf("是否继续/?(Y/N)");
       scanf("%c",&c);
      }while((c=='Y'||c=='y')&& (c=getchar()) );
      
}