Code:
#include <iostream>
using namespace std;
enum Action { LEAF, ADD, SUB, DIV, MUL };
struct ExprNode {
ExprNode *left;
ExprNode *right;
Action action;
int value;
ExprNode(int value)
: left(0), right(0), action(LEAF)
{
this->value = value;
}
ExprNode(ExprNode *left, ExprNode *right, Action action)
: value(0)
{
this->left = left;
this->right = right;
this->action = action;
}
double eval() {
switch (action) {
case LEAF: return value;
case ADD: return left->eval() + right->eval();
case SUB: return left->eval() - right->eval();
case DIV: return left->eval() / right->eval();
case MUL: return left->eval() * right->eval();
}
return 0;
}
friend ostream& operator<<(ostream &out, const ExprNode &rhs) {
switch (rhs.action) {
case LEAF: return out << rhs.value;
case ADD: return out << "(" << *rhs.left << " + " << *rhs.right << ")";
case SUB: return out << "(" << *rhs.left << " - " << *rhs.right << ")";
case DIV: return out << "(" << *rhs.left << " / " << *rhs.right << ")";
case MUL: return out << "(" << *rhs.left << " * " << *rhs.right << ")";
}
return out;
}
};
int main() {
Action actions[4] = { ADD, SUB, DIV, MUL };
int values[4] = { 3, 3, 8, 8 };
for (int i = 0; i < 4; ++i)
for (int j = 0; j < 4; ++j)
for (int k = 0; k < 4; ++k)
for (int l = 0; l < 4; ++l) {
// bypass duplicates
if (i == j || i == k || i == l ||
j == k || j == l || k == l)
continue;
ExprNode one (values[i]);
ExprNode two (values[j]);
ExprNode three(values[k]);
ExprNode four (values[l]);
for (int x = 0; x < 4; ++x) {
for (int y = 0; y < 4; ++y) {
for (int z = 0; z < 4; ++z) {
for (int type = 0; type < 5; ++type) {
switch (type) {
// ((a ? b) ? c) ? d
case 0: {
ExprNode AB(&one, &two, actions[x]);
ExprNode ABC(&AB, &three, actions[y]);
ExprNode ABCD(&ABC, &four, actions[z]);
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}
// (a ? b) ? (c ? d)
case 1: {
ExprNode AB(&one, &two, actions[x]);
ExprNode CD(&three, &four, actions[z]);
ExprNode ABCD(&AB, &CD, actions[y]);
if (actions[y] == DIV && CD.eval() == 0)
break;
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}
// (a ? (b ? c)) ? d
case 2: {
ExprNode BC(&two, &three, actions[y]);
ExprNode ABC(&one, &BC, actions[x]);
ExprNode ABCD(&ABC, &four, actions[z]);
if (actions[x] == DIV && BC.eval() == 0)
break;
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}
// a ? ((b ? c) ? d)
case 3: {
ExprNode BC(&two, &three, actions[y]);
ExprNode BCD(&BC, &four, actions[z]);
ExprNode ABCD(&one, &BCD, actions[x]);
if (actions[x] == DIV && BCD.eval() == 0)
break;
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}
// a ? (b ? (c ? d))
case 4: {
ExprNode CD(&three, &four, actions[z]);
ExprNode BCD(&two, &CD, actions[y]);
ExprNode ABCD(&one, &BCD, actions[x]);
if ((actions[y] == DIV && CD.eval() == 0) ||
(actions[x] == DIV && BCD.eval() == 0))
break;
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}
}
}
}
}
}
}
return 0;
}