/*************************************************************************
        > File Name: 广义表转二叉树.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月18日 星期二 14时33分25 秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
typedef struct Node {
    char data;
    struct Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root;
    int length;
} Tree;

typedef struct Stack {
    Node **data;
    int top, size;
} Stack;

Node *getNewNode(char val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->lchild = p->rchild = NULL;
    return p;
}

Tree *getNewTree() {
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    tree->root = NULL;
    tree->length = 0;
    return tree;
}

Stack *init_stack(int n) {
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->data = (Node **)malloc(sizeof(Node *) * n);
    s->top = -1;
    s->size = n;
    return s;
}

Node *top(Stack *s) {
    return s->data[s->top];
}

int empty(Stack *s) {
    return s->top == -1;
}

int push(Stack *s, Node *val) {
    if(s == NULL) return 0;
    if(s->size - 1 == s->top) return 0;
    s->data[++(s->top)] = val;
    return 1;
}

int pop(Stack *s) {
    if(s == NULL) return 0;
    if(empty(s)) return 0;
    s->top--;
    return 1;
}

void clear_stack(Stack *s) {
    if(s == NULL) return ;
    free(s->data);
    free(s);
    return ;
}
void clear_node(Node *root) {
    if(root == NULL) return ;
    clear_node(root->lchild);
    clear_node(root->rchild);
    free(root);
    return ;
}

void clear_tree(Tree *tree) {
    if(tree == NULL) return ;
    clear_node(tree->root);
    free(tree);
    return ;
}

Node *build(const char *str, int *node_num) {
    Stack *s = init_stack(strlen(str));
    int falg = 0;
    Node *temp = NULL, *p =NULL;
    while(str[0]) {
        switch(str[0]) {
            case '(' : {
                push(s, temp);
                falg = 0;
            } break;
            case ')' : {
                p = top(s);
                pop(s);
            } break;
            case ',' : falg = 1; break;
            case ' ' : break;
            default :
                temp = getNewNode(str[0]);
            if(!empty(s) && !falg) {
                top(s)->lchild = temp;
            } else if(!empty(s) && falg){
                top(s)->rchild = temp;
            }
            ++(*node_num);
        }
        ++str;
    }
    clear_stack(s);
    if(temp && p == NULL) p = temp;
    return p;
}

// 前 根 左 右
void pre_order_node(Node *root) {
    if(root == NULL) return ;
    printf("%c ", root->data);
    pre_order_node(root->lchild);
    pre_order_node(root->rchild);
    return ;
}

// 前
void pre_order(Tree *tree) {
    if(tree == NULL) return ;
    printf("pre_order (%d) : ", tree->length);
    pre_order_node(tree->root);
    printf("\n");
    return ;
}

// 中 左 根 右
void in_order_node(Node *root) {
    if(root == NULL) return ;
    in_order_node(root->lchild);
    printf("%c ", root->data);
    in_order_node(root->rchild);
    return ;
}

// 中
void in_order(Tree *tree) {
    if(tree == NULL) return ;
    printf("in_order (%d) : ", tree->length);
    in_order_node(tree->root);
    printf("\n");
    return ;
}

// 后 左 右 根
void post_order_node(Node *root) {
    if(root == NULL) return ;
    in_order_node(root->lchild);
    in_order_node(root->rchild);
    printf("%c ", root->data);
    return ;
}

// 后
void post_order(Tree *tree) {
    if(tree == NULL) return ;
    printf("post_order (%d) : ", tree->length);
    post_order_node(tree->root);
    printf("\n");
    return ;
}

int main() {
    char str[1000] = {0};
    int node_num = 0;
    scanf("%[^\n]s", str);
    getchar();
    Tree *tree = getNewTree();
    tree-> root = build(str, &node_num);
    tree->length = node_num;
    pre_order(tree);
    in_order(tree);
    post_order(tree);
    return 0;
}