#include<stdio.h>
//#include<conio.h>
#include<string.h>
#include<stdlib.h>
const int size=400;
char infix[400],postfix[400],stack[400];
int top=-1;
int precedence(char ch);
char pop();
char topelement();
void push(char ch);
int braces(char*);
int main()
{char ele,elem,t;
int i,prep,pre,popped,j=0,chk=0;
strcpy(postfix," ");
//clrscr();
//printf("enter the number of testcases\n");
scanf("%d",&t);
while(t>0)
{ // printf("%d\n",t);
j=0;
//printf("ASSUMPTION:the infix expression contains single letter variables\n\t and single digit constants only.\n\n");
//printf("enter infix expression...\n");
scanf("%s",&infix);
/*chk=braces(infix);
if(chk!=0)
{printf("unbalanced no. of braces \n extra");
printf((chk==1?"right braces":"left braces"));
getch();
exit(1);
} */
for(i=0;infix[i]!='\0';i++)
{if(infix[i]!='('&&infix[i]!=')'&&infix[i]!='^'&&infix[i]!='*'&&infix[i]!='/'&&infix[i]!='+'&&
infix[i]!='-')
postfix[j++]=infix[i];
else if(infix[i]=='(')
{elem=infix[i];
push(elem);
}
else if(infix[i]==')')
{while((popped=pop())!='(')
{postfix[j++]=popped;
}
}
else
{elem=infix[i];
pre=precedence(elem);
ele=topelement();
prep=precedence(ele);
if(pre>prep)
push(elem);
else{while(prep>=pre)
{if(ele=='#')
break;
popped=pop();
ele=topelement();
postfix[j++]=popped;
prep=precedence(ele);
}
push(elem);
}
}
}
while((popped=pop())!='#')
postfix[j++]=popped;
postfix[j]='\0';
//printf("\npostfix:");
printf("%s\n",postfix);
t--;
}
//getch();
return 0;
}
int precedence(char ch)
{switch(ch)
{case'^':return 5;
case'/':return 4;
case'*':return 4;
case'+':return 3;
case'-':return 3;
default:return 0;
}
}
char pop()
{char ret;
if(top!=-1)
{ret=stack[top];
top--;
return ret;
}
else return'#';
}
char topelement()
{char ch;
if(top!=-1)ch=stack[top];
else ch='#';
return ch;
}
void push(char ch)
{if(top!=size-1)
{top++;
stack[top]=ch;
}
}
/*int braces(char *s)
{int i,leftbr,rightbr;
leftbr=rightbr=0;
for(i=0;s[i];i++)
{if(s[i]=='(') leftbr++;
else if(s[i]==')') rightbr++;
}if(leftbr==rightbr) return 0;
else if(leftbr<rightbr) return 1;
else return -1;
} */
