#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];//變量的取值組合數組定義;
int N;//變量個數;

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

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


//用于產生變量的各種取值組合;

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;
 }
}

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

//重言式的識別函數；
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);//取運算符棧的棧頂元素進行優先級比較
     switch(youxianji(*s,e->data))
   {
   case '<': //棧頂的運算符優先級低,邏輯運算符進棧
          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);
      //建樹的函數調用
      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;
}
//根據變量的取值組合并利用邏輯表達式的性質對樹進行求值 
int value_tree(bitree 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->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>>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;  //用于累加變量的每種組合的邏輯表達式的結果;可以作為邏輯表達式類別判別的根據
  cout<<"請輸入邏輯表達式的變量的個數"<<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<<"************            請選擇你要的操作              **********"<<endl;
  cout<<"************ 1 邏輯表達式的判別(不顯示各種取值組合的結果) **********"<<endl;
  cout<<"************ 2 邏輯表達式的判別(并顯示各種取值組合的結果) **********"<<endl;
  cout<<"************ 3 邏輯表達式的求值(根據用戶的取值)           **********"<<endl;
  cout<<"請選擇你要的操作: ";
  cin>>choose;
  switch(choose)
  {
  case 1://對變量的不同組合依次調用重言式二叉樹的求值函數;并判別重言式的類別;
      creattree(string,Tree);//建立重言式的二叉樹;
  
   for(loop=0;loop<sum;loop++)
   {
       
            creatzuhe(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++)
   {
      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");
   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--;

 
  }
}