An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Figure 1

Input Specification:

Each input file contains one test case. For each case, the first
line contains a positive integer N (<=30) which is the total number
of nodes in a tree (and hence the nodes are numbered from 1 to N). Then
2N lines follow, each describes a stack operation in the format: "Push
X" where X is the index of the node being pushed onto the stack; or
"Pop" meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the
corresponding tree in one line. A solution is guaranteed to exist. All
the numbers must be separated by exactly one space, and there must be
no extra space at the end of the line.

Sample Input:

6

Push 1

Push 2

Push 3

Pop

Pop

Push 4

Pop

Pop

Push 5

Push 6

Pop

Pop

Sample Output:

3 4 2 6 5 1

 #include <string>

 #include <vector>

 #include <iostream>

 #include <stack>

 using namespace std;

 void print(int t, int &flag)

 {

     if(flag){

         flag = ;

         cout << t;

     }else{

         cout << ' ' << t;

     }

 }

 int main()

 {

     int n;

     const string s1 = "Push";

     const string s2 = "Pop";

     while(cin >> n){

         n <<= ;

         vector<string> input(n,"");

         vector<int> val(n,);

         for(int i = ; i < n; ++i){

             cin >> input[i];

             if(input[i] == s1)

               cin >> val[i];

         }

         stack<int> stk;

         stack<int> root;

         vector<int> rightchild(n>>,);

         int flag = ;

         for(int i = ; i < n; ++i){

             if(input[i] == s1){

                 stk.push(val[i]);

             }else{

                 if(i+ >= n || input[i+] == s2){

                     int t = stk.top();

                     stk.pop();

                     if(root.empty()){

                         print(t,flag);

                     }else{

                         while(!root.empty() && rightchild[root.top()] == t){

                             print(t,flag);

                             t = root.top();

                             root.pop();

                         }

                         print(t,flag);

                     }

                 }else{

                     int t = stk.top();

                     stk.pop();

                     root.push(t);

                     rightchild[t] = val[i+];

                 }

             }

         }

         cout << endl;

     }

     return ;

 }