// ------------------------------------------------------------------------------------------------
// ---- Aplicação de Pilhas: Notação Polonesa e Polonesa Reversa ----------------------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <string>
#include <windows.h>
using namespace std;

string expr_to_polonesa(string expr, bool rev);
string polonesa_to_expr(string expr, bool rev);




typedef struct pilha {
    string str[50];//pilha de 50 strings
    int topo;// pilha topo
    int tam;// pilha tamanho
} pilha;


bool Push(pilha* P, string str);
string Pop(pilha* P);
void pilha_create(pilha* P);




int main() {
    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;
    return 1;
}


// ------------------------------------------------------------------------------------------------
// ---- Algoritmos de CONVERSAO (POLONESA) --------------------------------------------------------
// ------------------------------------------------------------------------------------------------
string expr_to_polonesa(string expr, bool rev) {
    pilha Pilha, Pilha_op;
    pilha_create(&Pilha); pilha_create(&Pilha_op);
    int i = 0;
    while (true) {
        char c = expr[i++];
        if (c==0) break;
        string s(1,c);
        if ((c=='+')||(c=='-')||(c=='*')||(c=='/')) {
            Push(&Pilha_op,s);
        } else
        if (c==')') {
            string B = Pop(&Pilha);
            string A = Pop(&Pilha);
            string op = Pop(&Pilha_op);
            if ((A=="")||(B=="")||(op=="")) return "";

            string aux;
            if (rev) aux = A+B+op;
            else aux = op+A+B;
            Push(&Pilha,aux);
        } else if ((c!='(')&&(c!=' ')) {
            Push(&Pilha,s);
        }
    }
    return Pop(&Pilha);
}


string polonesa_to_expr(string expr, bool rev) {
    int i;
    int N = expr.size();
    pilha Pilha;
    pilha_create(&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 = Pop(&Pilha);
            string A = Pop(&Pilha);
            if ((A=="")||(B=="")) return "";

            string aux;
            if (rev) aux = "("+A+c+B+")";
            else aux = "("+B+c+A+")";
            Push(&Pilha,aux);
        } else
        if (c!=' ') {
            Push(&Pilha,s);
        }
    }
    return Pop(&Pilha);
}


// ------------------------------------------------------------------------------------------------
// ---- Algoritmos de PILHA -----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
bool pilha_vazia(pilha* P) {
    if (P->topo<0) return true;
    return false;
}

bool pilha_cheia(pilha* P) {
    if (P->topo >= P->tam-1) return true;
    return false;
}

void pilha_create(pilha* P) {
    P->tam = 50;
    P->topo = -1;
    return;
}

bool Push(pilha* P, string str) {
    if (pilha_cheia(P)) {
        printf("Pilha Cheia (estouro positivo)\n");
        return false;
    }
    P->str[++P->topo] = str;
    return true;
}

string Pop(pilha* P) {
    if (pilha_vazia(P)) {
        //printf("Pilha Vazia (estouro negativo)\n");
        return "";
    }
    return P->str[P->topo--];
}