TRANSFORM THE EXPRESSION

PROBLEM STATEMENT


Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]
Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.
Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*



SOLUTION----



#include
#include

//using char array//
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
    char str[500];
    char postfix[500];
    char stack[500];
    scanf("%s",str);
    int k=strlen(str);
    int i,j=0,d,m=-1;
        for(i=0;i
        {
            d=str[i];
            if(d>=97&&d<=122)
            {
                postfix[j]=str[i];
                j=j+1;
            }
            else if(str[i]!=')')
            {
                m=m+1;
                stack[m]=str[i];
           
            }
            else
            {
                while(stack[m]!='(')
                {
                    postfix[j]=stack[m];
                    j=j+1;
                    m=m-1;
                }
                m=m-1;
            }
        }
        for(i=0;i
            printf("%c",postfix[i]);
        printf("\n");
    }
    return 0;
}