import java.io.*;
 
class BetterTreeApp {
    public static void main(String[] args) throws IOException{
        System.out.print("Enter postfix expression: ");
        String data = getString();
        Monkey monkey = new Monkey(data);
        monkey.see();
    }
 
    public static String getString() throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }
}
 
class Node {
    boolean isRoot = false;
    boolean isOperator;
    boolean hasRightChild = false;
    boolean hasLeftChild = false;
    Node parent;
    Node rightChild;
    Node leftChild;
    String data;
 
    public Node(String d, boolean oper) {
        isOperator = oper;
        data = d;
    }
}
 
class Tree {
    Node root;
    Node activeNode;
 
    public Tree(Node newNode){
        root = newNode;
        activeNode = root;
    }
 
    public void display() {
        UberStack globalStack = new UberStack();
        globalStack.push(root);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        System.out.println("................................................................................");
 
        while(!isRowEmpty) {
            UberStack localStack = new UberStack();
            isRowEmpty = true;
 
            for(int j=0; j < nBlanks; j++) System.out.print(' ');
 
            while(!globalStack.isEmpty()) {
                Node temp = (Node)globalStack.pop();
                if(temp != null) {
                    System.out.print(temp.data);
                    localStack.push(temp.leftChild);
                    localStack.push(temp.rightChild);
 
                    if(temp.leftChild != null || temp.rightChild != null) isRowEmpty = false;
                } else {
                    System.out.print("--");
                    localStack.push(null);
                    localStack.push(null);
                }
                for(int j=0; j<nBlanks*2-2; j++) System.out.print(' ');
            }
            System.out.println();
            nBlanks /= 2;
 
            while(!localStack.isEmpty()) globalStack.push(localStack.pop());
        }
        System.out.println("................................................................................");
        System.out.print("pre order: ");
        preOrder(root);
        System.out.println("");
        System.out.print("in order: ");
        inOrder(root);
        System.out.println("");
        System.out.print("post order: ");
        postOrder(root);
        System.out.println("");
    }
 
    private boolean isOper(String s) {
        if(s.equals("0") || s.equals("1") || s.equals("2") || s.equals("3") || s.equals("4") || s.equals("5") || s.equals("6") || s.equals("7") || s.equals("8") || s.equals("9")) return false;
        else return true;
    }
 
    private void preOrder(Node localRoot) {
        if(localRoot != null) {
            System.out.print(localRoot.data);
            preOrder(localRoot.leftChild);
            preOrder(localRoot.rightChild);
        }
    }
 
    private void inOrder(Node localRoot) {
        if(localRoot != null) {
            if(isOper(localRoot.data))System.out.print("(");
            inOrder(localRoot.leftChild);
            System.out.print(localRoot.data);
            inOrder(localRoot.rightChild);
            if(isOper(localRoot.data))System.out.print(")");
        }
    }
 
    private void postOrder(Node localRoot) {
        if(localRoot != null) {
            postOrder(localRoot.leftChild);
            postOrder(localRoot.rightChild);
            System.out.print(localRoot.data);
        }        
    }
 
    public void insLeft(Node newNode) {
        if(root == null) {
            root = newNode;
            activeNode = root;
        } else {        
            while(true) {
                if(activeNode.hasLeftChild) activeNode = activeNode.leftChild;
                else {
                    activeNode.leftChild = newNode;
                    newNode.parent = activeNode;
                    activeNode.hasLeftChild = true;
                    break;
                }    
            }
        }
    }
 
    public void insRight(Node newNode) {
        if(root == null) {
            root = newNode;
            activeNode = root;
        } else {  
            while(true) {
                if(activeNode.hasRightChild) activeNode = activeNode.rightChild;
                else {
                    activeNode.rightChild = newNode;
                    newNode.parent = activeNode;
                    activeNode.hasRightChild = true;
                    break;
                }    
            }
        }
    }
 
 
    public void insTop(Node newNode) {
        if(root == null) {
            root = newNode;
            activeNode = root;
        } else {  
            root.parent=newNode;
            newNode.leftChild = root;
            root = root.parent;
        }
    } 
}
 
