#include <iostream>
#include <ctime>
#include <stack>
#include <vector>
#include <deque>
using namespace std;


// QUESTOES (algoritmos principais)
void Questao2(int N);
void Questao3(int N);
void Questao4(int N);
void Questao5(int N);
void Questao6(int N);
void Questao7();
void Questao8(int N);
void Questao9(int N, int k);




// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
	int i;

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 2 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao2(20); //par
	Questao2(21); //impar

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 3 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao3(50);

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 4 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao4(50);

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 5 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao5(50);

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 6 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao6(50);

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 7 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao7();

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 8 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao8(50);

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 9 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao9(2,2);
	Questao9(3,2);
	Questao9(4,2);
	Questao9(5,2);
	Questao9(6,2);
	Questao9(50,5);

	return 0;
}




// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 2 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void trocar(int& x, int& y) {int z = x; x = y; y = z;}

int Questao2busca(int* vetor, int elemento, int N) {
    int p,q,r;

    // Procura nas posicoes impares
    p=1; r=(N+1)/2;
    while (p<=r) {
        int q = (p+r)/2;
        if (vetor[2*q-1]< elemento) p = q+1; else
        if (vetor[2*q-1]> elemento) r = q-1; else
        if (vetor[2*q-1]==elemento) return 2*q-1;
    }
    // Procura nas posicoes pares
    p=1; r=N/2;
    while (p<=r) {
        int q = (p+r)/2;
        if (vetor[2*q]> elemento) p = q+1; else
        if (vetor[2*q]< elemento) r = q-1; else
        if (vetor[2*q]==elemento) return 2*q;
    }
    return -1;
}

