#include
#include<ctype.h>
#include<string.h>
using namespace std;
class stack
{
typedef struct node
{
int data;
node *next;
}node;
node *top;
public:
stack()
{
top=NULL;
}
int empty();
void push(int );
int pop();
};
int stack::empty()
{
if(top==NULL)
return 1;
return 0;
}
void stack::push(int x)
{
node *p;
p=new node;
p->data=x;
p->next=top;
top=p;
}
int stack::pop()
{
int x;
node *p;
p=top;
x=p->data;
top=top->next;
delete p;
return x;
}
int Priority(char x)
{
static int flag=3;
if(x==’*’ || x==’/’)
return 2;
if(x==’+’ || x==’-’)
return 1;
if(x==’^’)
return flag++;
else
return 0;
}
void coninfpos(char String[],char PostExpression[30])
{
char opr;
int I=0,J=0,count;
stack s;
for(I=0;I<strlen(String);I++ )
{
if(isalnum(String[I]))
PostExpression[J++]=String[I];
else
{
if(String[I]==')')
{
opr=s.pop();
while(opr!='(')
{
PostExpression[J++]=opr;
opr=s.pop();
}
}
else
{
if(String[I]=='(')
s.push(String[I]);
else
{
while(!s.empty())
{
opr=s.pop();
if(opr!='('&& Priority(opr)>=Priority(String[I]))
{
PostExpression[J++]=opr;
}
else
{
s.push(opr);
break;
}
}
s.push(String[I]);
}
}
}
}
while(!s.empty())
{
PostExpression[J++]=s.pop();
}
PostExpression[J]=’\0’;
}
int main()
{
stack s;
int ch,p,n,i;
char postfix[30][30],infix[30][30];
cin>>n;
for(i=0;i<n;i++)
{
cin>>infix[i];
coninfpos(infix[i],postfix[i]);
}
for(i=0;i<n;i++)
cout<<"\n"<<postfix[i];
return 0;
}
