Universidade Federal de Minas Gerais

Instituto de Ciências Exatas

Departamento de Ciência da Computação




Estruturas de Dados

Primeiro Trabalho Prático


Comentários Gerais

1.
Comece a fazer este trabalho logo, enquanto o problema está fresco na memória e o prazo para terminá-lo está tão longe quanto jamais poderá estar.
2.
Este trabalho exercita conceitos e estruturas de dados apresentados nos capítulos 1 e 2 do livro Ziviani (1993).
3.
Vão valer pontos clareza, indentação e comentários no programa.


O que deve ser apresentado:

1.
Listagem do programa em Pascal.
2.
Listagem dos testes executados.
3.
Descrição sucinta (por exemplo, desenho), das estruturas de dados e as decisões tomadas relativas aos casos e detalhes de especificação que porventura estejam omissos no enunciado.
4.
Estudo da complexidade do tempo de execução dos procedimentos implementados e do programa como um todo (notação O).

[Zivi93] Ziviani, Nivio, Projeto de Algoritmos Com Implementações em Pascal e C, Editora Pioneira, 1993.

Pilhas, Avaliações de Expressões, Notação Pós-Fixada

Quando a idéia de linguagens de programação de alto nível foi concebida, seus implementadores defrontaram-se com vários obstáculos técnicos. Um deles foi a questão de, durante a compilação, gerar instruções de máquina para avaliar corretamente uma expressão aritmética genérica. Uma expressão como

A/B*C+D*E-A*C

pode ter significados diferentes, se não forem definidas prioridades dos operandos, regras de avaliação ou uso de parêntesis. Aparentemente, a tarefa de gerar as instruções de máquina corretas na ordem correta não é trivial, mas existem soluções simples e elegantes. Na verdade, a solução é considerada tão simples que este aspecto de construção de compiladores é visto como um dos mais triviais.

Uma expressão é composta por operandos e operadores. A expressão acima contem 5 operandos: A,B,C,D e E; e os operadores +,-,* e /. O primeiro problema que deve ser resolvido para se entender o significado de uma expressão é decidir em qual ordem as operações são executadas. Isto significa que todas as linguagens devem definir alguma ordem. Para fixar a ordem de avaliação, as linguagens permitem o uso de vários níveis de parêntesis e definem uma prioridade para cada operador. Assim, operadores com prioridades mais alta são avaliados primeiro. Um possível assinalamento de prioridades é:

Operador Prioridade
*, / 2
+, - 1

Ainda resta o problema de uma expressão com dois operadores adjacentes de mesma prioridade (p.ex., A/B*C). Neste caso, uma regra adicional, dizendo, por exemplo, que a avaliação deve ser feita da esquerda para a direita resolve a ambiguidade.

Definidas as prioridades e regras de avaliação, sabemos que a expressão

A/B*C+D*E-A*C

será avaliada como

(((A/B)*C)+(D*E))-(A*C)

Como um compilador aceita expressões como essas e produz código de máquina correto? A resposta é reorganizar a expressão original numa forma que é conhecida como notação pós-fixada, ou notação polonesa (em homenagem ao matemático polonês Jan Lukasiewicz, que inventou a notação). Expressões escritas na forma convencional estão em notação infixada, porque os operadores entre os operandos. Na notação pós-fixada, cada operador aparece após seus operandos. Por exemplo,

Infixada A*B/C
Pós-fixada: AB*C/
   
Infixada A/B*C+D*E-A*C
Pós-fixada: AB/C*DE*+AC*-
   
Infixada (A/B)*(C+D)*(E-A)*C
Pós-fixada: AB/CD+*EA-*C*
   

A notação pós-fixada tem várias vantagens sobre a convencional:

Para se avaliar uma expressão na notação pós-fixada, basta dar uma passada na expressão da esquerda para a direita, procedendo-se assim:

Ao final, o resultado da expressão estará no topo da pilha. Usando o Pascal como notação: 

procedure Avalia(var E:Expressao; var S:Pilha);
var X: TipoSimbolo;
begin
  x := PrimeiroSimbolo(E);
  while (Not FimdeExpressao(x)) do begin
    if (Operando(x))
      then Empilha(x,S)
    else 
      RemovaOperandosExecutaOperacao(E);
    x := ProximoSimbolo(E);
  end
end;

Agora que já sabemos como avaliar expressões na notação pós-fixada, devemos resolver o problema de traduzir uma expressão na notação infixada para a pós-fixada. Este é o problema que você deverá resolver neste trabalho. Portanto, implemente um procedimento Pascal que faça a transformação: 

procedure InfixParaPosfix(var infix:Expressao;
                          var posfix:Expressao);

Desafio

Serão distribuídos 2 pontos extras para quem generalizar a solução e também tratar o operador exponenciação (^), que terá prioridade 3, ou seja, maior que todos os demais.

Infixada A*B^C
Pós-fixada: ABC^*

Dicas e simplificações:

Escreva um programa Pascal para testar a sua implementação. Seu programa deverá:

1.
ler expressões na forma infixada;
2.
transformá-las para a forma pós-fixada;
3.
aceitar valores para as variáveis;
4.
avaliá-las na forma pós-fixada.

O que deve ser apresentado:

É obrigatório o uso de alocação dinâmica de memória para implementar as várias estruturas de dados.

Distribuição dos pontos:

A entrega do trabalho prático deve seguir as instruções usuais.


Wagner Meira Jr
11/20/2000