2

xyPzwIM

abcABdefgCDEF

sample output

wzyxIPM

gfCecbDdAaEBF

    *

 +     -

x y  z  w

      F

   B    E

  a A  d D

   b c  e C

         f g

#include<cstdio>

#include<cstring>

#include<iostream>

#include<string>

#include<algorithm>

#include<stack>

#include<queue>

using namespace std;

struct node

{

        node(node* l, node* r, char ch): left(l), right(r), c(ch) {}

        node* left;

        node* right;

        char c;

}*root;

void build_tree(string & str)

{

        stack<node*> st;

        for(int i=0;i<str.length();i++)

        {

                if(islower(str[i]))

                {

                        st.push(new node(0, 0, str[i]));

                }

                else

                {

                        node* right=st.top(); st.pop();

                        node* left=st.top(); st.pop();

                        st.push(new node(left, right, str[i]));

                }

        }

        root=st.top();

}

vector<char> ans;

void bfs()

{

        ans.clear();

        queue<node*> q;

        q.push(root);

        while(!q.empty())

        {

                node* nd=q.front();q.pop();

                ans.push_back(nd->c);

                if(nd->left)

                {

                        q.push(nd->left);

                }

                if(nd->right)

                {

                        q.push(nd->right);

                }

        }

}

void delete_tree(node* nd)

{

        if(nd)

        {

                delete_tree(nd->left);

                delete_tree(nd->right);

                delete nd;

        }

}

void output()

{

        for(int i=ans.size()-1;i>=0;i--)

                cout<<ans[i];

        cout<<endl;

}

int main()

{

        int n;

        cin>>n;

        string str;

        while(n--)

        {

                cin>>str;

                build_tree(str);

                bfs();

                delete_tree(root);

                output();

        }

    return 0;

}