#include <cstdlib>
#include <iostream>
#include <conio.h>
#define Thing char
using namespace std;
#define STACK_SIZE 50
class Stack{
private:
int stackPtr;
Thing stack[STACK_SIZE];
public:
Stack(void);
int emptyStack(void);
bool push(Thing);
Thing pop(void);
Thing getTop(void);
Thing getElement(int);
int getStackPtr(void);
protected:
};
Stack::Stack(void)
{
stackPtr=-1;
}
int
Stack::emptyStack(void)
{
return stackPtr==-1;
}
bool
Stack::push(Thing iThing)
{
if(stackPtr+1==STACK_SIZE)
return false;
stack[++stackPtr]=iThing;
return true;
}
Thing
Stack::pop(void)
{
return stack[stackPtr--];
}
Thing
Stack::getTop(void)
{
return stack[stackPtr];
}
int
Stack::getStackPtr(void)
{
return stackPtr;
}
class BiTree
{
private: Thing inform;
int value;
BiTree *lchild,*rchild;
public:
BiTree(void);
BiTree(Thing iThing );
BiTree(Thing iThing ,BiTree *lchild ,BiTree *rchild);
BiTree* getRight(void);
BiTree* getLeft (void);
Thing getInform (void);
int getValue(void);
void setValue(int ival);
void setRight(BiTree *iNode);
void setLeft (BiTree *iNode);
void setInform (Thing iThing );
protected:
};
BiTree::BiTree(void)
{
lchild=NULL;
rchild=NULL;
}
BiTree::BiTree(Thing iThing)
{
inform=iThing;
lchild=NULL;
rchild=NULL;
}
BiTree::BiTree(Thing iThing ,BiTree *llchild ,BiTree *rrchild)
{
inform=iThing ;
lchild=llchild ;//開始的時候設的參數與類中的成員lchild和rchild同名，導致參數傳遞失敗！所以后面修改為llchild和rrchild
rchild=rrchild ;
}
BiTree*
BiTree::getRight(void)
{
return rchild;
}
BiTree*
BiTree::getLeft(void)
{
return lchild;
}
Thing
BiTree::getInform(void)
{
return inform ;
}
int
BiTree::getValue(void)
{
return value;
}
void
BiTree::setValue(int ival)
{
value=ival;
}
void
BiTree::setRight(BiTree *iNode)
{
rchild=iNode;
}
void
BiTree::setLeft(BiTree *iNode)
{
lchild=iNode;
}
void
BiTree::setInform(Thing iThing)
{
inform=iThing;
}
#define Thing1 BiTree*
class Stack1{
private:
int stackPtr;
Thing1 stack[STACK_SIZE];
public:
Stack1(void);
int emptyStack(void);
bool push(Thing1);
Thing1 pop(void);
Thing1 getTop(void);
int getStackPtr(void);
protected:
};
Stack1::Stack1(void)
{
stackPtr=-1;
}
int
Stack1::emptyStack(void)
{
return stackPtr==-1;
}
bool
Stack1::push(Thing1 iThing)
{
if(stackPtr+1==STACK_SIZE)
return false;
stack[++stackPtr]=iThing;
return true;
}
Thing1
Stack1::pop(void)
{
return stack[stackPtr--];
}
Thing1
Stack1::getTop(void)
{
return stack[stackPtr];
}
int
Stack1::getStackPtr(void)
{
return stackPtr;
}
bool In(char ch)
{
switch(ch)
{
case '~':
case '|':
case '#':
case '(':
case ')':
case '&':return 1;
default :return 0;
}
}
bool precede(char c,char ch)
{
char ops[7]="|&~#()";
int p1;
for( p1=0;p1!=6;p1++)
if(ops[p1]==c)break;
// printf("p1=%d\n",p1);
int p2;
for( p2=0;p2!=6;p2++)
if(ops[p2]==ch)break;
//printf("p2=%d\n",p2);
int op[6][6]={
// | & ~ # ( )
/*|*/ 1,0,0,1,0,1,
/*&*/ 1,1,0,1,0,1,
/*~*/ 1,1,0,1,0,1,
/*#*/ 0,0,0,0,0,0,
/*(*/ 0,0,0,1,0,1,
/*)*/ 1,1,1,1,0,0 };
// printf("op[p1][p2]=%d\n",op[p1][p2]);
return op[p1][p2];
}
//例如:已知表達式 (a+b)×c – d/e
BiTree* CrtExptree( char exp[] ) {
// 建立由合法的表達式字符串確定的只含二元操作符的
// 非空表達式樹，其存儲結構為二叉鏈表
Stack S;
char cha='#';
S.push(cha);
// printf("gettop cha==%c\n",S.getTop());
Stack1 PTR;
char *p = exp;
char ch = *p;
// printf("ch=%c\n",ch);
char c;
while (!(S.getTop()=='#'&& ch=='#')) {
if (!In(ch)) {if(ch==' ' && ch!='#' ) { p++; ch = *p;continue;}
else{BiTree *t=new BiTree(ch); PTR.push(t);//printf("PTR.getTop()->getInform=%c\n",PTR.getTop()->getInform());getch();
}}
else {
// printf("go into else\n");
switch (ch) {
case '(' : S.push(ch); break;
case ')' : {
// printf("go into ')'");
c=S.pop();
while (c!='(')
{ BiTree *rc=NULL;
BiTree *lc=NULL;
if(c=='~'){rc=PTR.pop(); lc=NULL;}
else{rc=PTR.pop(); lc=PTR.pop();}
BiTree *t=new BiTree(c,lc,rc);
PTR.push(t);
// printf("**************%c*********\n",t->getInform());
c=S.pop();
}
break;
}
default : {
//printf("go into default!\n");
while((c=S.getTop()) && ( precede(c,ch)))
{ //printf("go into while\n");
if(c=='~')
{ BiTree *rc=PTR.pop();
BiTree *lc=NULL;
BiTree *t=new BiTree(c,lc,rc);
PTR.push(t);
S.pop();
}
else{
//getch();
BiTree *rc=PTR.pop();
//printf("rc=%c\n",rc->getInform());
BiTree *lc=PTR.pop();
//printf("lc=%c\n",lc->getInform());
BiTree *t=new BiTree(c,lc,rc);
// printf("t=%c\n",t->getInform());
//printf("t->rignt=%c\n",t->getRight()->getInform());
PTR.push(t);
S.pop();
}
}
if ( ch!='#' ) {S.push(ch);
//printf("S.PUSH=gettop()=%c\n",S.getTop());
}
break;
} // defult
} // switch
} // else
if ( ch!='#' ) { p++; ch = *p;}
} // while
return PTR.pop();
} // CrtExptree
int j[10]={0};
bool visit1(Thing iThing)
{ // static int count[5]={0,0,0,0,0};
printf("%c",iThing);
switch(iThing){
case 'A': j[0]++; break;
case 'B':j[1]++;break;
case 'C':j[2]++;break;
case 'D':j[3]++;break;
case 'E':j[4]++;break;
case 'F':j[5]++;break;
case 'G':j[6]++;break;
case 'H':j[7]++;break;
case 'I':j[8]++;break;
case 'J':j[9]++;break;
}
return 1;
}
//int jie[5]={1,2,6,24,120};
//int *p=(int*)malloc(jie[n-1]*(sizeof(int));
bool visit2(BiTree *p)
{
if(p){
switch(p->getInform()){
case '~':{int ival=p->getRight()->getValue(); ival=!(ival);p->setValue(ival);break; }
case 'A':{p->setValue(j[0]);/*printf("A==%d\n",j[0]);*/break;}
case 'B':{p->setValue(j[1]);/*printf("B==%d\n",j[1]);*/break;}
case 'C':{p->setValue(j[2]);/*printf("C==%d\n",j[2]);*/break;}
case 'D':{p->setValue(j[3]);/*printf("D==%d\n",j[3]);*/break;}
case 'E':{p->setValue(j[4]);/*printf("E==%d\n",j[4]);*/break;}
case 'F':{p->setValue(j[5]);/*printf("F==%d\n",j[5]);*/break;}
case 'G':{p->setValue(j[6]);/*printf("G==%d\n",j[6]);*/break;}
case 'H':{p->setValue(j[7]);/*printf("H==%d\n",j[7]);*/break;}
case 'I':{p->setValue(j[8]);/*printf("I==%d\n",j[8]);*/break;}
case 'J':{p->setValue(j[9]);/*printf("J==%d\n",j[9]);*/break;}
case '|':{p->setValue( p->getLeft()->getValue() || p->getRight()->getValue());break;}
case '&':{p->setValue( p->getLeft()->getValue() && p->getRight()->getValue());break;}
}
return 1;} else
return 0;
}
bool
InOderTraverse(BiTree *p ,bool(*visit)(Thing))
{
if(p)
{
if(InOderTraverse(p->getLeft(),visit))
if(visit(p->getInform()))
if(InOderTraverse(p->getRight(),visit))
return 1;
return 0;
}
else return 1;
}
bool
PostOderTraverse(BiTree *p ,bool(*visit)(BiTree*))
{
if(p)
{
if(PostOderTraverse(p->getLeft(),visit))
if(PostOderTraverse(p->getRight(),visit))
if(visit(p))
return 1;
return 0;
}
else return 1;
}
int val_num=0;
void call(int k)
{
if(j[k]==2)
{j[k]=0;
j[++k]++;
if(k<=val_num)
call(k);
}
else return ;
}
int main(int argc, char *argv[])
{
int i;
char exp[20]="A&~B|~A&B";
// scanf("%s",exp);
int len=strlen(exp);
exp[len++]='#';
exp[len]='\0';
// printf("%s",exp);
BiTree *p=CrtExptree(exp);
//int sum[6]={0};
InOderTraverse(p ,visit1);
cout<<endl;
for(i=0;i<10;i++)
if(j[i]){val_num++;j[i]=0;}
printf("val_num=%d\n",val_num);
//getch();
int counts=1;
for(i=1;i<=val_num;i++)
counts*=2;
// printf("counts=%d\n",counts); getch();
int *sum=(int *)malloc(counts*sizeof(int));
for(i=0;i<counts;i++)
sum[i]=0;
for(i=0;i<counts;i++)
{ //printf("case 1 ====i=%d\n",i);
call(0);
//if(j[0]==2)
//{j[0]=0;
//j[1]++;if(j[1]==2)
// {j[1]=0;
// j[2]++;
// }
//}
int jl;
//printf("case 2 ====i=%d\n",i);
for(jl=val_num-1;jl>=0;jl--)
cout<<j[jl];
cout<<endl;
// getch();
// printf("case 3 ====i=%d\n",i);
PostOderTraverse(p ,visit2);
// printf("case 4 ====i=%d\n",i);
sum[i]=p->getValue();
//printf("case 5 ====i=%d\n",i);
printf("sum%d=%d\n",i+1,sum[i]);
j[0]++;
}
int isTrue=0;
int isFalse=0;
//int isSatis;
for(i=0;i<counts;i++)
{
if(sum[i]==1)isTrue++;
if(sum[i]==0)isFalse++;
}
free(sum);
if(isTrue==counts)printf("True forever!\n");
else if(isFalse==counts)printf("False forever!\n");
else {printf("Satisfactible!\n");
for(i=0;i<val_num;i++)
{ scanf("%d",&j[i]);printf("j[%d]==%d\n",i,j[i]);
fflush(stdin);
}
PostOderTraverse(p ,visit2);
printf("sum=%d\n",p->getValue());
};
//printf("%c\n",p->getInform());
// printf("%c\n",(p->getLeft())->getInform());
//printf("after creater!\n");
system("PAUSE");
return EXIT_SUCCESS;
}