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

copynow
(usa Slackware)

Enviado em 03/03/2011 - 06:59h

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 ja com os templates do Pilha.h prontos oh:

#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

jessikadias
(usa Ubuntu)

Enviado em 21/11/2013 - 19:45h

Bom, o caso é o mesmo, balanceamento de parenteses.
Tá rodando legal, mas ele nao ignora outros caracteres.
Ele conta os (), {} e [] e conta tambem os numeros e sinais matemáticos.
Preciso que ele os ignore para que o código esteja corretíssimo.
Se puderem me ajudar, agradeço.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include "biblio.h"

struct dado{
char num;
struct dado *ant;
};

struct dado *push(struct dado *tp, char n)
{
struct dado *novo;
novo= (struct dado*)malloc(sizeof(struct dado));
novo->num= n;
novo->ant= tp;
tp=novo;

return tp;
}//funcao para inserir os dados

struct dado *pop(struct dado *tp)
{
struct dado *aux;
aux=tp;
tp= aux->ant;
free(aux);

return tp;
}//funcao para remover os dados


void mostrar (struct dado *tp)
{
struct dado *aux;
aux = tp;
while(aux != NULL)
{
printf("\n%d \n",aux -> num);
aux = aux -> ant;
}
}//funcao para mostrar os dados


struct dado *popEsp(struct dado *tp)
{
struct dado *esp, *aux;
aux=tp;
tp= aux->ant;
esp=(struct dado*)malloc(sizeof(struct dado));
esp->num=aux->num;
esp->ant= tp;//aux->ant;
free(aux);

return esp;
}//funcao remover especial retornando numero removido

int main()
{
struct dado *topo, *retorno;
topo = NULL;
char expr[20];
int i, tam, cont;
int flag;
flag = 0;
cont = 0;
printf("\nEntre com a expressao: ");
fflush(stdin);
gets(expr);
tam = strlen(expr);
for(i=0;i<tam;i++)
{
if((expr[i] == '(') || (expr[i] == '[') || (expr[i] == '{'))
{
topo = push(topo, expr[i]);
} else {
if(topo == NULL)
{
printf("\nExpressao errada!!!");
printf("\nPilha vazia!!!");
flag = 1;
break;
}
retorno = popEsp(topo);
topo = retorno->ant;
if(!(((expr[i] == ')') && (retorno->num == '(')) || (((expr[i] == ']') && (retorno->num == '[')) || ((expr[i] == '}') && (retorno->num == '{')))))
{
printf("\nA expressao esta invalida!!!");
printf("\n%c nao casa com %c!!!!\n", retorno -> num, expr[i]);
flag = 1;
break;
}
}

}

if ((flag == 0)&&(topo==NULL))
{
printf("\n\nExpressao correta!!!");
printf("\nTodos os elementos casam!!!\n");
}


if((flag ==0)&&(topo!=NULL))
printf("\n\nExpressao errada!!!");

}