Bino está estudando MC202 e decidiu criar sua própria calculadora de expressões aritméticas. A sua calculadora é muito simples e permite apenas definir novas expressões envolvendo valores numérico inteiros ou variáveis. Além disso, apenas operações binárias são suportadas! A vantagem, disse ele, é que é muito fácil representar uma expressão desse jeito: basta usar uma árvore binária.

1. Otimizando expressões

A primeira versão desenvolvida por Bino não decolou porque a as operações eram realizadas muito lentamente. Assim, ele gostaria de otimizar as expressões aritméticas informadas pelo usuário. Por exemplo, ao invés de calcular uma expressão diretamente informada pelo usuário, como ( ( 4 * ( 5 - 2 ) ) - ( x + y ) ), ele pode avaliar uma expressão otimizada equivalente ( 12 - ( x + y ) ). Para ilustrar, veja o exemplo a seguir para a expressão ( x * ( 1 + 2 ) ).

A árvore binária da esquerda corresponde à árvore construída a partir da expressão dada como entrada; enquanto que a árvore binária da direita corresponde à árvore obtida após a otimização da expressão.

Nessa primeira versão, Bino irá ignorar as propriedade de associatividade da soma e produto, assim não é possível otimizar a expressão ( 1 + ( 2 + x ) ). Além disso, Bino só irá considerar números pequenos positivos e todas as operações serão calculadas com módulo 256. Por exemplo, temos $255 + 1 = 0$, ainda $5 \times 100 = 245$ ou mesmo $5-10 = 251$.

Escreva um programa otimizar que receba como entrada uma expressão aritmética e devolva uma expressão otimizada equivalente.

Entrada

Uma expressão aritmética inteira. Os operadores aritméticos utilizados são de soma, subtração, multiplicação e divisão inteira. As expressões conterão números negativos e positivos e cada variável é uma sequência com até 10 letras. Cada operação está rodeada por parênteses, mesmo quando não houver ambiguidade. Os parênteses, operadores e operandos estão todos separados por espaço.

( ( 1 + 4 ) * ( 5 + ( x + 2 ) ) )

Saída

A saída do seu programa deverá conter a expressão otimizada.

( 5 * ( 5 + ( x + 2 ) ) )

2. Avaliando expressões

Uma vez implementada a otimização de uma expressão isolada, você deve construir a calculadora completa. Escreva um programa calculadora que receba uma sequência de atribuições de variáveis e calcule o valor de uma dada variável.

Entrada

A entrada começa com uma sequência de linhas representando atribuições, cada uma no formato <variavel> = <expressão>. A última linha contém uma variável cujo o valor deve ser computado. Toda linha termina com um ponto-e-vírgula.

a = ( ( 5 - ( 2 + 3 ) ) - ( 4 - 6 ) ) ;
b = ( ( 6 - ( y * a ) ) + ( 6 - 2 ) ) ;
c = ( ( ( 2 - a ) - 5 ) + ( 6 + 3 ) ) ;
d = ( ( a + y ) - 3 ) ;
e = ( ( ( g - c ) - c ) + ( 2 + 5 ) ) ;
g = ( ( a - b ) - a ) ;
y = ( ( 1 + 3 ) + ( ( 1 - 5 ) + 2 ) ) ;
z = ( 3 - ( 5 - b ) ) ;
e ;

Saída

O valor da variável. Suponha que é possível avaliar completamente o valor dessa variável.

249

Dicas

Por definição, uma expressão é uma estrutura recursiva. Por exemplo, uma expressão parentisada é definida como <expressão> := ( <expressão> <operador> <expressão> ). Assim, para ler a entrada, considere construir uma função recursiva que leia uma sequência de elementos (tokens) e devolva uma árvore binária.

Como cada elemento da expressão está separado por espaço em branco, você pode ler no formato string, descobrir o tipo de cada elemento e converter ao formato adequado, como em:

scanf(" %s", buffer);

if (buffer[0] == '(') { // início de alguma subexpressão
    ...
} else if (buffer[0] >= '0' && buffer[0] <= '9') {
    valor = atoi(buffer);
    ...
} else if (...) {
    ...
}

Observe que cada linha da entrada da segunda questão começa com o nome de uma variável. Para saber se estamos lendo uma atribuição ou a última linha, basta ler o nome da variável e verificar o valor da próxima string lida, se um igual ou um ponto-e-vírgula.

Note que, ao contrário de Python, a operação a % b em C só está bem definida para números positivos a e b; para números negativos, o resultado da operação pode não ser o que você espera.

Critérios

1. É obrigatório representar uma expressão como uma árvore binaria.

2. É obrigatório armazenar o conjunto de atribuições associando uma variável a uma expressão utilizando uma árvore binária de busca balanceada.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

← Anterior Voltar Próximo →