#include <iostream>
#include <assert.h>
using namespace std;
#define FIRST "ABCDEFGH"
#define MIDDLE "CBEDAGHF"
//function description: get the last-root order from the first-root order and middle-root order
//the recursive form of the needed function as follows.
char* getFirstRootOrder(const char* first,const char* middle,int len,char* last){
if(0==len)return last+1;//return the position where the character has been filled.
char root=*first;
int root_pos=-1;
while(middle[++root_pos]!=root);//get the position in the middle-order string.
*last=root;
char * rev=getFirstRootOrder(&first[root_pos+1],&middle[root_pos+1],len-root_pos-1,last-1);
rev=getFirstRootOrder(first+1,middle,root_pos,rev-1);//'rev-1' is a position that any character hasn't filled.
return rev;
}
//the non-recursive form of the needed function as follows.
struct Node{
const char* f;//the pointer of the first-order string
const char* m;//the pointer of the middle-order string
int len;//the length of the processing string
};
void getFRONR(const char* first, const char* middle,char* last){
assert(first!=NULL && middle!=NULL);
assert(strlen(first)==strlen(middle));
int len=strlen(first);
const char *pf=first;
const char *pm=middle;
Node *pstack=new Node[len];
int index=0;
int I_pos=len-1;
do{
while(len!=0){
int root_pos=0;
while(pm[root_pos++]!=*pf);
last[I_pos--]=*pf;
//push operation of the stack
//the left-hand sub-tree is pushed into the stack
pstack[index].len=root_pos-1;
pstack[index].f=pf+1;
pstack[index++].m=pm;
//update the new right-hand sub-tree
len=len-root_pos;
pf=pf+root_pos;
pm=pm+root_pos;
}
if(index>0){//pop operation of the stack
len=pstack[--index].len;
pf=pstack[index].f;
pm=pstack[index].m;
}
}while(index>0 || len!=0);
delete [] pstack;
}
void main(){
int len=strlen(FIRST);
assert(strlen(MIDDLE)==len);
char *first=new char[len+1];
strcpy(first,FIRST);
char *middle=new char[len+1];
strcpy(middle,MIDDLE);
char *last=new char[len+1];
memset(last,0,len+1);
getFirstRootOrder(first,middle,len,last+len-1);
cout<<last<<endl;
getFRONR(first,middle,last);
cout<<last<<endl;
delete [] first;
delete [] middle;
delete [] last;
}