#include "string.h"
#include "stdio.h"
#define MAX 100

void Insere(char chave);
char Remove(void);
bool verificaBalanco(char * Fonte);
bool mesmoTipo(char abre, char fecha);
bool abre(char c);
bool fecha(char c);


struct SNo
{
   char chave;
   SNo * prox;
};

SNo * Topo = NULL; /* Topo aponta para nada */

int main()
{
	 char Fonte[40];
	 int i;

	 strcpy(Fonte,"lixo");

	 while(strcmp(Fonte,"fim") != 0)
	 {
		 printf("Digite Sequencia: ");
		 scanf("%s",Fonte);
		 Topo = NULL;
		 if(verificaBalanco(Fonte)==true) {
		    printf("OK\n");
		 }
		 else {
		    printf("ERRO\n");
		 }
	 }
}

bool verificaBalanco(char * Fonte) {

   char topo;
   char c;
   
   for(int i=0;Fonte[i]!='\0';++i) {
      c = Fonte[i];
      if(abre(c)) Insere(c);
      if(fecha(c)) {
        if(Topo == NULL) {
	     printf("Fechando o que não foi aberto\n");
	    return(false);
	}
        topo = Remove();
	if(!mesmoTipo(c,topo)) {
	    printf("Fechou tipo incorreto\n");
	    return(false);
	}
      }
   }   
   if(Topo == NULL) return true;
   else {
      printf("Abriu e não fechou\n");
      return false;
   }
   
}

bool mesmoTipo(char fecha, char abre) {
   if(  (abre == '(' && fecha == ')') ||
        (abre == '{' && fecha == '}') ||
	(abre == '[' && fecha == ']') ) return true; 
   else return false;
}

bool abre(char c) {
   if(c == '[' || c == '(' || c == '{')  return true;
   else return false;
}

bool fecha(char c) {
   if(c == ']' || c == ')' || c == '}') return true;
   else return false;
}

void Insere(char chave)
{
   SNo * No;
   
   No = new SNo;
 
   
   if(No==NULL)
   {
   	printf("Overflow");
   }
   else
   {
      No->chave = chave;
      No->prox = Topo;
      
      Topo = No;
   }
}

char Remove(void)
{
   char chave;
   SNo * temp;
   
   if(Topo==NULL)
   {
   	printf("Underflow");
   }
   else
   {
      chave = Topo->chave;
      temp = Topo->prox;
      delete Topo;
      Topo = temp;
      
      return(chave);
   }  	
}