問題解決レポート-PAT-Tree Traversals Again(1086)

問題解決レポート-PAT-Tree Traversals Again
Tree Traversals Againには2つの解題構想があります.
1.PushとPopの過程で後のシーケンスを記録する.2、先頭シーケンスと中間シーケンスを構築し、build後シーケンスを構築します.PAT原題リンク:https://www.patest.cn/contests/pat-a-practise/1086
次の2つのアルゴリズムを示します:アルゴリズム1:

# include 
# include 
# include 
# define MAX 60

typedef struct stack{
	int top;
	int data[MAX];
	int flag[MAX];  //     0.        ，1.        。                  
}ST;
/**
    ：
	        ，           ，    ，         ，         。
              ，            ：
1.                ，    build(n,s1,s2,ans);        。
2.     ， Push Pop             。
	   s。 
	     Push ，        ，            ，     0，            。
     Pop ，               ，      pop s   ，   s        1，        
         ，          。        1    pop      1   ，          
      。
   Push:    s  push，    0
   Pop:        s  pop    1   ，     ，    0  ，    。         1，     
			        。 
**/ 
ST s;   //    
int main(){
	char str[10];
	int t, n, ans[MAX], j=0;
	cin >> n;

	s.top = 0;   //     0    
	for(int i = 0; i < MAX; i++){
		s.flag[i] = 0;
	}
	for(int i = 0;i < 2*n; i++){
		cin >> str;
		if(strcmp(str,"Push") == 0){ //  push 
			cin >> t;
			s.data[s.top] = t;
			s.flag[s.top++] = 0;

		}else{ //    pop 
			//       1    
			while(s.top!=0){
				if(s.flag[s.top-1] == 1)
					ans[j++] = s.data[--s.top];
				else
					break;
			}
			s.flag[s.top-1] = 1; //       1            。 
		}
	}
	while(s.top!=0) //         ，     
		ans[j++] = s.data[--s.top];
	
	for(int i=0;i

アルゴリズム2:

# include 
# include 
# include 
# include 
# define MAX 60
using namespace std;

stack s;
void build(int n,char *s1,char* s2,char *s){
	if(n<=0) //        
		return;
	int p=strchr(s2,s1[0]) - s2; //  s1[0] s2    
	build(p,s1+1,s2,s);
	build(n-p-1,s1+p+1,s2+p+1,s+p); //     n-p-1   
	s[n-1]=s1[0]; 
}
int main(){
	char str[5];
	int s1[MAX],s2[MAX];
	int j1=0,j2=0,t,n;
	cin >> n;
	for(int i=0;i<2*n;i++){
		cin>>str;
		if(strcmp(str,"Push") == 0){
			cin>>t;
			s.push(t);
			s1[j1++] = t;
		}else{
			s2[j2++]=s.top();
			s.pop();
		}
	}
	char str1[MAX],str2[MAX],ans[MAX];
	for(int i=0;i

アルゴリズム2はPATのコミットテストにおいて、N=30であり、複雑な組み合わせであり、テストポイント5は合格しなかった.後序研究を保留したり、原因を知っている人がいたら連絡してください.