#include <iostream>#include <sstream>#include<algorithm>#include<memory.h>#include<stdio.h>#include<queue>#include<stack>using namespace std;#define null NULLconst int N = 10000;struct Node{    Node* p;    Node* r;    Node* l;    char key;    Node()    {        p = null;        r = null;        l = null;        key = ‘0‘;    }};void print(queue<Node*> q, string& str){    Node* node = null;    while (!q.empty())    {        node = q.front();        q.pop();        str += node->key;        if (node->r != null)            q.push(node->r);        if (node->l != null)            q.push(node->l);    }}int main(){    freopen("d:\\1.txt", "r", stdin);    int t;    cin >> t;    while (t--)    {        Node* root;        string str;        cin >> str;        stack<Node*> s;        int l = str.length();        for (int i = 0; i < l; i++)        {            char c = str.at(i);            Node* node = new Node();            node->key = c;            if (‘A‘ <= c && c <= ‘Z‘)            {                Node* l = s.top();                s.pop();                Node* r = s.top();                s.pop();                node->l = l;                node->r = r;            }            s.push(node);        }        root = s.top();        s.pop();        queue<Node*> q;        q.push(root);        string& str1 = str;        str="";        print(q, str1);        reverse(str.begin(), str.end());        cout << str << endl;    }    return 0;}