#include <iostream>
#include <string>
#include <stack>

using namespace std;

//Counter jika ekspresi bernilai 24. Direset di main body.
int ctr;

//Cek karakter operan dalam rangka konversi postfix ke infix.
bool isOperand(char x)
{
   return (x >= 'a' && x <= 'z') ||
          (x >= 'A' && x <= 'Z');
}

//Konversi ekspresi postfix ke infix. Bermasalah karena tidak memroses spasi.
string getInfix(string exp)
{
    stack<string> s;

    for (int i=0; exp[i]!='\0'; i++)
    {
        // Push operands
        if (isOperand(exp[i]))
        {
           string op(1, exp[i]);
           s.push(op);
        }

        // We assume that input is
        // a valid postfix and expect
        // an operator.
        else
        {
            string op1 = s.top();
            s.pop();
            string op2 = s.top();
            s.pop();
            s.push("(" + op2 + exp[i] +
                   op1 + ")");
        }
    }

    // There must be a single element
    // in stack now which is the required
    // infix.
    return s.top();
}

//Cek karakter operator dalam rangka melakukan kalkulasi terhadap ekspresi posfix
bool isOperator(char ch)
{
    if (ch=='+' || ch=='-' || ch=='*' || ch=='/')
        return true;
    else
        return false;
}

//Kalkulator untuk evaluasi ekspresi postfix
int performOperation(int op1, int op2, char op)
{
    int ans;
    switch(op){
    case '+':
        ans = op2 + op1;
        break;
    case '-':
        ans = op2 - op1;
        break;
    case '*':
        ans = op2 * op1;
        break;
    case '/':
        ans = op2 / op1;
        break;
    }
    return ans;
}

//Evaluator ekspresi Reverse Polish Notation. Bermasalah karena memiliki kasus error yang tidak tertangani.
int EvaluatePostfix(string exp){
    int i,op1, op2, len, j = 0, x;
    char buffer[15];
    len = 13;
    stack<int> s;

    for(i=0; i<len;i++){

        if(exp[i]>='0' && exp[i]<='9'){
            buffer[j++] = exp[i];
        }
        else if(exp[i]==' '){
            if(j>0){
                buffer[j] = '\0';
                x = atoi(buffer);
                s.push(x);
                j = 0;
            }
        }

        else if(isOperator(exp[i])){
            op1 = s.top();
            s.pop();
            op2 = s.top();
            s.pop();
            s.push(performOperation(op1, op2, exp[i]));
        }
    }
}

//Prosedur pemanggil evaluator dan konverter.
//Karena masalah dalam kedua fungsi tsb, sementara hanya mengenumerasi seluruh 7680 kemungkinan.
void hitung(string s){
    cout << s;

    //if(EvaluatePostfix(s) == 24){
        //cout << getInfix(s);
        ctr++;
    //}

    cout << endl;
}

//Daftar operator dalam rangka kombinasi operator
char operative(int n){
    switch(n){
        case 1 : return '+';
        case 2 : return '-';
        case 3 : return '*';
        case 4 : return '/';
    }
}

//Kombinasi operator dan parser menurut 5 kemungkinan postfix parse tree
void triplet_op(int *a){
    string op;

    //Misalkan A sembarang operator, dan N sembarang integer
    //N N N N A A A
    //N N N A N A A
    //N N N A A N A
    //N N A N N A A
    //N N A N A N A

    for(int i=1; i<=4; i++){
        op = operative(i);
        op += " ";

        for(int j=1; j<=4; j++){
            op += operative(j);
            op += " ";

            for(int k=1; k<=4; k++){
                op += operative(k);

                hitung((char)(*a + '0') + string(" ") + (char)(*(a+1)+'0') + string(" ") + (char)(*(a+2)+'0') + string(" ") + (char)(*(a+3)+'0') + string(" ") + op);
                hitung((char)(*a + '0') + string(" ") + (char)(*(a+1)+'0') + string(" ") + (char)(*(a+2)+'0') + string(" ") + op[0] + string(" ") + (char)(*(a+3)+'0') + string(" ") + op.substr(2));
                hitung((char)(*a + '0') + string(" ") + (char)(*(a+1)+'0') + string(" ") + (char)(*(a+2)+'0') + string(" ") + op[0] + string(" ") + op[2] + string(" ") + (char)(*(a+3)+'0') + string(" ") + op[4]);
                hitung((char)(*a + '0') + string(" ") + (char)(*(a+1)+'0') + string(" ") + op[0] + string(" ") + (char)(*(a+2)+'0') + string(" ") + (char)(*(a+3)+'0') + string(" ") + op.substr(2));
                hitung((char)(*a + '0') + string(" ") + (char)(*(a+1)+'0') + string(" ") + op[0] + string(" ") + (char)(*(a+2)+'0') + string(" ") + op[2] + string(" ") + (char)(*(a+3)+'0') + string(" ") + op[4]);

                op.pop_back();
            }
            op.pop_back();
            op.pop_back();
        }
    }


}

//Fungsi swap member array dalam rangka permutasi integer masukan
void swap(int *x, int *y)
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

//Fungsi permutasi integer masukan
void permute(int *a, int l, int r)
{
   int i;
   if (l == r)
   {
        triplet_op(a);
   }
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i));
       }
   }
}



int main(){
    cout << '\n' <<"--------------WELCOME TO 24SOLVER!--------------" << '\n';
    cout << "Tugas Kecil Kuliah Strategi Algoritma (IF2211)" << '\n';
    cout << "Nama   : Harry Prabowo" << '\n' << "NIM    : 13517094" << '\n';
    cout << '\n' << "Masukkan 4 angka, masing-masing dalam baris baru." << '\n';

    //Dapat mencoba program hingga force-close.
    do{
        int n = 0, arr[4];

        ctr = 0;

        //Proses input user & passing ke array
        while(n < 4)
            cin >> arr[n++];

        permute(&arr[0], 0, 3);

        cout << "Terdapat " << ctr << " solusi." << endl;

    } while(1);

    cout << "\n\n" << "------------------Terima kasih------------------" << '\n';

    return 0;
}