C Conversão de notação Infixa para Pósfixa (PILHA)

Lvcas Jesus · 2 de maio de 2018

Olá, estou com um problema no meu código que deveria receber uma expressão aritmética em notação infixa (comum) para notação pósfixa (polonesa reversa). Por exemplo, ao receber (A+B*C) ele deveria imprimir ABC*+.
O problema de meu código é que, ao receber "(A+B*C)" ele imprime "ABC<quatro quadrados>". Ao receber "(A*(B+C)/D-E)" ele imprime "ABC<quatro quadrados>DE<quatro quadrados>". Em outros compiladores, os quadrados não aparecem, mas o retorno continua errado.
Ele não dá erro, nem mostra nenhum warning. Eu acho que ele dá segfault em algum lugar, mas como estou usando o repl.it para compilar, não tenho acesso ao debug.

O código é o seguinte:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 256
 
typedef enum {FALSE, TRUE} BOOL;
 
typedef int TIPOCHAVE;
 
typedef struct {
    TIPOCHAVE chave;
} REGISTRO;
 
typedef struct {
    REGISTRO a[MAX];
    int topo;
} PILHA;
 
REGISTRO criarReg(TIPOCHAVE chave) {
    REGISTRO reg;
    reg.chave = chave;
    return reg;
}
 
void inicializar(PILHA *pilha) {
    pilha->topo = 0;
}
 
int vazia(PILHA *pilha) {
    return pilha->topo == 0;
}
 
int cheia(PILHA *pilha) {
    return pilha->topo == MAX;
}
 
void exibir(PILHA *pilha) {
    int i = 0;
    printf("Pilha: [");
    for (i=0; i<pilha->topo; i++) {
        printf("%d", pilha->a[i].chave);
        if (i < pilha->topo-1)
            printf(", ");
    }
    printf("] <-- topo\n");
}
 
int empilha(REGISTRO elem, PILHA *pilha) {
    if (cheia(pilha)) {
        return FALSE;
    }
    pilha->a[pilha->topo] = elem;
    pilha->topo++;
    return TRUE;
}
 
int desempilha(PILHA *pilha, REGISTRO *elem) {
    if (vazia(pilha))
        return FALSE;
    *elem = pilha->a[pilha->topo-1];
    pilha->topo--;
    return TRUE;
}
 
void esvaziar(PILHA *pilha) {
    pilha->topo = 0;
}
 
int topo(PILHA *pilha, REGISTRO *elem) {
    if (vazia(pilha))
    return FALSE;
    *elem = pilha->a[pilha->topo-1];
    return TRUE;
}
 
 
//função para checar se o caractere da string é um operando
int operando(char ch)
{
    return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z');
}
 
//função que determina a prioridade de cada operador
//valor retornado maior é igual a operador de prioridade maior
int prioridade(char ch)
{
    switch(ch)
    {
        case '+':
        case '-':
            return 1;
 
        case '*':
        case '/':
            return 2;
 
        case '^':
            return 3;
    }
    return -1;
}
 
//função que converte de infixa para posfixa
int inpos(char *expr)
{
 
    PILHA pilha;
    inicializar(&pilha);
 
    int i, aux;
    REGISTRO elem;
 
    for (i = 0, aux = 0; expr[i] != '\0'; i++)
    {
      	//se o caractere escaneado for um operando, colocar no output.
        if (operando(expr[i]))
            expr[aux++] = expr[i];
      
 		//se o caractere escaneado for um '(', empilhar.
        else if (expr[i] == '(')
            empilha(criarReg(expr[i]), &pilha);
 
      	//se o caractere escaneado for um ')', desempilhar e mostrar até
      	//um '(' ser achado.
        else if (expr[i] == ')')
        {
            while (!vazia(&pilha) && topo(&pilha, &elem) != '(')
                expr[aux++] = desempilha(&pilha, &elem);
 
                if (!vazia(&pilha) && topo(&pilha, &elem) != '(')
                    return 0; //expressão inválida
                else
                    desempilha(&pilha, &elem);
        }
 
        else	//um operador é encontrado
        {
            while (!vazia(&pilha) && prioridade(expr[i]) <= prioridade(topo(&pilha, &elem)))
                expr[aux++] = desempilha(&pilha, &elem);
            empilha(criarReg(expr[i]), &pilha);
        }
    }
    //desempilha todos os elementos da pilha
    while (!vazia(&pilha))
        expr[aux++] = desempilha(&pilha, &elem);
    expr[aux++] = '\0';
    printf("%s", expr);
}
 
int main()
{
    char expr[60];
 
    fgets(expr, 60, stdin);
    inpos(expr);
 
    return 0;
}

Qualquer ajuda é apreciada.

Plástico Bolha · 2 de maio de 2018

Algumas coisas estranhas que percebi aí foi esta linha

   for (i = 0, aux = 0; expr[i] != '\0'; i++)

Em expr depois que a expressão acaba você tem um '\n' (efeito do stdin), isto causa uma iteração a mais.

E na sua função desempilha você retorna um booleano para expr, não sei se a ideia era essa mesmo, mas foi um trecho que me pareceu estranho, porque você retorna o topo da pilha para 'elem', mas não retorna ele para expr, o que expr recebe é só o bool indicando se a pilha estava vazio ou não. Como expr é um *char ele recebe bool, mas na hora de imprimir fica estranho rsrsrs ...

