Índice >
Pilha >
Aplicação de Pilha: Notação Polonesa
Instituto de Ciências Matemáticas de São Carlos
Departamento de Computação e Estatística
SCE182 - Algoritmos e Estruturas de Dados 1
Profs. Resp.: Graça Pimentel e Maria Cristina
Aplicação de Pilha: Notação Polonesa
Uma representação para expressões aritméticas
que seja conveniente do ponto de vista computacional é assunto de
interesse, por exemplo, na área de compiladores.
A notação tradicional é ambígua e, portanto,
obriga o pré-estabelecimento de regras de prioridade.
Isso torna a tarefa computacional menos simples. Outras notacões
são apresentadas a seguir, considerendo-se apenas operações
binárias (com dois operandos):
-
Notação completamente Parentizada: acrescenta-se sempre
um parênteses a cada par de operandos e seu operador.
Exemplo:
tradicional: A * B - C / D
parentizada: ((A*B)-(C/D))
-
Notação Polonesa: os operandos aparecem imediatamente
antes dos operandos. Esta notação especifica quais operadores,
e em que ordem, devem ser calculados. Por esse motivo dispensa o uso de
parênteses, sem ambiguidades.
Exemplo:
tradicional: A * B - C / D
polonesa: - * A B / C D
-
Notação Polonesa Reversa (ou posfix): é como
a polonesa na qual os operandos aparecem após os operandos.
Exemplo:
tradicional: A * B - C / D
polonesa reversa: A B * C D / -
Avaliação de expressões aritméticas
programa fonte - notação infix: x := A / B + D * E - A
objetivo- notação posfix: x := A B / D E * + A -
Um algoritmo para a avaliação de Expressões
PosFix:
-
empilha operandos até encontrar um operador
-
retira o número de operandos; calcula e empilha o valor resultante
-
até que chegue ao final da expressão
Exemplo: A B / D E * + A -
function valor ( E: expressão): TipoValor;
var x : TipoOperador;
begin
topo := 0;
while not acabou(E) do
begin
x := proxsimb(E);
if x é operando then push(x,pilha)
else
begin
remove o número de operandos (dois) para o operador x da pilha;
calcule o resultado da operação;
empilhe resultado;
end;
valor := P[topo];
end;
Exemplo de Utilização
Pilha