Contato

• Jean Paulo Martins (jeanmartins utfpr edu br)
• Sala 105, Bloco S (UTFPR - Campus Pato Branco)

Conteúdo

• Introdução
  • Input Format
  • Motivação
  • Notação préfixa
  • Notação pósfixa
  • Utilidade
  • Conversão infixa/pósfixa
• Avaliação de expressão pósfixa

Introdução

Considere a soma de A mais B, numa expressão $A+B$. Neste exemplo, $+$ é um operador sendo aplicado aos operandos $A,B$. Este tipo de representação para a expressão de soma dos dois operandos é chamada infixa, pois o operador se posiciona entre os operandos.

Considerando-se o posicionamento do operador, no entando, existem duas representações alternativas: prefixa e posfixa.

• +AB (prefixa)
• AB+ (posfixa)

Input Format

Uma string contendo operandos (dígitos 0-9) e operandos (+,-,/,^,*) na forma posfixa. O operador exponenciação é indicado pelo caracter ‘^’, e pode ser implementado pela função:

#include <math.h>
// Exponenciação, é representada por AB^ (posfixa) => A^B (infixa) 
double r = pow(A, B);

A string pode conter espaços, os quais devem ser ignorados. As seguintes funções podem ser utilizadas para verificar o tipo de um caracter char c.

Motivação

Como poderá ser notado, notações prefixa e posfixa removem a ambiguidade de uma expressão, desta forma, parenteses não são mais necessários.

Notação préfixa

Para compreendermos a utilidade das notações prefixa e posfixa, consideremos as demais operações definidas como funções:

int add(int A, int B);
int mult(int A, int B);
int div(int A, int B);	

Dada uma expressão de exemplo, definida como:

Ela seria implementada em uma chamada da seguinte forma:

mult(add(A, div(B,C)),D);

O que utilizando a notação prefixa em termos de $+,*,/$, avalia-se a expressão acima, considerando-se as operações que serão efetuadas em primeiro lugar, ou seja, neste caso:

1. divisão $\rightarrow /BC$,
2. adição $\rightarrow +A/BC$,
3. multiplicação $\rightarrow *+A/BCD$.

Para comprovarmos se essa expressão se equivale à forma infixa, performe as operações assim que dois operandos estiverem disponíveis, iniciando a avaliação da esquerda para a direita.

Ao compararmos as duas representações para a expressão, o que é visivelmente notável?

Parenteses se tornam desnecessários! Como consequência, avaliar o resultado de uma expressão se torna muito mais simples. De fato pode ser implementado lendo-se a expressão apenas uma vez.

Notação pósfixa

Tanto na notação préfixa quanto na pósfixa, é importante lembrar que os operadores com precedência devem ser avaliados/convertidos primeiro, a não ser que uma possível parentização altere a ordem de precedência.

No exemplo anterior $(A+B/C) * D$, a multiplicação é efetuado somente ao final, devido à parentização. A ausência de parênteses, nesse exemplo, nos permitiria outras interpretações:

A forma pósfixa é a contrapartida da prefixa, em que os operadores são posicionados após os operandos. Retornando ao exemplo original $(A+B/C)*D$, temos que a divisão $B/C$ deve ser convertida em primeiro lugar:

Em seguida a adição entre parênteses

Por fim, a multiplicação

Utilidade

Dada a expressão em forma infixa, elabore um algoritmo que dê o resultado da expressão em apenas uma leitura da string:

Dada a expressão em forma pósfixa, elabore um algoritmo que dê o resultado da expressão em apenas uma leitura da string:

Conversão infixa/pósfixa

Avaliação de expressão pósfixa