void Questao2(int N) {
	int* vetor = new int [N+1];
	for (int i=1; i<=N; i+=2) vetor[i] = i;
	for (int i=2; i<=N; i+=2) vetor[i] = N-i+2 -N%2;
	cout<<"Vetor[1..."<<N<<"] = (";
	for (int i=1; i<=N; i++) cout<<vetor[i]<<" ";
	cout<<")\n\n";

	int elemento = 7;
	int q = Questao2busca(vetor, elemento, N);
	if (q<0) cout<<"Elemento "<<elemento<<" nao encontrado\n";
	else cout<<"Elemento "<<elemento<<" encontrado na posicao "<<q<<"\n";

	elemento = 14;
	q = Questao2busca(vetor, elemento, N);
	if (q<0) cout<<"Elemento "<<elemento<<" nao encontrado\n";
	else cout<<"Elemento "<<elemento<<" encontrado na posicao "<<q<<"\n";

	elemento = 21;
	q = Questao2busca(vetor, elemento, N);
	if (q<0) cout<<"Elemento "<<elemento<<" nao encontrado\n\n";
	else cout<<"Elemento "<<elemento<<" encontrado na posicao "<<q<<"\n\n";

	delete[] vetor;
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 3 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void maxheapify(int* vetor, int i, int p, int r) {
    int m = i;
    int esq = p+2*(i-p)+1;
    int dir = p+2*(i-p)+2;
    if ((esq<=r)&&(vetor[esq]>vetor[i])) m = esq;
    if ((dir<=r)&&(vetor[dir]>vetor[m])) m = dir;
    if (m != i) {
        trocar(vetor[i], vetor[m]);
        maxheapify(vetor,m,p,r);
    }
}
void HeapSort(int* vetor, int p, int r) {
    int i;
    for (i=(r+p-1)/2; i>=p; i--) {
        maxheapify(vetor,i,p,r);
    }
    for (i=r;i>p;i--) {
        trocar(vetor[p], vetor[i]);
        r = r-1;
        maxheapify(vetor,p,p,r);
    }
}

void Questao3(int N) {
	int* vetor = new int [N];
	srand(time(NULL));
	cout<<"Vetor original: ";
	for (int i = 0; i<N; i++) {
        vetor[i] = rand() % 1000;
        cout<<vetor[i]<<" ";
	}
	cout<<"\n\n";
	cout<<"Vetor ord parcial: ";

	HeapSort(vetor,N/3,2*N/3);
	for (int i = 0; i<N; i++) cout<<vetor[i]<<" ";
	cout<<"\n\n";
	delete[] vetor;
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 4 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
// Usa heap mínimo enraizado na última posição do vetor
// Considerando o vetor da posição p até a posição r
void min_heapify(int* vetor, int i, int p, int r) {
    int m = i;
    int esq = 2*i-r-1;
    int dir = esq-1;
    if ((esq>=p)&&(vetor[esq]<vetor[i])) m = esq;
    if ((dir>=p)&&(vetor[dir]<vetor[m])) m = dir;
    if (m != i) {
        trocar(vetor[i], vetor[m]);
        min_heapify(vetor,m,p,r);
    }
}

void HeapSort_min(int* vetor, int p, int r) {
    int i;
    for (i=(r+p+2)/2; i<=r; i++) {
        min_heapify(vetor,i,p,r);
    }
    for (i=p;i<r;i++) {
        trocar(vetor[r], vetor[i]);
        p = p+1;
        min_heapify(vetor,r,p,r);
    }
}

void Questao4(int N) {
	int* vetor = new int [N];
	srand(time(NULL));
	cout<<"Vetor original: ";
	for (int i = 0; i<N; i++) {
        vetor[i] = rand() % 1000;
        cout<<vetor[i]<<" ";
	}
	cout<<"\n\n";
	cout<<"Vetor ordenado: ";
	HeapSort_min(vetor,0,N-1);
	for (int i = 0; i<N; i++) cout<<vetor[i]<<" ";
	cout<<"\n\n";
	delete[] vetor;
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 5 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
struct node {
	int valor;
	node* prox;
	node* ant;
};

node* InverteLista(node* raiz) {
    node* noh = raiz;
    if (noh==NULL) return NULL;
    node* nooh = noh->prox;
    noh->prox = NULL;
    while (nooh!=NULL) {
        node* noooh = nooh->prox;
        nooh->prox = noh;
        noh = nooh;
        nooh = noooh;
    }
    return noh;
}

void Questao5(int N) {
    cout<<"Lista simples: ";
    node* raiz = new node;
    node* noh = raiz;
    noh->valor = 1;
    for (int i=2; i<=N; i++) {
        noh->prox = new node;
        noh = noh->prox;
        noh->valor = i;
    }
    noh->prox = NULL;

    noh = raiz;
    while (noh!=NULL) {
        cout<<noh->valor<<" ";
        noh = noh->prox;
    }

    cout<<"\n\nLista invertida: ";
    raiz = InverteLista(raiz);
    noh = raiz;
    while (noh!=NULL) {
        cout<<noh->valor<<" ";
        node* aux = noh;
        noh = noh->prox;
        delete aux;
    }
    cout<<"\n\n";
}


// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 6 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------

class pilha_dupla {
    vector<int> vet;//vetor de inteiros
    int topo1, topo2;// pilha topo
    int tam;// pilha tamanho

public:
    pilha_dupla(int N); // construtor
    int tamanho();
    bool vazia(int i);
    bool cheia();
    bool push(int i, int x);
    int pop(int i);
    void imprime();
};

int pilha_dupla::tamanho() {return tam;}

bool pilha_dupla::vazia(int i) {
    if ((i==1) && (topo1<=0 )) return true;
    if ((i==2) && (topo2>tam)) return true;
    return false;
}

bool pilha_dupla::cheia() {
    if (topo1+1>=topo2) return true;
    return false;
}

bool pilha_dupla::push(int i, int x) {
    if ((i!=1) && (i!=2)) return false;
    if (cheia()) return false;
    if (i==1) vet[++topo1] = x;
    if (i==2) vet[--topo2] = x;
    return true;
}

int pilha_dupla::pop(int i) {
    if ((i==1) && (vazia(1))) {
        cout << "Pilha 1 vazia (estouro negativo)" << endl;
        return -1;
    }
    if ((i==2) && (vazia(2))) {
        cout << "Pilha 2 vazia (estouro negativo)" << endl;
        return -1;
    }
    if (i==1) return vet[topo1--];
    if (i==2) return vet[topo2++];
    return -1;
}

pilha_dupla::pilha_dupla(int N) {
    if (N<=0) N=10;
    tam = N;
    topo1 = 0;
    topo2 = N+1;
    vet.resize(N+1,0);
}

void pilha_dupla::imprime() {
    for (int k=1; k<=tam; k++)
        cout << vet[k] << " ";
}

void Questao6(int N) {
    pilha_dupla P(20);

    cout <<"Pilhas preenchidas aleatoriamente com PUSH_1 ou PUSH_2\n";
    int k=1;
    while (!P.cheia()) {
        if (rand()%2==0)
             P.push(1,k++);
        else P.push(2,k++);
    }
    cout << endl;
    cout <<"Numeros do vetor da pilha dupla: ";
    P.imprime();

    cout<<"\n\n";
    cout <<"Numeros tirados da PILHA_1 com POP_1: ";
    while (!P.vazia(1)) cout << P.pop(1) << " ";
    cout<<"\n\n";
    cout <<"Numeros tirados da PILHA_2 com POP_2: ";
    while (!P.vazia(2)) cout << P.pop(2) << " ";
    cout<<"\n\n";
}


// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 7 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
string expr_to_polonesa(string expr, bool rev) {
    stack<string> Pilha;
    stack<string> Pilha_op;
    int i = 0;
    while (true) {
        char c = expr[i++];
        if (c==0) break;
        string s(1,c);
        if ((c=='+')||(c=='-')||(c=='*')||(c=='/')) {
            Pilha_op.push(s);
        } else
        if (c==')') {
            string B = Pilha.top(); Pilha.pop();
            string A = Pilha.top(); Pilha.pop();
            string op = Pilha_op.top(); Pilha_op.pop();
            if ((A=="")||(B=="")||(op=="")) return "";

            string aux;
            if (rev) aux = A+B+op;
            else aux = op+A+B;
            Pilha.push(aux);
        } else if ((c!='(')&&(c!=' ')) {
            Pilha.push(s);
        }
    }
    return Pilha.top();
}


string polonesa_to_expr(string expr, bool rev) {
    int i;
    int N = expr.size();
    stack<string> Pilha;
    if (rev) i=0; else i=N-1;
    while (true) {
        if ((i<0)||(i>=N)) break;
        char c = expr[i];
        string s(1,c);
        if (rev) i++; else i--;
        if ((c=='+')||(c=='-')||(c=='*')||(c=='/')) {
            string B = Pilha.top(); Pilha.pop();
            string A = Pilha.top(); Pilha.pop();
            if ((A=="")||(B=="")) return "";

            string aux;
            if (rev) aux = "("+A+c+B+")";
            else aux = "("+B+c+A+")";
            Pilha.push(aux);
        } else
        if (c!=' ') {
            Pilha.push(s);
        }
    }
    return Pilha.top();
}


void Questao7() {
    cout<<"expr: ((A*B)-(C/D)) => polo_rev: "<<expr_to_polonesa("((A*B)-(C/D))",1)<<endl;
    cout<<"expr: ((A*B)-(C/D)) => polonesa: "<<expr_to_polonesa("((A*B)-(C/D))",0)<<endl;
    cout<<"polo-rev: AB*CD/-   => expr: "<<polonesa_to_expr("AB*CD/-",1)<<endl;
    cout<<"polonesa: -*AB/CD   => expr: "<<polonesa_to_expr("-*AB/CD",0)<<endl;
    cout<<endl;
    cout<<"expr: (W+(X*(Y-Z))) => polo_rev: "<<expr_to_polonesa("(W+(X*(Y-Z)))",1)<<endl;
    cout<<"expr: (W+(X*(Y-Z))) => polonesa: "<<expr_to_polonesa("(W+(X*(Y-Z)))",0)<<endl;
    cout<<"polo-rev: WXYZ-*+   => expr: "<<polonesa_to_expr("WXYZ-*+",1)<<endl;
    cout<<"polonesa: +W*X-YZ   => expr: "<<polonesa_to_expr("+W*X-YZ",0)<<endl;
    cout<<endl;
    cout<<"expr: (((R+S)*T)-U) => polo_rev: "<<expr_to_polonesa("(((R+S)*T)-U)",1)<<endl;
    cout<<"expr: (((R+S)*T)-U) => polonesa: "<<expr_to_polonesa("(((R+S)*T)-U)",0)<<endl;
    cout<<"polo-rev: RS+T*U-   => expr: "<<polonesa_to_expr("RS+T*U-",1)<<endl;
    cout<<"polonesa: -*+RSTU   => expr: "<<polonesa_to_expr("-*+RSTU",0)<<endl;
    cout<<"\n";
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 8 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
class meu_deque {
    vector<int> vet;
    int ini, fim;// pilha topo
    int num, tam;// numero de elementos e tamanho maximo

public:
    meu_deque(int N);
    bool cheio();
    bool vazio();
    int pop_frente();
    int pop_atras();
    void push_frente(int x);
    void push_atras(int x);
};

meu_deque::meu_deque(int N) {
    if (N<=0) N=10;
    vet.resize(N+1,0);
    ini = 1; fim = N;
    tam = N; num = 0;
}

bool meu_deque::vazio() {
    if (num==0) return true;
    return false;
}

bool meu_deque::cheio() {
    if (num==tam) return true;
    return false;
}

void meu_deque::push_frente(int x) {
    if (cheio()) {cout<<"Deque cheio\n"; return;}
    num++;
    ini--; if (ini<=0) ini=tam;
    vet[ini] = x;
}

void meu_deque::push_atras(int x) {
    if (cheio()) {cout<<"Deque cheio\n"; return;}
    num++;
    fim++; if (fim>tam) fim=1;
    vet[fim] = x;
}

int meu_deque::pop_frente() {
    if (num<=0) {cout<<"Deque vazio"; return -1;}
    num--;
    int x;
    x = vet[ini];
    ini++; if (ini>tam) ini=1;
    return x;
}

int meu_deque::pop_atras() {
    if (num<=0) {cout<<"Deque vazio"; return -1;}
    num--;
    int x;
    x = vet[fim];
    fim--; if (fim<=0) fim=tam;
    return x;
}

void Questao8(int N) {

    cout <<"\n Deque - usando meu_deque, que usa vetor internamente";
    meu_deque D(N);

    cout <<"\n Deque PUSH fim POP fim: ";
    for (int i=1; i<=N; i++) D.push_atras(i);
    while (!D.vazio()) {cout << D.pop_atras()  << " ";}

    cout <<"\n Deque PUSH fim POP ini: ";
    for (int i=1; i<=N; i++) D.push_atras(i);
    while (!D.vazio()) {cout << D.pop_frente() << " ";}

    cout <<"\n Deque PUSH ini POP fim: ";
    for (int i=1; i<=N; i++) D.push_frente(i);
    while (!D.vazio()) {cout << D.pop_atras()  << " ";}

    cout <<"\n Deque PUSH ini POP ini: ";
    for (int i=1; i<=N; i++) D.push_frente(i);
    while (!D.vazio()) {cout << D.pop_frente() << " ";}

    cout<<"\n\n\n";



    cout <<"\n Deque - usando Deque<int> pronto do C++";
    deque<int> D2;

    cout <<"\n Deque PUSH fim POP fim: ";
    for (int i=1; i<=N; i++) D2.push_back(i);
    while (!D2.empty()) {cout << D2.back() << " ";  D2.pop_back();}

    cout <<"\n Deque PUSH fim POP ini: ";
    for (int i=1; i<=N; i++) D2.push_back(i);
    while (!D2.empty()) {cout << D2.front() << " "; D2.pop_front();}

    cout <<"\n Deque PUSH ini POP fim: ";
    for (int i=1; i<=N; i++) D2.push_front(i);
    while (!D2.empty()) {cout << D2.back() << " ";  D2.pop_back();}

    cout <<"\n Deque PUSH ini POP ini: ";
    for (int i=1; i<=N; i++) D2.push_front(i);
    while (!D2.empty()) {cout << D2.front() << " "; D2.pop_front();}

    cout<<"\n\n\n";
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 9 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void print_ainda_vivos(node* Pri) {
    node* noh = Pri;
    do{ cout << noh->valor << " ";
        noh = noh->prox;
    } while (noh!=Pri);
}


void Questao9(int N, int k) {
    node* Pri;// primeiro noh da lista circular

    node* noh = new node;
    noh->valor = 1;
    Pri = noh;
    for (int i=2; i<=N; i++) {
        node* nooh = new node;
        nooh->valor = i;
        noh->prox = nooh;
        noh = nooh;
    }
    noh->prox = Pri;

    cout <<"Lista circular (N="<<N<<",k="<<k<<"):";
     cout<<endl; print_ainda_vivos(Pri);

    noh = Pri;
    for (int i=1; i<=N-k+1; i++) {
        for (int j=1; j<k-1; j++) noh = noh->prox;
        node* nooh = noh->prox->prox;
        if (noh->prox==Pri) Pri = nooh;
        delete noh->prox;
        noh->prox = nooh;
        noh = noh->prox;
        cout<<endl; print_ainda_vivos(Pri);
    }
    cout <<"            <--------   Sobreviventes\n";

    noh = Pri->prox;
    while (noh!=Pri) {
        node* nooh = noh->prox;
        delete noh;
        noh = nooh;
    }
    delete Pri;
    cout<<"\n\n";
}