Usualmente, estamos acostumados a ver expressões matemáticas. Uma expressão matemática é um arranjo de termos que seguem o seguinte padrão
operando operador operando
sendo o operador algum dos operadores matemáticos, por exemplo,
+, -, * e /, e o
operando um número ou outro termo do mesmo formato. Por exemplo,
A+Be
(A+B)*Csão exemplos de expressões matemáticas.
Essa forma de organizar uma expressão matemática se chama notação infixa. Todavia, existe uma outra forma de representar, que é a notação pós-fixa, também chamada de polonesa reversa. Nessa notação, o operador vem depois dos operandos
operando operando operadorNos exemplos acima, teríamos
AB+e
AB+C*Embora à primeira vista pareça muito mais complicada, do ponto de vista computacional ela é muito mais fácil de ser avaliada que a notação infixa, pois, entre outros fatores,
Dispensa o uso de parêntesis
É uma forma mais sistemática, portanto simplifica a elaboração de procedimentos computacionais para avaliar a expressão.
Sua tarefa é, dada uma expressão matemática na notação infixa, convertê-la para a notação pós-fixa. Note que a expressão deve estar corretamente parentizada, caso não esteja, você deve exibir na saída padrão a mensagem “incorretamente parentizada”.
A entrada é composta por uma única linha, contendo uma expressão matemática na notação infixa com, no máximo, 500 caracteres. A expressão matemática contém apenas
Letras maiúsculas de A a Z representando os números,
Parênteses e
As operações de adição +, subtração -,
divisão /, multiplicação * e potenciação
^.
A expressão de entrada não contém espaços em branco.
A saída é composta de uma única linha contendo a expressão dada em notação pós-fixa.
A+BAB+(A+B)/CAB+C/A+B/CABC/+A+B*(C-D*(E-F)-G*H)-I*KABCDEF-*-GH*-*+IK*-A+B*(C-D*(E-F)-G*H-I*Kincorretamente parentizada