Uma pilha encadeada é uma estrutura de dados que segue o princípio LIFO (último a entrar, prmieiro a sair), implementada por meio de uma lista ligada. Neste contexto, vamos definir uma pilha ancadeada em linguagem C e utilizá-la para converter expressões infixas para a notação pós-fixa, um processo essencial em compiladores e sistemas de avaliação de expressões.

Definição da Pilha Encadeada

A estrutura da pilha é definida em um cabeçalho, com operações básicas como inicialização, limpeza, verificação de vazio, obtenção do topo, empilhamento e desempilhamento.

#ifndef PILHA_ENC_H
#define PILHA_ENC_H

#include <stdbool.h>

typedef char TipoElemento;

typedef struct NoPilha {
    TipoElemento valor;
    struct NoPilha *prox;
} NoPilha, *PilhaEnc;

void InicializarPilhaEnc(PilhaEnc *p);
void LimparPilhaEnc(PilhaEnc *p);
bool PilhaEncVazia(PilhaEnc p);
int TamanhoPilhaEnc(PilhaEnc p);
bool ObterTopoPilhaEnc(PilhaEnc p, TipoElemento *e);
void EmpilharPilhaEnc(PilhaEnc *p, TipoElemento e);
bool DesempilharPilhaEnc(PilhaEnc *p, TipoElemento *e);

#endif

Implementação das Operações

A implementação utiliza alocação dinâmica e mantém um nó sentinela para simplificar as operações.

#include "pilha_enc.h"
#include <stdlib.h>

void InicializarPilhaEnc(PilhaEnc *p) {
    *p = (NoPilha *)malloc(sizeof(NoPilha));
    if (*p == NULL) exit(EXIT_FAILURE);
    (*p)->prox = NULL;
}

void LimparPilhaEnc(PilhaEnc *p) {
    NoPilha *atual = (*p)->prox;
    NoPilha *temp;
    while (atual != NULL) {
        temp = atual;
        atual = atual->prox;
        free(temp);
    }
    (*p)->prox = NULL;
}

bool PilhaEncVazia(PilhaEnc p) {
    return p->prox == NULL;
}

int TamanhoPilhaEnc(PilhaEnc p) {
    int cont = 0;
    NoPilha *no = p->prox;
    while (no != NULL) {
        no = no->prox;
        cont++;
    }
    return cont;
}

bool ObterTopoPilhaEnc(PilhaEnc p, TipoElemento *e) {
    if (p->prox == NULL) return false;
    *e = p->prox->valor;
    return true;
}

void EmpilharPilhaEnc(PilhaEnc *p, TipoElemento e) {
    NoPilha *novoNo = (NoPilha *)malloc(sizeof(NoPilha));
    if (novoNo == NULL) exit(EXIT_FAILURE);
    novoNo->valor = e;
    novoNo->prox = (*p)->prox;
    (*p)->prox = novoNo;
}

bool DesempilharPilhaEnc(PilhaEnc *p, TipoElemento *e) {
    if ((*p)->prox == NULL) return false;
    *e = (*p)->prox->valor;
    NoPilha *temp = (*p)->prox;
    (*p)->prox = temp->prox;
    free(temp);
    return true;
}

Função de Conversão

A conversão de infixas para pós-fixas utiliza a pilha encadeada para gerenciar operadores com base em suas prioridades. O algoritmo percorre a expressão infixa e constrói a expressão pós-fixa passo a paso.

#include "pilha_enc.h"
#include <ctype.h>
#include <stdio.h>

int PrioridadeOperador(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '(': case '@': return 0;
        default: return 0;
    }
}

bool ConverterParaPosfixo(char *exprInfixa, char *exprPosfixa) {
    PilhaEnc pilha;
    InicializarPilhaEnc(&pilha);
    EmpilharPilhaEnc(&pilha, '@'); // Sentinela

    int i = 0, j = 0;
    char ch = exprInfixa[i];
    TipoElemento topo;

    while (ch != '@') {
        if (ch == ' ') {
            ch = exprInfixa[++i];
        } else if (ch == '(') {
            EmpilharPilhaEnc(&pilha, ch);
            ch = exprInfixa[++i];
        } else if (ch == ')') {
            while (true) {
                ObterTopoPilhaEnc(pilha, &topo);
                if (topo == '(') break;
                DesempilharPilhaEnc(&pilha, &topo);
                exprPosfixa[j++] = topo;
                exprPosfixa[j++] = ' ';
            }
            DesempilharPilhaEnc(&pilha, &topo);
            ch = exprInfixa[++i];
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            ObterTopoPilhaEnc(pilha, &topo);
            while (PrioridadeOperador(topo) >= PrioridadeOperador(ch)) {
                exprPosfixa[j++] = topo;
                exprPosfixa[j++] = ' ';
                DesempilharPilhaEnc(&pilha, &topo);
                ObterTopoPilhaEnc(pilha, &topo);
            }
            EmpilharPilhaEnc(&pilha, ch);
            ch = exprInfixa[++i];
        } else {
            while (isdigit(ch) || ch == '.') {
                exprPosfixa[j++] = ch;
                ch = exprInfixa[++i];
            }
            exprPosfixa[j++] = ' ';
        }
    }

    DesempilharPilhaEnc(&pilha, &topo);
    while (topo != '@') {
        if (topo == '(') return false;
        exprPosfixa[j++] = topo;
        exprPosfixa[j++] = ' ';
        DesempilharPilhaEnc(&pilha, &topo);
    }

    exprPosfixa[j++] = ' ';
    exprPosfixa[j++] = '@';
    exprPosfixa[j] = '\0';
    return true;
}

Exemplo de Uso

A função principal testa a conversão com uma expressão de exemplo, onde o caractere '@' é utilizado como marcador de fim da entrada.

#include <stdio.h>
#include <string.h>
#include "pilha_enc.h"

bool ConverterParaPosfixo(char *exprInfixa, char *exprPosfixa);

int main() {
    char entrada[] = "16-9*(4+3)+2@";
    char saida[100];
    ConverterParaPosfixo(entrada, saida);
    printf("Resultado pós-fixo: %s\n", saida);
    return 0;
}

Saída esperada: 16 9 4 3 + * - 2 + @. O caractere '@' no final facilita operações subsequentes, como avaliação da expressão.