#include <iostream>
#include <string>
#include <stack>
using namespace std;
struct node;
typedef node *pNode;
struct node {
     char data;
     pNode left, right;
};
string line;
string::iterator it;
// 前序扩展序列建立二叉树  
void plant(pNode &root)
{
     if (it == line.end())
         return;
     char data = *it++;
     if (data == '/')
         root = NULL;
     else {
         root = new node();
         root->data = data;
         plant(root->left);
         plant(root->right);
     }
}
// 先序遍历  
void pre_order(pNode root)
{
     stack<pNode> s;
     while (root != NULL || !s.empty())
     {
         if (root != NULL) {
             cout << root->data << " ";
             s.push(root);
             root = root->left;
         } else {
             root = s.top();
             s.pop();
             root = root->right;
         }
     }
}
// 中序遍历  
void in_order(pNode root)
{
     stack<pNode> s;
     while (root != NULL || !s.empty())
     {
         if (root != NULL) {
             s.push(root);
             root = root->left;
         } else {
             root = s.top();
             s.pop();
             cout << root->data << " ";
             root = root->right;
         }
     }
}
// 压栈的参数类型，包括局部变量和行号  
struct stack_arg {
     stack_arg(pNode _root, int _line)
     : root(_root), line(_line) { }
     pNode root;
     int line;
};
// 后序遍历  
void post_order(pNode root)
{
     stack<stack_arg> s;
     s.push(stack_arg(root, 1));
     while (!s.empty())
     {
         switch (s.top().line) {
         case 1:
             if (s.top().root == NULL)
                 s.pop();
             else
                 s.top().line = 2;
             break;
         case 2:
             s.top().line = 3;  
             s.push(stack_arg(s.top().root->left, 1));
             break;
         case 3:
             s.top().line = 4;
             s.push(stack_arg(s.top().root->right, 1));
             break;
         case 4:
             cout << s.top().root->data << " ";
             s.pop();
             break;
         }
     }
}
int main()
{
     cin >> line;
     it = line.begin();
     pNode root = NULL;
     plant(root);
     cout << "先序遍历" << endl;  
     pre_order(root);
     cout << endl;
     cout << "中序遍历" << endl;  
     in_order(root);
     cout << endl;
     cout << "后序遍历" << endl;  
     post_order(root);
     cout << endl;
     system("pause");
     return 0;
}
/*
input
     ABDI//J//EK//LQ///CFM//N//GO//P//
output
     先序遍历:
     A B D I J E K L Q C F M N G O P
     中序遍历
     I D J B K E Q L A M F N C O G P
     后序遍历  
     I J D K Q L E B M N F O P G C A