5.cpp

二叉树实现逻辑表达式真值判断

#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<math.h>
#define stack_size 100
int zuhe[20];//变量的取值组合数组定义;
int N;//变量个数;
int k=0;
//根据表达式建立的二叉树的结点定义;
typedef struct tree{
 char data;
 struct tree *lch;    //结点的左孩子；
 struct tree  *rch;  //结点的右孩子.
}*BNode;
//识别表达式使用的堆栈定义,它存放的都是树的结构;
typedef struct stack{
 struct tree **base;    //栈中的元素都是树的结点结构；
 struct tree **top;
 int stacksize;
}sqstack;
//用于产生变量的各种取值组合;
void creatzuhe(int n)
{
  int i;
 for(i=N-1;i>=0;i--)
 {zuhe[i]=n%2;
 n=n/2; }
}
//自底向上地根据运算符地优先级来建立分子树函数;当逻辑表达式读完后-子根zigen就是一棵完整的二叉树
void create(BNode &zigen,BNode l,BNode r)
{
    zigen->lch=l;
 zigen->rch=r;
 if(l&&r)
 {
     if(int(l->data)>=65&&int(l->data)<=90)
  {
  l->lch=NULL;
  l->rch=NULL;
  }
   if(int(r->data)>=65&&int(r->data)<=90)
   {
     r->lch=NULL;
     r->rch=NULL;
   }
 }
}
//逻辑运算符的优先级判别；
char paixu(char row,char col)
{
 int    i,j;
 char compare[7][7]={' ','|','&','~','(',')','#',
                 '|','>','<','<','<','>','>',
                 '&','>','>','<','<','>','>',
                 '~','>','>','>','<','>','>',
                 '(','<','<','<','<','=',' ',
                 ')','>','>','>',' ','>','>',
                 '#','<','<','<','<',' ','='};
for(i=0;i<7;i++)
   if(compare[0][i]==row)
    break;
for(j=0;j<7;j++)
   if(compare[j][0]==col)
    break;
   return compare[j][i];
}
void creatstack(sqstack &S)
{
S.base=(BNode*)malloc(stack_size*sizeof(tree));
 if(!S.base)
 exit(0);
 S.top=S.base;
 S.stacksize=stack_size;
}
void push(sqstack &S,BNode e)
{
 if(S.top-S.base<S.stacksize)
 *S.top++=e;
 else exit(0);
}
void pop(sqstack &S,BNode &e)
{
 if(S.top==S.base)
 exit(0);
 e=*--S.top;
}
void gettop(sqstack &S,BNode &e)
{
 if(S.top==S.base)
 exit(0);
 e=*(S.top-1);
}

//重言式识别
void creattree(char s[],BNode &tree)
{
sqstack  variable;       //变量栈;
    sqstack  logic;         //逻辑运算符栈;
    creatstack(variable);
 creatstack(logic);
 BNode logic_di,variables,logics,e,a,b,theta,parentheses;   //定义栈中的元素;
 logic_di=(BNode)malloc(sizeof(tree));
 if(!logic_di)  exit(0);
 logic_di->data='#';
 push(logic,logic_di);
   while(*s!=NULL)
 {
  if(int(*s)>=65&&int(*s)<=90)
  {
      variables=(BNode)malloc(sizeof(tree));
   if(!variables)  exit(0);
   variables->data=*s;
   push(variable,variables);
    }
    else if(int(*s)>90||int(*s)<65)
    {
      gettop(logic,e);//优先级比较
     switch(paixu(*s,e->data))
   {
   case '<':
          logics=(BNode)malloc(sizeof(tree));
             if(!logics)  exit(0);
             logics->data=*s;
             push(logic,logics);
          break;

            case '=':
         pop(logic,parentheses);break;

   case '>':pop(logic,theta);
         pop(variable,a);
      b=NULL;
      if(theta->data!='~')
          pop(variable,b);
      k=k+1;
      create(theta,b,a);

                     push(variable,theta);
         if(*s!='#'&&*s!=')')
      {
      logics=(BNode)malloc(sizeof(tree));
               if(!logics)  exit(0);
               logics->data=*s;
               push(logic,logics);
      }
      else  s=s-1;
      break;
   }
    }
   s++;
 }
 tree=theta;
}
int value_tree(BNode tree)
{
    if(!tree) return 0;                                       //空结点;
 else if(tree->data!='|'&&tree->data!='&'&&tree->data!='~')//变量；
     return  zuhe[int(tree->data)-65];
    else if(int(tree->data)<65||int(tree->data)>90)           //运算符;
      switch(tree->data)
   {
   case '|': return(value_tree(tree->lch)||value_tree(tree->rch));
   case '&': return(value_tree(tree->lch)&&value_tree(tree->rch));
   case '~': return(!value_tree(tree->rch));
   }
}
void main()
{
  char str[60],string[60],*pstr;
  int loop=20,i=0,sum;
  BNode Tree;
  while(loop)
  {
  pstr=str;
  i=0;
  int  SUM=0,l;
  cout<<"Please input the number of variables"<<endl;
  cin>>N;
  if(N<=1||N>20)
  {
    cout<<"Input error"<<endl;
    break;
  }
  else{
  sum=int(pow(2,N));
  cout<<"Please input the logic expression(use'|',or '&' or '~')"<<endl;
  cin>>str;
  for(;*pstr!=NULL;pstr++)
     if(*pstr!=' ') string[i++]=*pstr;
  string[i]='#';
  string[i+1]='\0';
 creattree(string,Tree);//建立重言式二叉树;
        cout<<"         Result        "<<endl;
  printf("|       ");
  for(l=65;l<65+N;l++)
       printf("%-4c",l);
  printf("   expression");
  printf("         |\n");
   for(loop=0;loop<sum;loop++)
   {
    creatzuhe(loop);//产生变量取值组合;
   SUM+=value_tree(Tree);
        printf("|       ");
   for(int h=0;h<N;h++)
    printf("%-4d",zuhe[h]);
   printf("%8d",value_tree(Tree));
            printf("              |\n");
  }
  string[i]='\0';
  if(SUM==0) cout<<"logic expression: "<<string<<"  is contradiction"<<endl;//矛盾式
  else if(SUM==sum)
  cout<<"logic expression: "<<string<<"  is  tautology"<<endl;//重言式
  else
  cout<<"logic expression: "<<string<<"  is neither tautology，nor contradiction"<<endl;
  break;
}
  }
}