zysbb.cpp

数据结构之重言式辨别 数据结构之重言式辨别数据结构之重言式辨别

 #include<string.h>
 #include<ctype.h>
 #include<malloc.h> // malloc()等
 #include<limits.h> // INT_MAX等
 #include<stdio.h> // EOF(=^Z或F6),NULL
 #include<stdlib.h> // atoi()
 #include<io.h> // eof()
 #include<math.h> // floor(),ceil(),abs()
 #include<process.h> // exit()
 #include<iostream.h> // cout,cin
 // 函数结果状态代码
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
 typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE

#define VARIES_MAX 20
#define STRING_MAX 60
#define STACK_INIT_SIZE 100
int Comb[VARIES_MAX];//变量的取值组合数组定义;
int N;//变量个数;


typedef struct BitNode{  //二叉树的结点定义;
 char data;
 struct BitNode *lchild; 
 struct BitNode  *rchild;
}*BiTree;

typedef struct {      //堆栈定义,它存放的都是树的结构;
 struct BitNode **base;    
 struct BitNode **top;
 int stacksize;
}SqStack;


void CreatComb(int n)           //产生变量的各种取值组合;
{
 int i,num=0,j=0,e;
 int temp[VARIES_MAX];
    for(i=0;i<N;i++)
  Comb[i]=0;
 while(n)
 {
  e=n%2;
  num++;
  temp[j++]=e;
  n=n/2;
 }
 j=j-1;
    num=N-num;
 while(j>=0)
 {
     e=temp[j--];
 Comb[num++]=e;
 }
}


//以下为对操作符栈和变量堆栈的操作；
void InitSqStack(SqStack &st)
{
 st.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BitNode));
 if(!st.base) exit(0);
 st.top=st.base;
 st.stacksize=STACK_INIT_SIZE;
}

void Push(SqStack &st,BiTree e)
{
 if(st.top-st.base<st.stacksize)
 *st.top++=e;
 else exit(0);
}

void Pop(SqStack &st,BiTree &e)
{
 if(st.top==st.base) exit(0);
 e=*--st.top;
}

void Gettop(SqStack &st,BiTree &e)
{
 if(st.top==st.base) exit(0);
 e=*(st.top-1);
}


int k=0;//建树的标志，k＝1表示第一次建立分子树，要对左右孩子的指针域处理
void CreateSub_tree(BiTree &sub_root,BiTree l,BiTree r)  //自底向上的运算符优先级法建立分子树
{
 sub_root->lchild=l;
 sub_root->rchild=r;//分树的链接
 if(l&&r)
 {
     if(int(l->data)>=65&&int(l->data)<=90)
  {
  l->lchild=NULL;
  l->rchild=NULL;
  }
   if(int(r->data)>=65&&int(r->data)<=90)
   {
     r->lchild=NULL;
     r->rchild=NULL;
   }
 }
}
 

char Precede(char col,char row)//逻辑运算符的优先级判别函数；
{
 int    i,j;
 char compare[7][7]={' ','|','&','~','(',')','#',
                     '|','>','<','<','<','>','>',
                     '&','>','>','<','<','>','>',                                                                                                                                                                                                                                                                                                                                                                                                                                                         
                     '~','>','>','>','<','>','>',
                     '(','<','<','<','<','=',' ',
                     ')','>','>','>',' ','>','>',
                     '#','<','<','<','<',' ','='};
for(i=0;i<7;i++)
   if(compare[0][i]==col)
    break;
for(j=0;j<7;j++)
   if(compare[j][0]==row)
    break;
   return compare[j][i];
}


void CreateBiTree(char s[],BiTree &tree)     //重言式的识别函数；
{
 
   SqStack  OPND;       //变量栈;
   SqStack  OPTR;         //逻辑运算符栈; 
   InitSqStack(OPND);
   InitSqStack(OPTR);
 BiTree logic,variables,logic1,e,a,b,theta,Brackets;   //定义栈中的元素,都为树结构;
                  //theta为最后的二叉树的根;
 logic=(BiTree)malloc(sizeof(BitNode));
 if(!logic)  exit(0);
 logic->data='#';
 Push(OPTR,logic);
   while(*s!=NULL)
 {     
  if(int(*s)>=65&&int(*s)<=90)
  {  
      variables=(BiTree)malloc(sizeof(BitNode));
   if(!variables)  exit(0);
   variables->data=*s;
   Push(OPND,variables);
    }
    else if(int(*s)>90||int(*s)<65)
    {  
      Gettop(OPTR,e);//取运算符栈的栈顶元素进行优先级比较
     switch(Precede(*s,e->data))
   {
   case '<': //栈顶的运算符优先级低,逻辑运算符进栈
          logic1=(BiTree)malloc(sizeof(BitNode));
             if(!logic1)  exit(0);
             logic1->data=*s;
             Push(OPTR,logic1);
          break;
            case '='://脱括号并接受下一个字符;
         Pop(OPTR,Brackets);break;
      
   case '>':Pop(OPTR,theta);//弹出逻辑运算符
         Pop(OPND,a);//弹出变量
      b=NULL;
      if(theta->data!='~')
          Pop(OPND,b);
      //建树的函数调用
      k=k+1;
      CreateSub_tree(theta,b,a);
      
                     Push(OPND,theta);//将临时的根作为新的变量压入变量栈中;
         if(*s!='#'&&*s!=')') 
      {
      logic1=(BiTree)malloc(sizeof(BitNode));
               if(!logic1)  exit(0);
               logic1->data=*s;
               Push(OPTR,logic1);
      }
      else  s=s-1;
      break;
   }
    }
   s++;
 }
 tree=theta;
}
 
