char str[STARMAXLEN];//存放输入的
int varitab[VARIMAXNUM+1];//取值组合
int sum;
BiTree root;//定义树的根
SqStack OPTR,OPND;//定义逻辑运算符和变元栈

char cmp(char a,char b)             //取左右交叉的符号即"<"">""="
{
    int i,j;
    for(i=0;i<=6;i++)
    {
        if(OPTRCHART[i][0]==a)
            break;
    }
    for(j=0;j<=6;j++)
    {
        if(OPTRCHART[0][j]==b)
            break;
    }
    return OPTRCHART[i][j];
}


void CreatBiTree()            //  建树
{
   
    BiTree temp,a,b;
    char *p=str;//变量赋值
    temp=(BiTree)malloc(sizeof(BiTNode));
    temp->data='#';
    Push(&OPTR,temp);
    while((*p!='#')||(GetTop(&OPTR)->data!='#'))
    {
        if((*p>=65)&&(*p<=90))
        {
            temp=(BiTree)malloc(sizeof(BiTNode));
            temp->data=*p;
            temp->Lchild=NULL;
            temp->Rchild=NULL;
            Push(&OPND,temp);
            p++;
        }
        
        else
        {
            switch(cmp(GetTop(&OPTR)->data,*p))    //开始判断优先级
            {
            case '<':     //栈顶的运算符优先级小，入栈
                temp=(BiTree)malloc(sizeof(BiTNode));
                temp->data=*p;
                temp->Lchild=NULL;
                temp->Rchild=NULL;
                Push(&OPTR,temp);
                p++;
                break;
            case '=':    //运算符的优先级相等，脱括号
                temp=Pop(&OPTR);
                free(temp);//释放括号结点的空间
                p++;
                break;
            case '>':   //栈顶的运算符的优先级高，出栈
                temp=Pop(&OPTR);
                b=Pop(&OPND);
                temp->Rchild=b;
                if(temp->data!='~')//出栈的运算符有两个操作数
                {
                a=Pop(&OPND);
                temp->Lchild=a;
                }
                Push(&OPND,temp);
                break;
            }/*switch*/
        }/*else*/
    }/*while*/
    root=Pop(&OPND);//若为空表达式,则返回NULL
    temp=Pop(&OPTR);//去除运算符栈的伪栈底，并将其所占内存单元释放
    free(temp);
}

void DestroyBiTree(BiTree tree){           //销毁树并取出需要的值
    if(!tree){
        return;
    }
    else if((tree->Lchild==NULL)&&(tree->Rchild==NULL)){
        free(tree);
        return;
    }
    else{
        DestroyBiTree(tree->Lchild);
        DestroyBiTree(tree->Rchild);
        free(tree);
    }
}


int GetValue(BiTree tree){      
    if(!tree){     //是空变元
        return 0;
    }
    else if((tree->data>=65)&&(tree->data<=90)){
        return varitab[tree->data-64]; //变元
    }
    else if((tree->data>=97)&&(tree->data<=122))
    {
        return varitab[tree->data-96];//是逻辑元算符
    }
    else{
        switch(tree->data){
        case '|':
            return (GetValue(tree->Lchild)||GetValue(tree->Rchild));
        case '&':
            return (GetValue(tree->Lchild)&&GetValue(tree->Rchild));
        case '~':
            return (!GetValue(tree->Rchild));
        }
    }
   
}

void destroy()             //销毁栈
{
   
    DestroyStack (&OPTR);
    DestroyStack (&OPND);
}
void init(){
    InitStack(&OPTR);
    InitStack(&OPND);
    *varitab=0;
    sum=(int)pow(2.0,*varitab);
    root=NULL;
    str[0]='#';
}
   

void input(){                       // 为了能继续输入需要判别的式子
    char *p,*q;

    printf("请输入要判断的式子中变元的数目\n");
    scanf("%d",varitab);
    while(*varitab<=0){
        printf("错误，请重新输入数字！\n");
        printf("请输入要判断的式子中变元的数目:\n");
        scanf("%d",varitab);
    }
    getchar();
    sum=(int)pow(2.0,*varitab);
    printf("输入要判别的式子：\n");
    gets(str);
    for(p=q=str;*p;p++)
        if(*p!=' ')
            *q++=*p;
        *q='#';

}
void Varitab(int n)
{
    int i;
    for(i=0;i<*varitab;i++)
        varitab[*varitab-i]=(n>>i)%2;
}

void table()
{
    int i,j,value;
    printf("真值表为：\n");
    for(i=1;i<=*varitab;i++)
        printf("%c ",64+i);
    printf("\n");
    for(i=0;i<sum;i++)
    {
        Varitab(i);
        for(j=1;j<=*varitab;j++)
            printf("%d ",varitab[j]);
        value=GetValue(root);
        if(value)
            printf("真\n");
        else
            printf("假\n");
    }
}
void mutualcm()
{
    int i,value,truenum=0,falsenum=0,cmd;
    for(i=0;i<sum;i++)
    {
        Varitab(i);
        value=GetValue(root);
        if(value)
            truenum++;
        else
            falsenum++;
    }

    if(truenum==sum)
        printf("True forever！！\n");
    else if(falsenum==sum)
        printf("False forever！！\n");
    else
    {
        printf("Satisfactible！！\n");
        printf("******请进行选择******\n");
        printf("****1 进行用户输入验证****\n");
        printf("****2 计算机进行列举验证****\n");
        scanf("%d",&cmd);
        if(cmd==1)
        {
            printf("输入变元值：\n");
            for(i=1;i<=*varitab;i++)
            {
                printf("%c=",64+i);
                scanf("%d",varitab+i);
            }
            value=GetValue(root);
            if(value)
                printf("真！！\n");
            else
                printf("假！！\n");
        }else
        {
            table();
        }

    }
}