Você irá utilizar uma árvore binária para armazenar uma expressão aritmética. Cada nó interno guarda um operador (+, -, * ou /) e cada folha guarda um número.
A árvore deve ser construída a partir de uma expressão escrita em notação pós-fixa (Reverse Polish Notation), na qual o operador vem depois dos seus dois operandos e não existem parênteses. Por exemplo, a expressão 5 9 + 2 * 3 + corresponde à árvore abaixo e produz o resultado 31:
+
/ \
* 3
/ \
+ 2
/ \
5 9
Lendo a árvore de baixo para cima: primeiro soma-se 5 + 9 = 14, depois multiplica-se 14 * 2 = 28 e por fim soma-se 28 + 3 = 31.
Depois de montada, você deve usar duas travessias diferentes na mesma árvore:
- uma travessia em ordem (esquerda, nó, direita) para reescrever a expressão na forma infixa, do jeito que estamos acostumados a ler;
- uma travessia em pós-ordem (esquerda, direita, nó) para calcular o resultado da expressão.
Repare que as duas funções são o mesmo percurso recursivo, mudando apenas o momento em que o nó atual é visitado.
Formato da entrada
Uma única linha contendo a expressão em notação pós-fixa, com os símbolos separados por um espaço. Os números são inteiros não negativos e os operadores são +, -, * e /.
Formato da saída
Duas linhas:
- A expressão reescrita na forma infixa, totalmente parentizada e sem espaços. Ou seja, para cada nó interno deve ser escrito um parêntese de abertura antes de descer à esquerda e um parêntese de fechamento depois de voltar da direita. As folhas são escritas como números inteiros.
- O resultado do cálculo, sempre inteiro e positivo, qualquer divisão será arredondada para baixo.