L1Q2 - NEW

    #include <iostream>
    #include <string>
    #include <cstdio>
    using namespace std;


    //IMPLEMENTAÇÃO DA MINHA PILHA ~
    typedef struct nop
    {
        struct nop* proximo;
        char valor;

    } Nop;

    typedef struct pilha
    {
        Nop* primeiro;
    } Pilha;

    Pilha* inicializarPilha(Pilha* p)
    {
        p->primeiro = NULL;
        return p;
    }

    bool isVazia(Pilha* p)
    {
        return p->primeiro == NULL;
    }

    Pilha* push(Pilha* p, char v)
    {
        Nop* novo = new Nop();
        novo->valor = v;
        if (p->primeiro == NULL)
        {
            novo->proximo = NULL;
            p-> primeiro = novo;
        }
        else
        {
            novo->proximo = p->primeiro;
            p->primeiro = novo;
        }
        return p;
    }

    char pop(Pilha *p)
    {
        char v;
        Nop* aux = p->primeiro;
        v = p->primeiro->valor;
        if (p->primeiro->proximo == NULL)
        {
            p->primeiro = NULL;
        }
        else
        {
            p->primeiro = p->primeiro->proximo;
        }
        delete aux;
        return v;
    }

    void mostrarElementos(Pilha *p)
    {
        Nop* aux = p->primeiro;
        while (aux != NULL)
        {
            printf("%c ", aux->valor);
            aux = aux->proximo;
        }
    }

    void deletaPilha(Pilha* p)
    {
        Nop* aux = p->primeiro;
        while (aux != NULL)
        {
            Nop* aux2 = aux->proximo;
            delete(aux);
            aux = aux2;
        }
        delete p;

    }

    //Teste de pilha
    /*int main() {
    Pilha* p = new Pilha();

        p = inicializarPilha(p);

        p = push(p, '(');
        p = push(p, '(');
        p = push(p, '[');
        p = push(p, 'c');
        mostrarElementos(p);
        pop(p);
        pop(p);
        printf("\n");
        mostrarElementos(p);

        return 0;
    } */


    //IMPLEMENTAÇÃO DA LISTA

    //FILA DUPLAMENTE ENCADEADA NO ESTILO LISTA ~DIMAS~DARK~

    typedef struct no
    {
        char valor;
        struct no *proximo, *anterior;
    } No;

    typedef struct lista
    {
        No* inicio;
        No* fim;

    } Lista;



    Lista* inicializa()
    {
        Lista* l = new Lista();
        l ->inicio = l->fim = NULL;
        return l;
    }

    int isVazia(Lista* l)
    {
        if (l->inicio == NULL)
            return 1;
        else
            return 0;
    }

    //Insere no início
    Lista* insereNoInicio(Lista* l, int v)
    {
        No* novo = new No();
        novo->valor = v;
        novo->anterior = NULL;
        novo->proximo = l->inicio;
        if (l->inicio != NULL)
        {
            l->inicio->anterior = novo;
            l->inicio = novo;
        }
        else
        {
            l->inicio = l->fim = novo;
        }


        return l;
    }

    //Insere no fim
    Lista* insereNoFinal(Lista* l, int v)
    {
        No* novo = new No();
        novo ->valor = v;
        novo ->proximo = NULL;
        novo ->anterior = l->fim;
        if (l->fim != NULL)
        {
            l->fim->proximo = novo;
            l->fim = novo;
        }
        else
            l->inicio = l->fim = novo;


        return l;
    }

    //Funções retira
    No* retiraIni(No* n)
    {
        No* p = n->proximo;
        if (p != NULL)
            p->anterior = NULL;
        delete(n);
        return p;

    }

    No* retiraFim(No* n)
    {
        No* p = n->anterior;
        if (p != NULL)
            p->proximo = NULL;
        delete(n);
        return p;
    }


    int retiraDoInicio(Lista* l)   //Remove do inicio e retorna o valor que removeu
    {
        int v;
        v = l->inicio->valor;
        l->inicio = retiraIni(l->inicio);
        if (l->inicio == NULL)
            l->fim = NULL;
        return v;
    }

    int retiraDoFinal(Lista* l)   //Retira do final e retorna o valor que removeu
    {
        int v;
        v = l->fim->valor;
        l->fim = retiraFim(l->fim);
        if (l->fim == NULL)
            l->inicio = NULL;
        return v;
    }

    int prioridade(char operador)
    {
        int retorno;
        switch (operador)
        {
        case '(':
        {
            retorno = 1;
            break;
        }
        case '+':
        {
            retorno = 2;
            break;
        }
        case '-':
        {
            retorno = 2;
            break;
        }
        case '*':
        {
            retorno = 3;
            break;
        }
        case '/':
        {
            retorno = 3;
            break;
        }
        }
        return retorno;
    }

    bool verificaPrioridade(char opr1, char opr2)
    {
        int prioridade1 = prioridade(opr1);
        int prioridade2 = prioridade(opr2);

        if (prioridade1 >= prioridade2)
            return true;
        else
            return false;
    }

    void mostrarElementos(Lista *l)
    {
        No* aux = l->inicio;
        while (aux != NULL)
        {
            printf("%c ", aux->valor);
            aux = aux->proximo;
        }
    }

    //Passa uma string para lista
    void stringNaLista(Lista* l, char* entrada)
    {
        for (int i = 0; entrada[i]; i++)
        {
            l = insereNoFinal(l, entrada[i]);
        }
    }



    string pre2pos(string prefixa)
    {
        Pilha* p = new Pilha();
        string posfixa;
        char x;

        for (unsigned int i = 0; prefixa[i] != '\0'; i++)
        {

            if (prefixa.at(i)>= '0' && prefixa.at(i) <= '9')
                posfixa += prefixa.at(i);
            else if (prefixa.at(i) == '+' || prefixa.at(i) == '-' || prefixa.at(i) == '*' || prefixa.at(i) == '/')
            {
                if (isVazia(p) || p->primeiro->valor == '(')
                {
                push(p, prefixa.at(i));
                }
                else {
                while (!isVazia(p) && (verificaPrioridade(p->primeiro->valor, prefixa.at(i))) && p->primeiro->valor != '(')
                {
                    x = pop(p);
                    cout<< x << "\n";
                    posfixa += x;
                }
                push(p, prefixa.at(i));

                }
            }else if (prefixa.at(i) == '(') {
                push(p, prefixa.at(i));
            }
            else if (prefixa.at(i) == ')')
            {
                while (p->primeiro->valor != '(')
                {
                    x = pop(p);
                    cout<< x << "\n";
                    posfixa += x;

                }
                pop(p);
            }
        }
        while (!isVazia(p))
        {
            x = pop(p);
            cout<< x << "\n";
            posfixa += x;
        }
        delete p;
        return posfixa;
    }



    int main()
    {
        Lista* l = new Lista();
        l = inicializa();

        char line[1024];
        string entrada;
        cin.getline(line, 1024);
        entrada = line;
        cout << verificaPrioridade(entrada[2], entrada[5]);
        string saida = pre2pos(entrada);

       cout << saida;

        return 0;
    }