int Value_tree(BiTree tree)  //根据变量的取值组合并利用逻辑表达式的性质对树进行求值
{
    if(!tree) return 0;                                       //遇到空的结点;
 else if(tree->data!='|'&&tree->data!='&'&&tree->data!='~')//找到的是变量；
     return  Comb[int(tree->data)-65];
    else if(int(tree->data)<65||int(tree->data)>90)           //找到的是运算符;
      switch(tree->data)
   {
   case '|': return(Value_tree(tree->lchild)||Value_tree(tree->rchild));
   case '&': return(Value_tree(tree->lchild)&&Value_tree(tree->rchild));
   case '~': return(!Value_tree(tree->rchild));
   }
    return 1;
}

void User_In()  //用户设定变量的一种取值；
{
 int i;
 
 cout<<"请依次输入你的变元取值"<<endl;
 for(i=65;i<65+N;i++)
 {
 cout<<char(i)<<" = ";
 cin>>Comb[i-65];
 }
}

void Re_value(BiTree tree,char string[],int a,int b)//根据变量组合的总数a以及每种组合的值的累加值b,输出真值表
{
       cout<<"-------------------------------------------"<<endl;
       for(int l=65;l<65+N;l++)
       printf("%-4c",l);
       cout<<"      "<<string<<endl;
       
       cout<<"*******************************************"<<endl;
       for(int i=0;i<a;i++)
       {
          CreatComb(i);//产生变量取值组合;
          b+=Value_tree(tree);

          for(int j=0;j<N;j++)
             printf("%-4d",Comb[j]);
          cout<<"        "<<Value_tree(tree);
          cout<<endl<<"-------------------------------------------"<<endl;
       }//for
}


void main()
{
  char *pstr,string1[STRING_MAX],string2[STRING_MAX];
  char choice1,choice2;
  int loop=10,i=0,sum;
  BiTree Tree;
  
  cout<<endl<<endl<<endl<<endl;
  cout<<"                    ***********数据结构·课程设计**********"<<endl<<endl<<endl;
  cout<<"                       题目：重言式辨别                    "<<endl<<endl;
  cout<<"                       班级：06级计算机科学与技术03班      "<<endl<<endl;
  cout<<"                       姓名：刘源                          "<<endl<<endl;
  cout<<"                       学号：3106006516                    "<<endl<<endl<<endl;
  cout<<"                    ***********数据结构·课程设计**********"<<endl<<endl<<endl;
  system("pause");
  system("cls");


  while(loop)
  {
  pstr=string1;
  i=0;
  int  SUM=0;  //用于累加变量的每种组合的逻辑表达式的结果，可以作为逻辑表达式类别判别的根据
  cout<<endl<<"请输入逻辑表达式的变量的个数:";
  cin>>N;
  sum=int(pow(2,N)); //变量组合的总数;
  cout<<endl<<"请输入逻辑表达式的表达式(变量用大写字母,或用'|',与用'&'和非用'~')："<<endl;
  cin>>string1;
  //吃掉空格符
  for(;*pstr!=NULL;pstr++)
     if(*pstr!=' ') string2[i++]=*pstr;
  string2[i]='#';
  string2[i+1]='\0';
  
   CreateBiTree(string2,Tree);//建立重言式的二叉树;
  
   for(loop=0;loop<sum;loop++)
   {
       
      CreatComb(loop);//产生变量取值组合;
      SUM+=Value_tree(Tree);
  }
  string2[i]='\0';
  if(SUM==0) cout<<"逻辑表达式"<<string2<<"  是矛盾式"<<endl<<endl;
     if(SUM==sum) cout<<"逻辑表达式"<<string2<<"  是重言式"<<endl<<endl;
     if (SUM>0&&SUM<sum)
     {cout<<"逻辑表达式"<<string2<<"  既不是重言式,也不是矛盾式"<<endl<<endl;
      cout<<"             *  人机交互输入(E/e)     显示真值表(Z/z)  *"<<endl;
      cout<<"请选择操作:";
      cin>>choice1;
      if(choice1=='E'||choice1=='e')
	  {   User_In();
          cout<<endl<<"逻辑表达式"<<string2<<"=" <<Value_tree(Tree)<<endl;
      }
       else if(choice1=='Z'||choice1=='z')
       Re_value(Tree,string2,sum,SUM);//else if
     }//if
  
  cout<<endl<<"继续运算？是按Y/ 否按N:";
  cin>>choice2;
  if(choice2=='N'||choice2=='n')
    exit(0);
  loop--;
 
  }
}