class Monkey {
    private Tree someTree;
    private String postfx;
    UberStack us;
 
    public Monkey(String pfx) {
        postfx = pfx;
        doo();
    }
 
    public void see() {
        someTree.display();
    }
 
    private void doo() {
        us = new UberStack(postfx.length());
        String ch;
 
        int j;
 
        for(j=0; j < postfx.length(); j++) {
            ch = postfx.substring(j, (j+1));
 
 
            if(!isOper(ch)) {
                us.push(ch);
            } else {
                Node newNode = new Node(ch, true);
                System.out.println("Made node of: " + ch);
 
 
                Node newNodeRight;
                if (us.peek() instanceof String) newNodeRight = new Node((String)us.pop(),false);
                else newNodeRight = (Node)us.pop();
                System.out.println("Made node of: " + newNodeRight.data);
 
                Node newNodeLeft;
                if (us.peek() instanceof String) newNodeLeft = new Node((String)us.pop(),false);
                else newNodeLeft = (Node)us.pop();
                System.out.println("Made node of: " + newNodeLeft.data);
 
                newNode.rightChild = newNodeRight;
                newNode.leftChild = newNodeLeft;
 
                newNodeRight.parent = newNode;
                newNodeLeft.parent = newNode;
                us.push(newNode);
                System.out.println("Pushed node with " + newNode.data + " onto top of UberStack");
 
                if((j == (postfx.length()-1))) {
                    newNode.isRoot = true;
                    someTree = new Tree(newNode);
                    System.out.println("Monkey made a tree with node " + newNode.data);
                }
 
            }
        }
    }
 
 
    private boolean isOper(String s) {
        if(s.equals("0") || s.equals("1") || s.equals("2") || s.equals("3") || s.equals("4") || s.equals("5") || s.equals("6") || s.equals("7") || s.equals("8") || s.equals("9")) return false;
        else return true;
    }
}
 
/*
*   This software is part of the Insomnia 24/7 code library;
*    http://www.insomnia247.nl.nl/
*    This program is free software: you can redistribute it and/or modify
*    it under the terms of the GNU General Public License as published by
*    the Free Software Foundation, either version 3 of the License, or
*    (at your option) any later version.
*
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details.
*
*    You should have received a copy of the GNU General Public License
*    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
 
/**
 * This stack works FILO. (First In Last Out)
 * This stack can handle all Java objects. Different object types may be held in the same stack.
 * 
 * @author coolfire
 */
 
class UberStack <T>{
 
    private int pointer = 0;
    private T stack[];
 
    /**
     * If no stack size is passed to the constructor, a default stack size of 20 is used. 
     */
    public UberStack(){
        stack = (T[]) (new Object[20]);
    }
 
    /**
     * Create a new stack.
     * @param size of the stack.
     */
    public UberStack(int size){
        stack = (T[]) (new Object[size]);
    }
 
    /**
     * @return the element at the top of the stack.
     */
    public T pop() {
        if (pointer != 0) {
            pointer--;
            return stack[pointer];
        } else {
            return null;
        }
    }
 
    /**
     * @return the element at the top of the stack WHITHOUT removing it. 
     */
    public T peek() {
        if (pointer != 0) {
            return stack[pointer-1];
        } else {
            return null;
        }
    }
 
    /** 
     * Puts a new element on the stack.
     *  @param Object element to be added.
     */
    public void push(T var) {
        if(pointer <= stack.length) {
            stack[pointer] = var;
            pointer++;
        }
    }
 
    /** 
     * @return the position of the stack pointer.
     */
    public int getPointer() {
        return pointer;
    }
 
    /**
     * Resets the stack pointer.
     */
    public void empty() {
        pointer = 0;
    }
 
    public boolean isEmpty() {
        return(pointer == 0);
    }
 
}