重言式判别.cpp

1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入）

#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
#define stack_size_normal 100
#define variable_max 20
#define str_max 60
int weave[variable_max];//变量的取值组合数组定义
int N;//变量个数
//根据表达式建立的二叉树的结点定义
typedef struct btnode{
 char data;
 struct btnode *lchild; 
 struct btnode *rchild;
}*bitree;
//识别表达式使用的堆栈定义,它存放的都是树的结构
typedef struct lnode_optr{      
 struct btnode **base;    //栈中的元素都是树的结点结构
 struct btnode **top;
 int stacksize;
}sqstack;
//用于产生变量的各种取值组合
void creatweave(int n)
{ int i,num=0,j=0,e;
 int temp[variable_max];
    for(i=0;i<N;i++)
  weave[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--];
  weave[num++]=e;
 }
}
//自底向上地根据运算符地优先级来建立分子树函数;当逻辑表达式读完后-子根zigen就是
//一棵完整的二叉树
int k=0;//建树的标志，k＝1表示第一次建立分子树，要对左右孩子的指针域处理
void create(bitree &zigen,bitree l,bitree r)
{zigen->lchild=l;
 zigen->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  PRI (char list,char row)
{ int    i,j;
 char compare[7][7]={' ','|','&','~','(',')','#', '|','>','<','<','<','>','>', '&','>','>','<','<','>','>',                                                                                                                                                                                                                                                                                                                                                                                                                                                         
  '~','>','>','>','<','>','>', '(','<','<','<','<','=',' ', ')','>','>','>',' ','>','>', '#','<','<','<','<',' ','='};
for(i=0;i<7;i++)
   if(compare[0][i]==list)
    break;
for(j=0;j<7;j++)
   if(compare[j][0]==row)
    break;
   return compare[j][i];
}
//对操作符栈和变量堆栈的操作
void creatstack(sqstack &st)
{ st.base=(bitree*)malloc(stack_size_normal*sizeof(btnode));
 if(!st.base) exit(0);
 st.top=st.base;
 st.stacksize=stack_size_normal;
}
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);
}
//重言式的识别函数
void creattree(char s[],bitree &tree)
{sqstack  variable;       //变量栈
    sqstack  logic;       //逻辑运算符栈
    creatstack(variable);
 creatstack(logic);
 bitree logic_di,variables,logics,e,a,b,theta,kuohao;   
//定义栈中的元素，theta为最后的二叉树的根
 logic_di=(bitree)malloc(sizeof(btnode));
 if(!logic_di)  exit(0);
 logic_di->data='#';
 push(logic,logic_di);
   while(*s!=NULL)
 {   if(int(*s)>=65&&int(*s)<=90)
  {   variables=(bitree)malloc(sizeof(btnode));
   if(!variables)  exit(0);
   variables->data=*s;
   push(variable,variables);
    }
    else if(int(*s)>90||int(*s)<65)
    { gettop(logic,e);//取运算符栈的栈顶元素进行优先级比较
     switch( PRI (*s,e->data))
   {
   case '<': //栈顶的运算符优先级低,逻辑运算符进栈
          logics=(bitree)malloc(sizeof(btnode));
             if(!logics)  exit(0);
             logics->data=*s;
             push(logic,logics);
          break;
case '='://脱括号并接受下一个字符
         pop(logic,kuohao);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=(bitree)malloc(sizeof(btnode));
               if(!logics)  exit(0);
               logics->data=*s;
               push(logic,logics);
      }
      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  weave[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));
   }
}
//用户设定变量的一种取值
void user()
{ int i;
 cout<<"请依次输入你的变元取值"<<endl;
 for(i=65;i<65+N;i++)
 { cout<<char(i)<<" = ";
 cin>>weave[i-65];
 }
}
void main()
{char str[str_max],string[str_max],*pstr;
  int loop=20,choice,i=0,choose,sum;
  bitree Tree;
  while(loop)
  { pstr=str;
  i=0;
  int  SUM=0,l;  //用于累加变量的每种组合的逻辑表达式的结果;可以作为逻辑表达式类//别判别的根据
cout<<"┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n";
cout<<"┃                 实习5.1 重言式判别                   ┃\n";
cout<<"┃                 设计者：林庆达                       ┃\n";
cout<<"┃                 班 级： 计算机(7)班                  ┃\n";
cout<<"┃                 学 号： 80号                         ┃\n";
cout<<"┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n";
cout<<"\n请输入逻辑表达式的变量的个数"<<endl;
  cin>>N;
  sum=int(pow(2,N)); //变量组合的总数;
  cout<<"请输入逻辑表达式(或用'|',与用'&'和非用'~')"<<endl;
  cin>>str;
  //重言式的正确读取
  for(;*pstr!=NULL;pstr++)
     if(*pstr!=' ') string[i++]=*pstr;
  string[i]='#';
  string[i+1]='\0';
cout<<"┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n";
cout<<"┃                     选择操作:                        ┃\n";
cout<<"┃              1、判别逻辑表达式                       ┃\n";
cout<<"┃              2、判别逻辑表达式，并打印出真值表       ┃\n";
cout<<"┃              3、输入变量值求值逻辑表达式             ┃\n";
cout<<"┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n";
  cout<<"选择操作: ";
  cin>>choose;
  switch(choose)
  { case 1://对变量的不同组合依次调用重言式二叉树的求值函数;并判别重言式的类别
      creattree(string,Tree);//建立重言式的二叉树
   for(loop=0;loop<sum;loop++)
   { creatweave(loop);//产生变量取值组合
      SUM+=value_tree(Tree);
  }
  string[i]='\0';
  if(SUM==0) cout<<"逻辑表达式： "<<string<<" 是矛盾式"<<endl;
     if(SUM==sum) cout<<"逻辑表达式： "<<string<<" 是重言式"<<endl;
     if (SUM>0&&SUM<sum)cout<<"逻辑表达式： "<<string<<" 既不是重言式，也不是矛盾式"<<endl;
  break;
 case 2:creattree(string,Tree);//建立重言式的二叉树
  cout<<"         逻辑表达式变量组合的预算结果        "<<endl;
  cout<<" ━━━━━━━━━━━━━━━━━━━━━━"<<endl;
  printf("┃       ");
  for(l=65;l<65+N;l++)
       printf("%-4c",l);
  printf("逻辑表达式的值");
  printf("              ┃\n");
  cout<<" ━━━━━━━━━━━━━━━━━━━━━━"<<endl;
   for(loop=0;loop<sum;loop++)
   {creatweave(loop);//产生变量取值组合
   SUM+=value_tree(Tree);
   printf("┃       ");
   for(int h=0;h<N;h++)
    printf("%-4d",weave[h]);
   printf("%8d",value_tree(Tree));
   printf("                    ┃\n");
   cout<<" ━━━━━━━━━━━━━━━━━━━━━━"<<endl;
  }
  string[i]='\0';
  if(SUM==0) cout<<"逻辑表达式： "<<string<<" 是矛盾式"<<endl;
  else if(SUM==sum) cout<<"逻辑表达式： "<<string<<" 是重言式"<<endl;
  else cout<<"逻辑表达式： "<<string<<" 既不是重言式，也不是矛盾式"<<endl;
  break;
 case 3: creattree(string,Tree);
      user();
   cout<<"逻辑表达式的值为："<<value_tree(Tree)<<endl;
   break;
  } 
  cout<<"继续运算？是(1)/ 否(0):";
  cin>>choice;
  if(choice==0)
   exit(0);
  loop--;
}
}