Problema com notação posfixa em pilha

[vidaloka860 1]

tenho o seguinte trabalho...

Pegar uma operação posfixa e fazer o calculo da mesma...

Cheguei a seguinte logica... So que não tando certo a parte de buscar o ultimo elemento da lista... pq?

 

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 100

struct Pilha
{
	char dados[MAX];
	int topo;
};

Pilha p;

int push(char px);
int pop(char *px);
int calc_pri(char px);

main()
{
	char exp[101], val, val1, val2;
	int i,vet2[101],controla2=0,resultado,total;
	
	printf("Notacao postixa: ");
	gets(exp);
	printf("\nResultado: ");
	
	p.topo = -1; // iniciar pilha (vazia)
	i = 0;
	while (exp[i] != '\0')
	{
		if(exp[i] >=48 && exp[i]<=56){
            push(exp[i]);


		}
		else if(exp[i]=='+'){
            vet2[controla2]=1;
  push('|');       
		}else if(exp[i]=='-'){
            vet2[controla2]=2;
            controla2++;
             push('|');  
		}else if(exp[i]=='*'){
            vet2[controla2]=3;
            controla2++;
             push('|');  
		}else if(exp[i]=='/'){
            vet2[controla2]=4;
            controla2++;
             push('|');  
		}

	total++;				
		i++;	
	}
	for(int i=0;i<total;i++){
	
if(vet2[i]==1)
resultado=((pop(&val1))+(pop(&val2)));

}

printf("%d",resultado);
	getch();
		
}

int push(char px)
{
	if (p.topo == MAX - 1)
		return 1; // pilha cheia
	else
	{
		p.topo++;
		p.dados[p.topo] = px;
		return 0; // inseriu na pilha	
	}	
}

int pop(char *px)
{
	if (p.topo == -1)
		return 1; // pilha vazia
	else
	{
		*px = p.dados[p.topo];
		p.topo--;
		return 0; // removeu da pilha	
	}
}

[ScreenBlack 13]

Você está percorrendo errado a string pra inserir na pilha. Deve ser feita de trás pra frente, pois o primeiro elemento a entrar, será o último a sair.

Exemplo:

56*7+

Inserir nessa ordem:

PilhaSinal[0] = '+'
PilhaValores[0] = 7;
PilhaSinal[1] = '*';
PilhaValores[1] = 6;
PilhaValores[2] = 5;

Você fará 2 "pop()" de Valor e 1 "pop()" de sinal, ficando:

5*6

Põe o resultado na pilha novamente:

PilhaValores[1] = 30;

Agora, faz novamente 2 "pop()" de Valor e 1 "pop()" de sinal, ficando:

30+7

Põe o resultado na pilha novamente:

PilhaValores[0] = 37;

Finalmente o "pop()" de Valor pra pegar o resultado:

resultado = pop();

Além disso, você precisa mudar o tipo de vetor de char pra int na estrutura pilha.
Pra fazer a inserção diretamente em int, use:

push(exp[i]-48);

o valor 48 é '0' em ascii, logo, 48 - 48 = 0 em inteiro.

Espero que ajude.

 

EDIT:

Fazendo uns testes, vi que a minha solução não servirá pra todas as funções pós-fixas.
Por exemplo:

523+*

Nesse caso, teria de somar 2 e 3, depois multiplicar por 5, resultando em 25.

[guidjos 65]

"56*" é um erro: * é binário.

[ScreenBlack 13]

guidjos, desculpe, mas não entendi. Internamente, tudo é binário.

 

Se for sobre a interpretação do "*" pra efetuar a multiplicação, o código faz essa comparação.

No caso "56*", os valores "5" e "6" serão convertidos pra inteiros, inseridos na pilha e para "*" , será feita a comparação convertendo pra um "id" e inseridos na pilha de operadores.

 

O código do colega acima, parou na interpretação do primeiro "id" (1), que é a soma.

A lógica está certa. Faltou apenas converter os chars entre "0" e "9" pra inteiros, e trocar o tipo de dado da estrutura, para poder executar a operação e obter o resultado correto. Porém, nada impede de fazer as comparações depois, na hora do cálculo.

 

Abs!

[guidjos 65]

O caso é que o operador * (multiplicação) é binário, ou seja, tem aridade 2. Isto quer dizer que ele precisa de 2 operandos.

Pensei que a ideia era aceitar operandos maiores que 9. Parece que não.

Ainda assim, o programa todo precisa ser reestruturado. Antes de consertar a lógica, sugiro arrumar a indentação e remover as chamadas a gets.

Como o código que você postou usa a conio.h, que é dependente de implementação, ao invés de encontrar os erros nele, escrevi minha própria calculadora.

Ela também usa notação posfixa, e consome os argumentos da linha de comando. Exemplo:

./rpn 52 48 + 77 - 155 "*" 137 12841 10 sum

A operação acima é equivalente à seguinte:

sum((52 + 48 - 77) * 155, 137, 12841, 10)

O programa devolve o resultado correto: 16553. Observar que o caractere * tem significado especial no bash, portanto é preciso explicitar que se deseja passar a string "*".

O código está aqui: https://gist.github.com/guipn/5122682

[Roberto Bauer 0]

Luis, fiz um texto no meu blog sobre o assunto, de uma olhada, a tecnica usada é a mesma do Aaron Tenenbaum no livro de estrutura de dados que este escreveu.

http://algoritmoconcreta.blogspot.com.br/2013/02/avaliando-uma-expressao-pos-fixa.html