Código C++ para balanceamento de parenteses usando pilha encadeada

[copynow]

Eu precisava de ajuda com um código para um programa para validar uma

expressão aritmética com relação ao balenceamento

de “()” “[]” e “{}”

- Exemplo:

◦ d^{[(a+B ) * c] * [c*(a+d) ^(d+e)]} ok

◦ d^{[(a+B ) * c] * c*(a+d) ^(d+e)]} errado

Usando pilha encadeada já com os templates do Pilha.h que já estão ok.

#ifndef _PilhaEnc_H
#define _PilhaEnc_H
#include <stdexcept>
using std::logic_error;

namespace ED {
template <typename Tipo>
class PilhaEnc {
public:
PilhaEnc();
~PilhaEnc();

// Métodos principais
void empilha(const Tipo &elem) throw (logic_error);
Tipo desempilha() throw (logic_error);
// Métodos auxiliares
bool vazia();
int tamanho();
private:
struct Celula {
Tipo el;
Celula *prox;
};

Celula *topo;
int nelem;
};

// Construtor
template <typename Tipo>
PilhaEnc<Tipo>::PilhaEnc() {
topo = NULL;
nelem = 0;
}

// Destrutor
template <typename Tipo>
PilhaEnc<Tipo>::~PilhaEnc() {
Celula *aux;
while (topo) {
aux = topo;
topo = topo->prox;
delete aux;
}
}

// Empilha
template <typename Tipo>
void PilhaEnc<Tipo>::empilha(const Tipo &el) throw (logic_error){
Celula *nova = new Celula;
if (nova == NULL) throw logic_error("Falta memoria\n");
nova->el = el;
nova->prox = topo;
topo = nova;
nelem++;
}

// Desempilha
template <typename Tipo>
Tipo PilhaEnc<Tipo>::desempilha() throw (logic_error) {
if (nelem == 0) throw logic_error("Pilha vazia\n");
Tipo ret = topo->el;
Celula *aux = topo;
topo = topo->prox;
delete aux;
nelem--;
return(ret);
}

// Métodos auxiliares
template <typename Tipo>
bool PilhaEnc<Tipo>::vazia() {
return(nelem == 0);
}
template <typename Tipo>
int PilhaEnc<Tipo>::tamanho() {
return(nelem);
}
}
#endif

Editado Março 3, 2011 por copynow

[CPP]

Se ainda precisar de ajuda segue o codigo com uma sugestão.

Abs

#ifndef _PilhaEnc_H
#define _PilhaEnc_H
#include <stdexcept>
using std::logic_error;

namespace ED 
{
template <typename Tipo>
class PilhaEnc 
    {
    public:
        PilhaEnc();
        ~PilhaEnc();

        // Métodos principais
        void empilha(const Tipo &elem) throw (logic_error);
        Tipo desempilha() throw (logic_error);
        // Métodos auxiliares
        bool vazia();
        int tamanho();
        
    private:
        struct Celula 
            {
            Tipo el;
            Celula *prox;
            };
        Celula *topo;
        int nelem;
};

// Construtor
template <typename Tipo>
PilhaEnc<Tipo>::PilhaEnc() 
{
    topo = NULL;
    nelem = 0;
}

// Destrutor
template <typename Tipo>
PilhaEnc<Tipo>::~PilhaEnc() 
{
    Celula *aux;
    while (topo) 
        {
        aux = topo;
        topo = topo->prox;
        delete aux;
        }
}

// Empilha
template <typename Tipo>
void PilhaEnc<Tipo>::empilha(const Tipo &el) throw (logic_error)
{
    Celula *nova = new Celula;
    if (nova == NULL) throw logic_error("Falta memoria\n");
        nova->el = el;
    nova->prox = topo;
    topo = nova;
    nelem++;
}

// Desempilha
template <typename Tipo>
Tipo PilhaEnc<Tipo>::desempilha() throw (logic_error) 
{
    if (nelem == 0) 
        throw logic_error("Pilha vazia\n");
    Tipo ret = topo->el;
    Celula *aux = topo;
    topo = topo->prox;
    delete aux;
    nelem--;
    return(ret);
}

// Métodos auxiliares
template <typename Tipo>
bool PilhaEnc<Tipo>::vazia() 
{
    return(nelem == 0);
}

template <typename Tipo>
int PilhaEnc<Tipo>::tamanho() 
{
    return(nelem);
}
} // end namespace
#endif

#include <stdio.h>

using namespace ED;
void main(void)
{
    PilhaEnc <char> c;
    char Abre = 1; 
    char Fecha = -1;
    
    char expressao[100];
    char *teste[] = {"d^{[(a+B ) * c] * [c*(a+d) ^(d+e)]}",
                     "d^{[(a+B ) * c] * c*(a+d) ^(d+e)]}"};
    for (int n = 0; n < 2; n++)
        {
        strcpy(expressao, teste[n]);
        for (int x = 0; expressao[x]; x++)
            {
            if (expressao[x] == '(' || expressao[x] == '{' || expressao[x] == '[')
                c.empilha(Abre);
            if (expressao[x] == ')' || expressao[x] == '}' || expressao[x] == ']')
                c.empilha(Fecha);
            }
        char check = 0;
        while (c.tamanho() > 0)
            {
                check += c.desempilha();
            }
            
        if (check)
            printf("Expressao: %s desbalanceada...\n", expressao);
        else
            printf ("Expressao: %s Ok...\n", expressao);
        }
}