MAC0122 - Lista 3 - Pilhas

1. Considere uma sequência de elementos entre {, }, [, ], ( e ). Dizemos que uma tal sequência é bem formada se
   • ela é vazia ou
   • ela é {S}R ou [S]R ou (S)R, onde S e R são sequências bem formadas.
   Escreva uma função que recebe como parâmetros um inteiro n e string com uma sequência de n elementos entre {, }, [, ], ( e ), e devolve 1 se tal sequência é bem formada, 0 caso contrário.

   Exemplos: {[()[]]()}({}) é bem formada, enquanto que {[}], {()}[(), (}{) e {()}] não são bem formadas.

2. Reescreva a sua função acima para que ela use a biblioteca "stack.h" vista em aula.

3. Converta as seguintes expressões para notação posfixa usando o algoritmo visto em aula. Mostre em cada passo o conteúdo da pilha de operadores.
   1. A - B / C * (D - (E + F)) / G + H * I
   2. ( A + B ) / C * D - E / (F * G)

4. Considere expressões que, além dos operadores binários +, -, * e /, têm também o operador binário ^, de exponenciação. O operador ^ tem precedência maior que os operadores acima. Ademais, o operador de exponenciação, diferente dos demais, tem prioridade da direita para a esquerda. Ou seja, a expressão 2^3^2 = 2^(3^2) = 2^9 = 512, e não 64. Adapte o algoritmo visto em aula para aceitar também expressões com ^. Depois simule o seu algoritmo com a seguinte expressão:
   1. A ^ B ^ C + D
   2. A ^ B + C ^ D
   3. A ^ B + C * D ^ E ^ F - G / H ^ (I + J)

5. Escreva uma implementação da biblioteca "stack.h" vista em aula usando lista encadeada sem cabeça.

6. Considere dada uma função float valor(char ch); que recebe uma letra e devolve o valor da variável dada pela letra. Escreva uma função
   float calcula(char *posfixa); que recebe uma expressão posfixa como as calculadas pelo programa que vimos em aula e devolve o valor da expressão. Utilize a função acima para saber o valor das variáveis da expressão. Note que uma pilha vai o ajudar nesse processo. Defina o tipo Item adequadamente e escreva a sua função usando a biblioteca "stack.h" vista em aula.