Tarefa «Transformação de árvore de expressões usando enum e pattern matching»

Dada uma expressão aritmética representada como uma árvore binária. Cada nó da árvore é um número (folha) ou uma operação (adição, subtração, multiplicação, divisão) com dois filhos. É necessário implementar uma função que recebe essa árvore e retorna uma nova árvore, simplificada de acordo com as seguintes regras: se um nó for uma operação e ambos os filhos forem números, calcular o resultado e substituir o nó por um número; se um dos filhos for o número 0 e a operação for multiplicação, substituir o nó por 0; se um dos filhos for o número 0 e a operação for adição, substituir o nó pelo outro filho; se a operação for divisão e o divisor for o número 1, substituir o nó pelo dividendo; se a operação for subtração e ambos os filhos forem iguais, substituir o nó pelo número 0. Aplicar recursivamente enquanto possível. É garantido que todas as operações são inteiras, e a divisão é inteira com arredondamento para baixo. Dados de entrada: primeiro o número n — quantidade de nós. Em seguida, n linhas, cada uma no formato: tipo do nó ("num" ou "op"), para "num" — valor (inteiro), para "op" — símbolo da operação ('+', '-', '*', '/') e dois números inteiros — índices dos filhos esquerdo e direito (indexação 0). A raiz sempre tem índice 0. Saída: para cada nó após a simplificação, exibir seu tipo e valor/operação no mesmo formato (ordem dos nós como na árvore original, mesmo que o nó tenha se tornado um número, manter seu índice). Se o nó se tornar um número, exibir "num valor"; se permanecer como operação, exibir "op símbolo esquerdo_índice direito_índice" (índices dos filhos da árvore simplificada).

Exemplo 1

Exemplo 2

Exemplo 3

Exemplo 4