1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5  6 void func(vector
       
        kind,int count[],int n) 7 { 8     if(count[0]>=1) 9     {10         kind.push_back('(');11         count[0]--;12         func(kind,count,n);13         count[0]++;14         kind.pop_back();15     }16     if((count[1]>=1) && (count[1]>count[0]))17     {18         kind.push_back(')');19         count[1]--;20         func(kind,count,n);21         count[1]++;22         kind.pop_back();23     }24     if(kind.size()==2*n)25     {26         vector
        
         ::iterator iter;27         for(iter=kind.begin();iter!=kind.end();iter++)28         {29             cout<<(*iter)<<" ";30         }31         cout<
         
          >n;41     int count[2]={n-1,n};42     vector
          
           kind;43 kind.push_back('(');44 func(kind,count,n);45 return 0;46 }
          
         
        
       
      
     

count[0]存着左括号数目，count[1]存着右括号数目。一开始kind中压入左括号，因为第一个肯定是左括号。然后count数组初始化为n-1个左括号，n个右括号。然后我们递归的处理。如果剩余左括号数count[0]大于0，就可以把左括号压栈。而对于右括号，栈中左括号个数必须多于右括号个数，也就是剩余右括号个数大于左括号个数，即count[1]>count[0]时，才能将右括号压栈。如果栈中元素个数达到2n时，就把栈中元素输出。

下面贴出出栈序列代码，几乎和上面相同。

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6  7 int number=0; 8 void func(vector
        
         kind,int count[],int n,int A[]) 9 {10     if(count[0]>=1)11     {12         kind.push_back(1);13         count[0]--;14         func(kind,count,n,A);15         count[0]++;16         kind.pop_back();17     }18     if((count[1]>=1) && (count[1]>count[0]))19     {20         kind.push_back(0);21         count[1]--;22         func(kind,count,n,A);23         count[1]++;24         kind.pop_back();25     }26     if(kind.size()==2*n)27     {28         vector
         
          ::iterator iter;29         stack
          
           stk;30 int j=0;31 for(iter=kind.begin();iter!=kind.end();iter++)32 {33 //cout<<(*iter)<<" ";//*iter记录的是进栈和出栈的顺序，1为进栈，0为出栈 34 if(1==(*iter))35 {36 stk.push(A[j]);37 j++;38 }39 else40 {41 cout<
           
            <<" ";42 stk.pop();43 }44 }45 number++;46 cout<
            
             >n;56 int A[n];57 cout << "please input the push sequence:" << endl;58 for(i=0;i
             
              >A[i];61 }62 int count[2]={n-1,n};63 vector
              
               kind;64 kind.push_back(1);65 66 cout<<"the result is:"<
              
             
            
           
          
         
        
       
      
     

 

 要注意到前一题括号的（*iter）是对栈内元素进行输出，而后一题序列(*iter)是考虑出栈的顺序~~~~纠结一晚上

 

 

1 /*************** 2 输出栈 3 *********************/ 4  5 #include
      
        6 #include
       
         7 #include
        
          8 #include
         
           9 #include
          
           10 using namespace std;11 12 int key=1,number=0;13 void function(vector
           
            v,int count[],int n)14 {15 key=1;16 if(count[0]>=1)17 {18 v.push_back(1);19 count[0]--;20 function(v,count,n);21 v.pop_back();22 count[0]++;23 }24 if(count[1]>count[0]&&(count[1]>=1) )25 {26 v.push_back(0);27 count[1]--;28 function(v,count,n);29 v.pop_back();30 count[1]++;31 }32 if(v.size()==2*n)33 {34 vector
            
             ::iterator iter;35 stack
             
              stk;36 int j=0;37 for(iter=v.begin();iter!=v.end();iter++)38 {39 if((*iter)==1)40 {41 stk.push(key);42 key++;43 }44 else45 {46 printf("%d ",stk.top());47 stk.pop();48 }49 }50 number++;51 printf("\n");52 }53 }54 55 int main()56 {57 int n,count[2],i;58 scanf("%d",&n);59 count[0]=n-1;60 count[1]=n;61 vector
              
               v;//创建一个整型容器62 v.push_back(1);//先把一个元素压栈63 function(v,count,n);64 printf("共有%d组\n",number);65 66 67 68 }