#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<math.h>



#define stack_size_normal 100
#define bianliang_max 20
#define str_max 60



int zuhe[bianliang_max];//變量的取值組合數(shù)組定義;
int N;//變量個數(shù);



//根據(jù)表達式建立的二叉樹的結(jié)點定義;
typedef struct btdnode{
char data;
struct btdnode *lchild; 
struct btdnode  *rchild;
}*bitree;



//識別表達式使用的堆棧定義,它存放的都是樹的結(jié)構(gòu);
typedef struct lnode_optr{      
struct btdnode **base;    //棧中的元素都是樹的結(jié)點結(jié)構(gòu)；
struct btdnode **top;
int stacksize;
}sqstack;




//用于產(chǎn)生變量的各種取值組合;



void creatzuhe(int n)
{
int i,num=0,j=0,e;
int temp[bianliang_max];
    for(i=0;i<N;i++)
  zuhe[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--];
  zuhe[num++]=e;
}
}



//自底向上地根據(jù)運算符地優(yōu)先級來建立分子樹函數(shù);當邏輯表達式讀完后-子根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;
   }



}
}

//邏輯運算符的優(yōu)先級判別；
char youxianji(char lie,char hang)
{
int    i,j;
char bijiao[7][7]={' ','|','&','~','(',')','#',
                 '|','>','<','<','<','>','>',
                       '&','>','>','<','<','>','>',                                                                                                                                                                                                                                                                                                                                                                                                                                                         
                       '~','>','>','>','<','>','>',
        '(','<','<','<','<','=',' ',
        ')','>','>','>',' ','>','>',
        '#','<','<','<','<',' ','='};
for(i=0;i<7;i++)
   if(bijiao[0][i]==lie)
    break;
for(j=0;j<7;j++)
   if(bijiao[j][0]==hang)
    break;
   return bijiao[j][i];
}
//對操作符棧和變量堆棧的操作；
void creatstack(sqstack &st)
{

    st.base=(bitree*)malloc(stack_size_normal*sizeof(btdnode));
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);
}



//重言式的識別函數(shù)；
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(btdnode));
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(btdnode));
   if(!variables)  exit(0);
   variables->data=*s;
   push(variable,variables);
    }
    else if(int(*s)>90||int(*s)<65)
    {  
      gettop(logic,e);//取運算符棧的棧頂元素進行優(yōu)先級比較
     switch(youxianji(*s,e->data))
   {
   case '<': //棧頂?shù)倪\算符優(yōu)先級低,邏輯運算符進棧
          logics=(bitree)malloc(sizeof(btdnode));
             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);
      //建樹的函數(shù)調(diào)用
      k=k+1;
      create(theta,b,a);
      
                     push(variable,theta);//將臨時的根作為新的變量壓入變量棧中;
         if(*s!='#'&&*s!=')') 
      {
      logics=(bitree)malloc(sizeof(btdnode));
               if(!logics)  exit(0);
               logics->data=*s;
               push(logic,logics);
      }
      else  s=s-1;
      break;
   }
    }
   s++;
}
tree=theta;
}
//根據(jù)變量的取值組合并利用邏輯表達式的性質(zhì)對樹進行求值 
int value_tree(bitree tree)
{
    if(!tree) return 0;                                       //遇到空的結(jié)點;
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->lchild)||value_tree(tree->rchild));
   case '&': return(value_tree(tree->lchild)&&value_tree(tree->rchild));
   case '~': return(!value_tree(tree->rchild));
   }



}
//用戶設(shè)定變量的一種取值；
void user()
{
int i;

cout<<"請依次輸入你的變元取值"<<endl;
for(i=65;i<65+N;i++)
{
cout<<char(i)<<" = ";
cin>>zuhe[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;  //用于累加變量的每種組合的邏輯表達式的結(jié)果;可以作為邏輯表達式類別判別的根據(jù)
  cout<<"請輸入邏輯表達式的變量的個數(shù)"<<endl;
  cin>>N;
  sum=int(pow(2,N)); //變量組合的總數(shù);
  cout<<"請輸入邏輯表達式的表達式(或用'|',與用'&'和非用'~')"<<endl;
  cin>>str;
  //重言式的正確讀取;
  for(;*pstr!=NULL;pstr++)
     if(*pstr!=' ') string[i++]=*pstr;
  string[i]='#';
  string[i+1]='\0';
  cout<<"************            請選擇你要的操作              **********"<<endl;
  cout<<"************ 1 邏輯表達式的判別(不顯示各種取值組合的結(jié)果) **********"<<endl;
  cout<<"************ 2 邏輯表達式的判別(并顯示各種取值組合的結(jié)果) **********"<<endl;
  cout<<"************ 3 邏輯表達式的求值(根據(jù)用戶的取值)           **********"<<endl;
  cout<<"請選擇你要的操作: ";
  cin>>choose;
  switch(choose)
  {
  case 1://對變量的不同組合依次調(diào)用重言式二叉樹的求值函數(shù);并判別重言式的類別;
      creattree(string,Tree);//建立重言式的二叉樹;
  
   for(loop=0;loop<sum;loop++)
   {
       
            creatzuhe(loop);//產(chǎn)生變量取值組合;
      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<<"         邏輯表達式變量組合的預(yù)算結(jié)果        "<<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++)
   {
      creatzuhe(loop);//產(chǎn)生變量取值組合;
   SUM+=value_tree(Tree);
   
        printf("|       ");
   for(int h=0;h<N;h++)
    printf("%-4d",zuhe[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<<"是否繼續(xù)進行運算？是按1/ 否按0:";
  cin>>choice;
  if(choice==0)
    exit(0);
  loop--;




  }
}