struct node
{
    object element;
    node *firstchild;
    node *nextsibling;
};

struct node
{
    int a;
    int b;//这些是结点包含的元素
    node *left;
    node *right;//这些是指向子树的指针
};

#include <bits/stdc++.h>

using namespace std;

struct node //定义一个结点
{
    char elem;
    node *left;
    node *right;
};

int main()
{
    stack<node *> temp_in; //构建一个栈用于存放指针(建树压栈)
    char char_in;          //构建一个临时变量用于读入(符号或数字)
    node node_arr[10000];  //构建一个数组用于存放树
    int pos = 0;           //构建的结点在数组中的位置(每构建一个结点时更新)
    while (true)
    {
        cin >> char_in;
        if (char_in == '!')
            break;

        if (char_in != '+' && char_in != '-' && char_in != '*' && char_in != '/') //读取非运算符(正常压栈)
        {
            node_arr[pos].elem = char_in; //把内容写入树
            temp_in.push(&node_arr[pos]); //将指针压入栈
        }
        else
        {
            node_arr[pos].elem = char_in;        //将运算符写入树
            node_arr[pos].right = temp_in.top(); //取为右儿子
            temp_in.pop();                       //弹出
            node_arr[pos].left = temp_in.top();  //取为左儿子
            temp_in.pop();                       //弹出
            //最后将这个树入栈
            temp_in.push(&node_arr[pos]);
        }
        pos++;
    }
    //此时树已经建立成功!!!接下来我们需要尝试以中序遍历和后序遍历来输出这个表达式
    node *print_node = temp_in.top(); //当前读出的根,先将栈顶的表达式读入
    temp_in.pop();//待会还要压进去
    while (true)
    {
        if ((*print_node).left == 0x0)
        {
            cout << (*print_node).elem;//若为最左叶,打印
            if (temp_in.empty())//打印完了要是栈顶为空,则跳出循环
            {
                break;
            }
            cout<<(*temp_in.top()).elem;//将根打印出来
            print_node = (*temp_in.top()).right;//修改读数为栈顶右儿子
            temp_in.pop();//将根从栈顶取出
        }
        else
        {
            temp_in.push(print_node);
            print_node = (*print_node).left;
        }
    } //找到最左侧元素

    return 0;
}