Avaliando uma expressão pós-fixa

Definição básica para infixa, pós-fixa e pré-fixa e como interpretar através do uso de uma pilha na aplicação, para isso considere que a representação mais comum de uma expressão é a infixa, utilizando o operador + e os operando X e Y, temos a soma no formato:

X + Y

               Ainda existem duas outras notações para representar a soma de X e Y com o símbolo +, sendo:

+ X Y      pré-fixa

X Y +      pós-fixa

               Fica simples através desta apresentação que os prefixos “pré”, “pós” e “in” indicam a posição dos operando em relação ao operador. Apesar da dificuldade de se avaliar esse tipo de expressão em um primeiro momento, lembre que + X Y, assemelha-se a analise léxica de uma função como add(X,Y).

               Outro caso que devemos considerar é o da precedência de um operador, aonde iremos sempre interpretar X + Y * Z como X + (Y * Z), ou seja, para reescrever esta expressão para notação pós-fixa , obedece-se as mesma regras de precedência.

X + Y * Z	Converte multiplicação
X + YZ*	Converte adição
XYZ *+	Pós-fixa

               Com o uso de parênteses a precedência tem aguardar a resolução dentro dos mesmos.

(X + Y) * Z	Converte adição
(XY+) * Z	Converte multiplicação
(XY+)Z*	Parentes desnecessários
XY+Z*	Pós-fixa

               Para a linguagem C existem 4 operações binárias nativas, adição subtração, multiplicação e divisão, através do símbolos +, /, * e -. Uma quinta operação de exponenciação que deverá tornar o símbolo $ em operador. A tabela de precedência a seguir deverá ser ignorada apenas quando ocorrer o uso de parênteses, entretanto uma das vantagens da forma pós-fixa é que não existem parênteses para determinar a prioridade da operação uma vez que a ordem dos operadores na expressão determina a verdadeira sequencia de operações.

PRECEDENCIA
1	Exponenciação	$
2	multiplicação/divisão	*, /
3	adição/subtração	+, -

A forma pós-fixa que posiciona operador na precedência desejada e torna desnecessário o uso do parênteses deveria torna a expressão mais simples para se resolver, não fosse o fato de que ao se costumar com o formato infixa, fica-se difícil avaliar, entretanto através de um algoritmo de pilha para avaliar uma expressão pós-fixa, a tarefa será simples, lembre que a cada operador, refere-se a dois operando anteriores, empilhando os operando até encontrar o operador, desempilha e efetua a ação indicada, voltando a empilhar o resultado, uma simulação da expressão 8 3 4 + - 6 4 2 / + * 2 $ 5 + mostrada abaixo exemplifica a solução.

Simb.	Op1	Op2	Resp.	Pilha
8				8
3				8, 3
4				8, 3, 4
+	3	4	7	8, 7
-	8	7	1	1
6	“	“	“	1, 6
4	“	“	“	1, 6, 4
2	“	“	“	1, 6, 4, 2
/	4	2	2	1, 6, 2
+	6	2	8	1, 8
*	1	8	8	8
2	“	“	“	8, 2
$	8	2	64	64
5	“	“	“	64, 5
+	64	5	69	69

               Interessante reparar que neste caso o tamanho usado pela pilha é inferior ao numero total de operando, o máximo teórico de oito operandos nunca é alcançado devido ao fato de que a cada operador tratado é removido o operando.

Todo o código em linguagem C para avaliar uma expressão pós-fixa utilizando pilha está incluído na próxima postagem “Rotinas para pós-fixa”. O tema sobre analise de expressões continua em “Avaliando uma expressão infixa” e sua programação.