#include <bits/stdc++.h>

using namespace std;


/*
Quando fazermos alguma estrutura dinâmica, isso quer dizer que você tera que utilizar apenas ponteiros,
e Nós, já que cada Nó guarda dados, e cada Nó tem um ponteiro apontando para o proximo Nó, pois para
conseguir acessar outros elementos é necessario fazer isso para não perdermos os outros elementos independentimente
da estrutura que você esteja usando.
*/
// O pai aponta pro item topo da pilha.
class No{
    public:
        char item;
        No *proximo;
};

class PilhaDinamica{
    public:
        No *topo;
        int pilha_tamanho;

        // Construtor
        PilhaDinamica(){
            topo = NULL;
            pilha_tamanho = 0;
        }

        // Verificando se a pilha esta vazia
        bool vazia(){
            if (topo == NULL){
                return true;
            }
            else
            {
                return false;
            }
        }

        // Verificando o tamanho da pilha
        int tamanho_pilha(){
            No *aux = topo;
            while(aux != NULL){
                pilha_tamanho++;
                aux = aux->proximo;
            }
            return pilha_tamanho;
        }

        /*
        Esse metodo push você insere elementos a pilha, o primero passo é alocar memoria dinamicamenta,
        em um ponteiro para ter um lugar para se armazenar.
        */
        bool push(char elemento){
            No *no_filho = new No();

            if (no_filho == NULL){ // Caso o OS não forneça memoria ele apontara para NULL e retornata false
                return false;
            }
            else
            {
                /*
                O no_filho tem memoria alocada dinamicamente, postanto sempre que o metodo for chamado, sera criado
                um local na memoria com esse Nó com seus dados dentro, esse Nó provem de uma class, portanto o mesmo
                funcionaria com o new já que ele sempre cria um novo endereço para tal objeto, portanto alocando
                dinamicamente.
                */
                no_filho->item = elemento;
                no_filho->proximo = topo;

                topo = no_filho;
                return true;
            }
        }

        // Metodo pop para retornar e remover o ultimo elemento da pilha,
        // no caso oque esta no topo.
        char pop(){
            No *TEMP;

            if (vazia()){
                return false;
            }
            else
            {
                char elemento = topo->item;
                TEMP = topo;
                topo = topo->proximo;
                free(TEMP);
                pilha_tamanho--;
                return elemento;
            }
        }

        // Metodo para verificar o elemento que esta no top da pilha.
        char espiando_topo(){
            return topo->item;
        }

};

int len(char *elemento){
    int tamanho = 0;
    while(*elemento != '\0'){
        tamanho++;
        elemento++;
    }
    return tamanho;
}

bool verificando(char *elemento){
    PilhaDinamica *referencia_pilhaDinamica = new PilhaDinamica();
    int tamanho = len(elemento);
    int aux = 0;

    while(aux < tamanho){

        if ((*elemento == '(') || (*elemento == '[') || (*elemento == '{')){
            referencia_pilhaDinamica->push(*elemento);
        }
        else
        {
            if (*elemento == ')'){
                if (referencia_pilhaDinamica->pop() != '('){
                    return false;
                }
            }
            else if(*elemento == '}'){
                if (referencia_pilhaDinamica->pop() != '{'){
                    return false;
                }
            }
            else if(*elemento == ']'){
                if (referencia_pilhaDinamica->pop() != '['){
                    return false;
                }
            }
        }
    aux++;
    elemento++;
    }
    return referencia_pilhaDinamica->vazia();
}

void resultado(char *elemento){
    if (verificando(elemento) == true){
        cout << "\n" << elemento << " <- CORRETO!" <<"\n";
    }
    else
    {
        cout << "\n" << elemento << " <- ERRADO!" <<"\n";
    }
}


int main()
{

    char *a = "{g}[(hj)]k";
    resultado(a);

    char *b = "a + [b + (2*c*d + 2)]";
    resultado(b);

    char *c = "a + b + (2*c*d + 2)]";
    resultado(c);

    char *d = "a +( b + 2*c*d + 2)]";
    resultado(d);

    char *f = "a +( b + 2*c*d + 2))";
    resultado(f);

    char *g = "a + [b + (2*c*d + 2])";
    resultado(g);

    char *h = "a + [b + (2*c*d + 2";
    resultado(h);

    char *i = "a + b + 2*c*d + 2])";
    resultado(i);

    char *j = "a + [b + [2*c*d + 2]]";
    resultado(j);

    char *l = "{[a + b] + ({2*c*d} + 2)}";
    resultado(l);



}