tautology_discriminant.cpp

实现同言式的判别。数据结构习题集作业。输入表达式

// 重言式判别2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#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(int argc, char* argv[])
{
    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)); //变量组合的总数;功能：计算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<<"请选择你要的操作: "<<endl;

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

 
	}
}