Lvcas Jesus · 2 de maio de 2018

Eu fiz algumas alterações no código, ele está mais perto do que eu quero mas ainda não dá o resultado esperado. Na função empilha e desempilha eu coloquei um printf para ele mostrar que valor ele está empilhando e desempilhando:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 256
 
typedef enum {FALSE, TRUE} BOOL;
 
typedef int TIPOCHAVE;
 
typedef struct {
    TIPOCHAVE chave;
} REGISTRO;
 
typedef struct {
    REGISTRO a[MAX];
    int topo;
} PILHA;
 
REGISTRO criarReg(TIPOCHAVE chave) {
    REGISTRO reg;
    reg.chave = chave;
    return reg;
}
 
void inicializar(PILHA *pilha) {
    pilha->topo = 0;
}
 
int vazia(PILHA *pilha) {
    return pilha->topo == 0;
}
 
int cheia(PILHA *pilha) {
    return pilha->topo == MAX;
}
 
void exibir(PILHA *pilha) {
    int i = 0;
    printf("Pilha: [");
    for (i=0; i<pilha->topo; i++) {
        printf("%d", pilha->a[i].chave);
        if (i < pilha->topo-1)
            printf(", ");
    }
    printf("] <-- topo\n");
}
 
int empilha(REGISTRO elem, PILHA *pilha) {
    if (cheia(pilha)) {
        return FALSE;
    }
    pilha->a[pilha->topo] = elem;
    pilha->topo++;
    printf("empilha %c\n", elem.chave);
    return TRUE;
}
 
int desempilha(PILHA *pilha, REGISTRO *elem) {
    if (vazia(pilha))
        return FALSE;
    *elem = pilha->a[pilha->topo-1];
    pilha->topo--;
    printf("desempilha %c\n", elem->chave);
    return TRUE;
}
 
void esvaziar(PILHA *pilha) {
    pilha->topo = 0;
}
 
int topo(PILHA *pilha, REGISTRO *elem) {
    if (vazia(pilha))
    return FALSE;
    *elem = pilha->a[pilha->topo-1];
    return TRUE;
}
 
 
//função para checar se o caractere da string é um operando
int operando(char ch)
{
    return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z');
}
 
//função que determina a prioridade de cada operador
//valor retornado maior é igual a operador de prioridade maior
int prioridade(char ch)
{
    switch(ch)
    {
        case '+':
        case '-':
            return 1;
 
        case '*':
        case '/':
            return 2;
 
        case '^':
            return 3;
    }
    return 0;
}
 
//função que converte de infixa para posfixa
int inpos(char expr[])
{
 
    PILHA pilha;
    inicializar(&pilha);
 
    int i, aux;
    REGISTRO elem;
 
    for (i = 0, aux = -1; expr[i]; ++i)
    {
        if (operando(expr[i]))
            expr[++aux] = expr[i];
 
        else if (expr[i] == '(')
            empilha(criarReg(expr[i]), &pilha);
 
        else if (expr[i] == ')')
        {
            while (!vazia(&pilha) && topo(&pilha, &elem) != '(')
            {
                desempilha(&pilha, &elem);
                expr[++aux] = elem.chave;
            }
            
                if (!vazia(&pilha) && topo(&pilha, &elem) != '(')
                    return 0;
                else
                    desempilha(&pilha, &elem);
            
        }
 
        else
        {
            while (!vazia(&pilha) && prioridade(expr[i]) <= prioridade(topo(&pilha, &elem)))
            {
                desempilha(&pilha, &elem);
                expr[++aux] = elem.chave;
            }
            empilha(criarReg(expr[i]), &pilha);
        }
    }
    //desempilha todos os elementos da pilha
    while (!vazia(&pilha))
    {
        desempilha(&pilha, &elem);
        expr[++aux] = elem.chave;
    }
    expr[++aux] = '\0';
    printf("%s", expr);
}
 
int main()
{
    char expr[60];
 
    fgets(expr, 60, stdin);
    inpos(expr);
 
    return 0;
}

Com essa implementação, ele retorna algo perto do que eu quero, mas ainda mostra resultados indesejáveis. Por exemplo, caso o input seja "(A+B)", ele retorna "AB+(". Com o input (A+B*C) ele retorna ABC*+(. Esse parêntesis no final não deveria estar ali.
Usando um input um pouco mais complexo, "(A*(B+C)/D-E)", meu programa agora retorna "ABC+(*(DE-/". Mesmo ignorando os parêntesis, a ordem ainda está errada.

48 minutos atrás, Plástico Bolha disse:

E na sua função desempilha você retorna um booleano para expr, não sei se a ideia era essa mesmo, mas foi um trecho que me pareceu estranho, porque você retorna o topo da pilha para 'elem', mas não retorna ele para expr, o que expr recebe é só o bool indicando se a pilha estava vazio ou não. Como expr é um *char ele recebe bool, mas na hora de imprimir fica estranho rsrsrs ...

Sim, reparei kkkkkkk, acho que isso está corrigido na segunda "versão"!