#include<stdio.h>
#include<ctype.h>
struct Stack
{
int tos;
char arr[200];
};
void push(struct Stack*,char);
char pop(struct Stack*);
int isoprnd(char);
int isempty(struct Stack);
int precedenc(char,char);//1st char–> operator inside stack
// 2nd char–> operator outside stack
void convert(char[],char[]);//1st char[]–> postfix
// 2nd char[]–> infix
void main()
{
int t;
scanf("%d",&t);
while(t>=1&&t<=10){
t–;
int n;
scanf("%d",&n);
if(n>=1&&n<=100){
char infix[100],postfix[100];
// printf(“Enter the infix expression:\n”);
scanf("%s",infix);
convert(postfix,infix);
printf("%s\n",postfix);
}
}
//exit(0);
}
void push(struct Stacks,char x)
{
if(s->tos==9)
{
// printf(“STACK OVERFLOW\n”);
return;
}
else
{
s->arr[++s->tos]=x;
}
}
char pop(struct Stacks)
{
if(s->tos==-1)
{
//printf(“STACK UNDERFLOW\n”);
return 0;
}
else
{
char ch;
ch=s->arr[s->tos–];//right value assign to left variable
return ch;
}
}
int isoprnd(char ch)
{
if(isalpha(ch)==0&&isdigit(ch)==0)
return 0;
return 1;
}
int isempty(struct Stack s)
{
return (s.tos==-1);
}
int precedenc(char op1,char op2 )//outside>inside operator return 1
{
if(op2==’(’||op2==’(’)
return 1;
else if(op1==’(’||op1==’(’)
return 1;//pop
else if(op1==’^’)
return 1;//push
else if(op2==’^’)
return 0;
else if(op2==’/’||op2==’’||op2==’%’)
return 0;
else if(op1==’/’||op1==’’||op1==’%’)
return 1;
else if(op1==’+’||op1==’-’)
return 0;
else
return 1;
}
void convert(char postfix[],char infix[])//a*{b+{c-d}/e}%g
{
struct Stack s;
int i,j=0;
char ch,temp,temp1;
int ans;
s.tos=-1;
for(i=0;infix[i]!=’\0’;i++)
{
ch = infix[i];
//printf("\nch1 = %c\n",ch);
if(isoprnd(ch)==1)
{
postfix[j]=ch;
// printf(“postfix1= %s\n”,postfix);
j++;
}
else if(ch==’)’)
{
temp=ch;
while(temp!=’(’)
{
temp= pop(&s);
printf(“temp= %c\n”,temp);
if(temp==’(’)
{
//temp = temp;
// printf(“temp= %c\n”,temp);
}
else
{
//temp= temp1;
postfix[j]=temp;
//printf(“postfix2= %s\n”,postfix);
j++;
}
}
//temp = pop(&s);
}
else
{
while(isempty(s)==0)
{
ans=precedenc(ch,s.arr[s.tos]);
// printf("ans = %d\n",ans);
//printf("\nch2 = %c",ch);
if(ans==1)
break;
postfix[j]=pop(&s);
//printf("postfix3= %s\n",postfix);
j++;
}
push(&s,ch);
//printf("stack = %c",s.arr[s.tos]);
}
}
while(isempty(s)==0)
{
postfix[j]=pop(&s);
j++;
}
postfix[j]='\0';
}