//Program to take an infix expression(ie. (x+y)*3^5) , to convert it into postfix and then to generate its
//expression tree from postfix expression

#include <bits/stdc++.h>
using namespace std;
stack<char> st;


int getPriority(char x) {
    if (x=='^') { return 3;}
    if(x=='*' or x=='/') { return 2; }
    if(x=='+' or x=='-') { return 1; }
    return 0; //ie. its an operand and not operator
}
vector<char> postfix;
class Node{
    public:
        char data;
        Node* left=NULL;
        Node* right = NULL;
        Node* next=NULL;
        Node(char value) {
            data = value;
            left=NULL;
            right=NULL;
            next=NULL;
        }
};


class Stack{

    public:
        Node* head=NULL;
        void push(Node* node) {
             if(head==NULL) { head = node; }
            node->next = head;
            head = node;
        }
        Node* top() {return head; }

        void pop() {
            Node* temp = head;
            head = head->next;
           // delete temp;
        }
};

class ExpTree{
    Stack st;

    public:
     Node* root=NULL;
        void createExpTree(vector<char> postfix) {
            for(auto x:postfix) {
                Node* temp = new Node(x);
                cout<<"New node: "<<temp->data<<endl;
                if(getPriority(temp->data)==0) {
                    cout<<"Pushing this node to stack"<<endl;
                    st.push(temp);
                } else {
                    Node* a = st.top();
                    cout<<"Right child of this node: "<<a->data<<endl;
                    st.pop();
                    Node* b = st.top();
                      cout<<"Left child of this node: "<<b->data<<endl;
                    st.pop();
                    temp->right = a;
                    temp->left = b;
                    cout<<"Now pushing to stack"<<endl;
                    st.push(temp);
                }

            }
            root = st.top();

            cout<<"root is "<<root->data<<endl;
           cout<<"left child of root is: "<<root->left->data<<endl;
            st.pop();
        }
        void inorder(Node* node) {
         //   cout<<node->data<<endl;
           //// cout<<node->right->data<<endl;
           // return;
           if(node==NULL) { return; }
            inorder(node->left);
            cout<<node->data<<"";
            inorder(node->right);
        }
         void postorder(Node* node) {
         //   cout<<node->data<<endl;
           //// cout<<node->right->data<<endl;
           // return;
           if(node==NULL) { return; }
            postorder(node->left);
             postorder(node->right);
            cout<<node->data<<"";

        }

        void preorder(Node *node) {
            if(node==NULL) { return;}
            cout<<node->data<<"";
            preorder(node->left);
            preorder(node->right);
        }
        void evaluatePostorder(string postfix) {
            float answer;
            stack<float> st;
            for(auto x:postfix) {
                cout<<"Char is : "<<x<<endl;
                if(getPriority(x)==0) {
                    float y= x-'0';
                    st.push(y);
                    cout<<"Pushed "<<y<<" into stack";
                } else  {
                    float a= st.top();

                    st.pop();
                    float  b = st.top();
                    cout<<"a: "<<a<<" b: "<<b<<endl;
                    st.pop();
                    float ans=0;
                    if(x=='+') { ans = a+b; }
                    if(x=='-') {ans = b-a; }
                    if(x=='*') { ans = a*b; }
                    if(x=='/') { ans = b/a; }
                    if(x=='^') { ans = pow(b,a); }
                    cout<<"After performing required operation: "<<ans<<endl;
                    st.push(ans);

                }
            }
            cout<<"ans is: "<<st.top() <<endl;
        }
};


/**
LOGIC---
1) If char c is '('- push it in the stack
2) If char c is ')'- keep on popping elements and inserting them into the postfix
expression till the time ( is encountered
3) If char c is of higher priority- just insert it in stack, otherwise pop and insert the elements into the postfix
expression till the time stack.top() is of lower priority
4) Finally, pop and insert all the remaining elements of stack into the postfix expression
 */
int main() {
string infix;
cin>>infix;
for(char x:infix) {
    if(x=='(') {
        st.push('(');
    }
    else if(x==')') {
        while(st.top()!='(') {
            postfix.push_back(st.top());
            st.pop();
        }
        st.pop();
    } else {
        //Is either a operand or operator
        //if operand just push it
        if(getPriority(x)==0) {
            postfix.push_back(x);
         } else {
            while(st.empty()==false && getPriority(st.top())>getPriority(x)) {
                   //Till the time we have higher priority elements in stack, just pop them and add them to postfix vector
                    postfix.push_back(st.top());
                    st.pop();
            }
            st.push(x);
         }

    }
}
//Now add all the remaining elements of stack into postfix expression
while(st.empty()==false) { postfix.push_back(st.top()); st.pop(); }

//Now print the result
string post="";
for(auto x:postfix) { cout<<x<<"";post+=x; }
//Now generate expression tree corresponding to it


ExpTree tree;

tree.createExpTree(postfix);
cout<<"Inorder: ";
tree.inorder(tree.root);
cout<<endl;
cout<<"Postorder: ";
tree.postorder(tree.root);
cout<<endl;
cout<<"Preorder: ";
tree.preorder(tree.root);
tree.evaluatePostorder(post);
}