newplan

阿基米德在洗澡時發現浮力原理,高興得來不及穿㆖褲子,跑到街㆖大喊:Eureka(我找到了)。
posts - 39, comments - 26, trackbacks - 0, articles - 4
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

重言式判别-二叉树实现

Posted on 2007-12-04 18:10 山泉弯延 阅读(2654) 评论(0)  编辑 收藏 引用 所属分类: 数据结构实验集
#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 
*= 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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理