Na aula de hoje vamos ver mais uma aplicação prática para estruturas de dados dinâmicas do tipo pilha. Vamos aprender como resolver uma expressão em notação pós-fixa (notação polonesa reversa).
A notação pós-fixa ou notação polonesa reversa é uma forma diferente de escrever uma expressão matemática de tal forma que não há dúvida sobre qual operação deve ser realizada primeiro. Nesta notação os números sempre ficam à esquerda e a operação a ser realizada a direita. Veja a seguir alguns exemplos de expressões escritas na notação infixa e sua equivalente em notação pós-fixa.
Notação Infixa Notação Pós-fixa
( 51 + 13 * 12 ) 51 13 12 * +
( 5 * ( 3 + 2 ) / 4 - 6 ) 5 3 2 + * 4 / 6 -
( 5 + 3 + 2 * 4 - 6 * 7 * 1 ) 5 3 + 2 4 * + 6 7 * 1 * -
( 5 * ( 3 + ( 2 * ( 4 + ( 6 * ( 7 + 1 )))))) 5 3 2 4 6 7 1 + * + * + *
O objetivo neste exercício é resolver uma expressão digitada a partir do teclado em notação pós-fixa, então, vamos entender como resolver uma expressão desse tipo no papel para depois programar o computador. Vamos avaliar o segundo exemplo: 5 3 2 + * 4 / 6 –
Para resolver esta equação, vamos procurar pela primeira operação matemática, da esquerda para a direita, e resolvê-la, lembrando que a operação está sempre à direita dos números. Assim, a primeira operação a ser a realizada é a soma de 3 e 2. Ao realizar esta soma, a expressão resultando é: 5 5 * 4 / 6 –
Agora, a próxima operação a ser realizada é a multiplicação de 5 e 5 chegando a: 25 4 / 6 –
A seguir temos a resolução completa da expressão: 5 3 2 + * 4 / 6 –
5 3 2 + * 4 / 6 –
5 5 * 4 / 6 –
25 4 / 6 –
6.25 6 –
0.25
Tente resolver os outros três exemplos, isso vai ajudar a fixar a ideia.
Como resolver uma expressão em notação pós-fixa
A princípio pode parecer complicado resolver este problema, mas não é. Com uma estrutura de dados do tipo pilha a solução fica bastante simples.
Como já foi mencionado, os números estão sempre à esquerda da operação. Assim, podemos percorrer a string digitada (estamos assumindo que a expressão foi digitada corretamente com um espaço entre cada caracter) e avaliar cada caracter diferente de espaço.
Se for um número, basta empilhar este número (precisamos primeiro convertê-lo para número). Se for uma operação matemática, precisamos desempilhar dois números da pilha, realizar a operação matemática e empilhar novamente o resultado. Ao final a pilha terá um único valor que é o resultado da expressão.
Vamos simular estes passos para a segunda expressão: 5 3 2 + * 4 / 6 –
1) empilha o 5
2) empilha o 3
3) empilha o 2
4) desempilha dois valores (3 e 2), realiza a operação e insere na pilha o resultado. A pilha está assim: 5, 5
5) desempilha dois valores (5 e 5), realiza a operação e empilha o resultado. A pilha está assim: 25
6) empilha o 4
7) desempilha dois valores (25 e 4), realiza a operação e empilha o resultado. A pilha está assim: 6.25
8) empilha o 6
9) desempilha dois valores (6.25, 6), realiza a operação e empilha o resultado. A pilha está assim: 0.25
10) como a string terminou, o único valor da pilha é o resultado da expressão
Agora, vamos escrever este algoritmo usando a linguagem C.
Como estamos assumindo que cada elemento da expressão está separado por um espaço, podemos utilizar a função strtok para dividir nossa string em tokens. Se você não conhece essa função é porque pulou a aula 141.
Agora que conseguimos acessar diretamente cada caracter da expressão, precisamos verificar se é ou não uma operação matemática. Se não for uma operação matemática, significa que é um número, então vamos convertê-lo para número com a função strtol e inserir na pilha. Contudo, se for uma operação matemática, então desempilhamos dois valores , realizamos a operação e empilhamos novamente o resultado.
Para o nosso exemplo da segunda expressão, observe que 3 – 2 é diferente de 2 – 3. Ou seja, precisamos realizar a operação do segundo valor desempilhado com o primeiro, senão teremos valores incorretos. Lembre-se que o 2 está no topo da pilha, foi o última valor empilhado, logo será o primeiro valor desempilhado.
pt = strtok(x, " ");
while(pt){
if(pt[0] == '+' || pt[0] == '-' || pt[0] == '/' || pt[0] == '*'){
n1 = desempilhar(&pilha);
n2 = desempilhar(&pilha);
num = operacao(n2->valor, n1->valor, pt[0]);
pilha = empilhar(pilha, num);
free(n1);
free(n2);
}
else{
num = strtol(pt, NULL, 10);
pilha = empilhar(pilha, num);
}
pt = strtok(NULL, " ");
}
A seguir temos a função completa para resolver uma expressão em notação pós-fixa.
float resolver_expressao(char x[]){
char *pt;
float num;
No *n1, *n2, *pilha = NULL;
pt = strtok(x, " ");
while(pt){
if(pt[0] == '+' || pt[0] == '-' || pt[0] == '/' || pt[0] == '*'){
n1 = desempilhar(&pilha);
n2 = desempilhar(&pilha);
num = operacao(n2->valor, n1->valor, pt[0]);
pilha = empilhar(pilha, num);
free(n1);
free(n2);
}
else{
num = strtol(pt, NULL, 10);
pilha = empilhar(pilha, num);
}
pt = strtok(NULL, " ");
}
n1 = desempilhar(&pilha);
num = n1->valor;
free(n1);
return num;
}
Observe que esta função não faz propriamente as operações, ela gerencia a estrutura pilha, empilhando e desempilhando. Para realizar as operações matemáticas temos outra função que recebe dois valores e uma operação a ser realizada, faz a operação e retorna o valor, como apresentado a seguir.
float operacao(float a, float b, char x){
switch(x){
case '+':
return a + b;
break;
case '-':
return a - b;
break;
case '/':
return a / b;
break;
case '*':
return a * b;
break;
default:
return 0.0;
}
}
Código completo em C para resolver uma expressão em notação pós-fixa (notação polonesa reversa)
/* Aula 233
4) Notação pós-fixa (polonesa reversa) (calculadoras HP)
Infixa Pós-fixa
(51+13*12) 51 13 12 * + R = 207
(5*(3+2)/4-6) 5 3 2 + * 4 / 6 - R = 0,25
(5+3+2*4-6*7*1) 5 3 + 2 4 * + 6 7 * 1 * - R = -26
(5*(3+(2*(4+(6*(7+1)))))) 5 3 2 4 6 7 1 + * + * + * R = 535
Código escrito por Wagner Gaspar
Julho de 2021
*/
typedef struct no{
float valor;
struct no *proximo;
}No;
No* empilhar(No *pilha, float num){
No *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
novo->proximo = pilha;
return novo;
}
else
printf("\tErro ao alocar memoria!\n");
return NULL;
}
No* desempilhar(No **pilha){
No *remover = NULL;
if(*pilha){
remover = *pilha;
*pilha = remover->proximo;
}
else
printf("\tPilha vazia\n");
return remover;
}
float operacao(float a, float b, char x){
switch(x){
case '+':
return a + b;
break;
case '-':
return a - b;
break;
case '/':
return a / b;
break;
case '*':
return a * b;
break;
default:
return 0.0;
}
}
float resolver_expressao(char x[]){
char *pt;
float num;
No *n1, *n2, *pilha = NULL;
pt = strtok(x, " ");
while(pt){
if(pt[0] == '+' || pt[0] == '-' || pt[0] == '/' || pt[0] == '*'){
n1 = desempilhar(&pilha);
n2 = desempilhar(&pilha);
num = operacao(n2->valor, n1->valor, pt[0]);
pilha = empilhar(pilha, num);
free(n1);
free(n2);
}
else{
num = strtol(pt, NULL, 10);
pilha = empilhar(pilha, num);
}
pt = strtok(NULL, " ");
}
n1 = desempilhar(&pilha);
num = n1->valor;
free(n1);
return num;
}
int main(){
char exp[50] = {"5 3 2 4 6 7 1 + * + * + *"};
printf("Resultado de %s:\t", exp);
printf("%f\n", resolver_expressao(exp));
}
