// ------------------------------------------------------------------------------------------------
// ----------- Aplicação de Pilhas: Notação Polonesa e Polonesa Reversa ---------------------------
// ---- Expressao Bem Parentizada, mas não necessariamente Parentizada Completa -------------------
// ------------------------------------------------------------------------------------------------
#include <iostream> //cout
#include <string>
#include <stack>
#include <cmath>
using namespace std;

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




// ------------------------------------------------------------------------------------------------
// ---------- MAIN --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
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;


    cout<<"expr: (A*B+C*D*E+F*G-H*I*J*K) => polo_rev: "<<expr_to_polonesa("(A*B+C*D*E+F*G-H*I*J*K)",0)<<endl;
    cout<<"expr: (A*B+C*D*E+F*G-H*I*J*K) => polo_rev: "<<expr_to_polonesa("(A*B+C*D*E+F*G-H*I*J*K)",1)<<endl;
    cout<<"expr: (A+B*C)*(D+E*F) => polo_rev: "<<expr_to_polonesa("(A+B*C)*(D+E*F)",1)<<endl;
    cout<<"expr: (A+B*C^D)^(E+F*G^H) => polo_rev: "<<expr_to_polonesa("(A+B*C^D)^(E+F*G^H)",0)<<endl;
    cout<<"expr: (A+B*C^D)^(E+F*G^H) => polo_rev: "<<expr_to_polonesa("(A+B*C^D)^(E+F*G^H)",1)<<endl;

    cout.precision(10);
    cout<<"expr: (1+4*3^2)^(1+1*3^0) => polo_rev: "<<calcula("(1+4*3^2)^(1+1*3^0)")<<endl;
    cout<<"expr: (9000.0009+1.1*1.1) => polo_rev: "<<calcula("(9000.0009+1.1*1.1)")<<endl;
    return 1;
}


// ------------------------------------------------------------------------------------------------
// ---- conversao da Notacao Polonesa para Expressao ----------------------------------------------
// ------------------------------------------------------------------------------------------------
string polonesa_to_expr(string expr, bool rev) {
    int i;
    int N = expr.size();
    stack<string> P;
    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 = P.top(); P.pop();
            string A = P.top(); P.pop();
            if ((A=="")||(B=="")) return "";

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


// ------------------------------------------------------------------------------------------------
// ---- conversao da Expressao para Notacao Polonesa ----------------------------------------------
// ------------------------------------------------------------------------------------------------
int prior(char op) {
    if (op=='+' || op=='-') return 1;
    if (op=='*' || op=='/') return 2;
    if (op=='^')            return 3;
    return -1;
}

void process_op(stack<string>& st, char op, bool rev) {
    string r = st.top(); st.pop();
    string l = st.top(); st.pop();
    string s(1,op);
    if (rev) st.push(l+r+s); else st.push(s+l+r);
}

string expr_to_polonesa(string expr, bool rev) {
    stack<string> st;
    stack<char> op;
    for (int i = 0; i < expr.size(); i++) {
        char c = expr[i];
        if (c==' ') continue;
        if (c=='(') op.push(c);
        else if (c == ')') {
            while (op.top() != '(') {
                process_op(st, op.top(), rev);
                op.pop();
            }
            op.pop();
        } else if (c=='+' || c=='-' || c=='*' || c=='/' || c=='^') {
            while (!op.empty() && prior(op.top()) >= prior(c)) {
                process_op(st, op.top(), rev);
                op.pop();
            }
            op.push(c);
        } else {
            string number;
            while (i < expr.size() && isalnum(expr[i]))
                number = number + expr[i++];
            --i;
            st.push(number);
        }
    }
    while (!op.empty()) {
        process_op(st, op.top(), rev);
        op.pop();
    }
    return st.top();
}


// ------------------------------------------------------------------------------------------------
// ---- Calcula o valor de uma expressao em Notacao Matematica com Numeros ------------------------
// ------------------------------------------------------------------------------------------------
void process_op2(stack<double>& st, char op) {
    double r = st.top(); st.pop();
    double l = st.top(); st.pop();
    switch (op) {
        case '+': st.push(l + r); break;
        case '-': st.push(l - r);  break;
        case '*': st.push(l * r);   break;
        case '/': st.push(l / r);    break;
        case '^': st.push(pow(l,r));  break;
    }
}

double calcula(string expr) {
    stack<double> st;
    stack<char> op;
    for (int i = 0; i < expr.size(); i++) {
        char c = expr[i];
        if (c==' ') continue;
        if (c=='(') {
            op.push(c);
        } else if (c == ')') {
            while (op.top() != '(') {
                process_op2(st, op.top());
                op.pop();
            }
            op.pop();
        } else if (c=='+' || c=='-' || c=='*' || c=='/' || c=='^') {
            while (!op.empty() && prior(op.top()) >= prior(c)) {
                process_op2(st, op.top());
                op.pop();
            }
            op.push(c);
        } else {
            double number = 0;
            double dig = 1;
            while (i < expr.size()) {
                if (isalnum(expr[i])) {
                    if (dig==1)
                        number = number * 10 + (expr[i++] - '0');
                    else {
                        number = number + dig*((expr[i++] - '0'));
                        dig /= 10.0;
                    }
                }
                else if ((dig==1)&&(expr[i]=='.' || expr[i]==',')) {
                    i++; dig /= 10.0;
                }
                else if ((dig!=1)&&(expr[i]=='.' || expr[i]==',')) {
                    i++; //ignorar se tiver mais de um ponto ou vírgula
                }
                else break;
            }
            --i;
            st.push(number);
        }
    }
    while (!op.empty()) {
        process_op2(st, op.top());
        op.pop();
    }
    return st.top();
}