beecrowd | 1077

Infixa para Posfixa

Por Neilor Tonin, URI Brasil

Timelimit: 1

O Professor solicitou que você escreva um programa que converta uma expressão na forma infixa (como usualmente conhecemos) para uma expressão na forma posfixa. Como você sabe, os termos in (no meio) e pos (depois) se referem à posição dos operadores. O programa terá que lidar somente com operadores binários +,-,*,/,^, parênteses, letras e números. Um exemplo seria uma expressão como:
(A*B+2*C^3)/2*A. O programa deve converter esta expressão (infixa) para a expressão posfixa: AB*2C3^*+2/A*
 

Entrada

A primeira linha da entrada contém um valor inteiro N (N < 1000), que indica o número de casos de teste. Cada caso de teste a seguir é uma expressão válida na forma infixa, com até 300 caracteres.

Saída

Para cada caso, apresente a expressão convertida para a forma posfixa.

Exemplo de Entrada Exemplo de Saída

3
A*2
(A*2+c-d)/2
(2*4/a^b)/(2*c)

A2*
A2*c+d-2/
24*ab^/2c*/