import java.util.*;

class Node {
    protected char data;
    protected Node next = null;

    public Node() {
    }

    public Node(char data, Node next) {
        this.data = data;
        this.next = next;
    }

    void setData(char data) {
        this.data = data;
    }

    void setLink(Node link) {
        this.next = link;
    }

    Node getLink() {
        return next;
    }

    char getData() {
        return data;
    }
}

class Stack {
    protected Node top = null;

    public void push(char val) {
        // Currently we have set no limits to pushing elements
        Node nptr = new Node(val, top);
        top = nptr;
    }

    public char pop() throws Exception {
        if (isEmpty()) {
            throw new Exception("Stack Underflow");
        } else {
            char val = top.getData();
            top = top.getLink();
            return val;
        }
    }

    public boolean isEmpty() {
        return top == null;
    }
}

class Convert {
    private char[] BEDMAS = { '-', '+', '*', '/', '^' };
    private int[] BEDMAS_PREC = { 0, 0, 1, 1, 2 };
    // Not Exactly follwing the BEADMAS rule here, but going with operator
    // precedence rules
    // To use BEDMAS to convert don't use BEDMAS_PREC and directly get the index
    // from BEDMAS
    private char[] data;

    public Convert(String str) {
        data = str.toCharArray();
    }

    public String getPostfix() throws Exception {
        String res = "";
        Stack stk = new Stack();
        int prv = -1; // storing previous precedence for comparision
        boolean first_op = true;
        boolean bracket = false;
        for (int x = 0; x < data.length; x++) {
            char ch = data[x];
            int prec = isBeadmasOperator(ch);
            if (prec == -1) {
                if (ch == '(') {
                    first_op = true;
                    bracket = true;
                    stk.push(ch);
                } else if (ch == ')')
                    try {
                        for (char op = stk.pop(); op != '('; op = stk.pop())
                            res += op;
                        bracket = false;
                    } catch (Exception e) {
                        throw new Exception("Invalid Expression");
                    }
                else
                    res += ch;
            } else if (prec != -1) { // BEDMAS operaator detected
                if (prv >= prec && !first_op)
                    while (!stk.isEmpty()) {
                        char vl = stk.pop();
                        if (vl == '(' && bracket) {
                            stk.push(vl);
                            break;
                        }
                        res += vl;
                    }
                stk.push(ch);
                prv = prec;
                first_op = false;
            }
        }
        while (!stk.isEmpty()) {
            char vl = stk.pop();
            if (vl == '(' && bracket)
                throw new Exception("Invalid Expression");
            res += vl;
        }
        return res;

    }

    private int isBeadmasOperator(char ch) {
        for (int x = 0; x < BEDMAS.length; x++)
            if (BEDMAS[x] == ch)
                return BEDMAS_PREC[x];
        return -1;
    }
}

public class InfixToPostfix {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter Infix Expression:");
        String val = sc.nextLine();
        Convert obj = new Convert(val);
        try {
            System.out.printf("Converted Postfix Expression:\n%s\n", obj.getPostfix());
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        sc.close();
    }
}