My solution to RubyQuiz #7 in C++. http://rubyquiz.com/quiz7.html

RubyQuiz7.cpp

#include <vector>
#include <array>
#include <unordered_map>
#include <string>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <utility>
#include <memory>
#include <functional>


// Type of an expression ("AST node", if you like)
enum NodeType {
	Add,
	Subtract,
	Multiply,
	Divide,
	Number
};

// Basic structure for working with rational numbers
struct Rational {
	int num;
	int denom;
};

// Simplify the fraction represented by 'r'
static Rational simplify(Rational r)
{
	// it's easier to work with non-negative numbers only
	// so we first note if the value of the fraction is negative,
	// and then we take its absolute value
	auto sign = [](int n) { return (n > 0) - (n < 0); };
	int s = sign(r.num) != 0 and sign(r.num) == -sign(r.denom) ? -1 : +1;

	r.num = std::abs(r.num);
	r.denom = std::abs(r.denom);

	// Then we enumerate all possible divisors of both the
	// numerator and the denominator, and if they have a
	// common divisor, then we use it to divide both.
	for (int i = 2; i <= r.num or i <= r.denom; i++) {
		while (r.num % i == 0 and r.denom % i == 0) {
			r.num /= i;
			r.denom /= i;
		}
	}

	// Put back original sign
	r.num *= s;
	return r;
}

// Pretty-print a (potentially integer-valued) fraction
static std::ostream &operator<<(std::ostream &os, Rational r)
{
	os << r.num;

	if (r.denom != 1) {
		os << "/" << r.denom;
	}

	return os;
}

// An AST node, representing an expression (operation or number).
struct Node {
	const NodeType type;

	// active if type != Number
	const struct {
		std::unique_ptr<Node> left;
		std::unique_ptr<Node> right;
	} children;

	// active if type == Number
	const Rational numval;

	// Construct a node from an integer
	Node(int n) : type(Number), children { nullptr, nullptr }, numval { n, 1 } {}

	// Construct a node from a fraction
	Node(int num, int denom) : type(Number), children { nullptr, nullptr }, numval { num, denom } {}

	// Construct a node from an operation and its two children
	Node(NodeType ptype, std::unique_ptr<Node> &&left, std::unique_ptr<Node> &&right) :
		type(ptype),
		children { std::move(left), std::move(right) },
		numval { 0, 0 }
	{}

	// Pretty-print the node. If it's a Rational, then
	// just print that; else print the left and right children
	// recursively (properly parenthesized based on precedence rules
	// as necesary), and print the symbol of the operation in between.
	void print(std::ostream &os) const {
		if (type == Number) {
			os << numval;
		} else {
			struct opspec {
				const char *symbol;
				int precedence;
			};
			static std::unordered_map<NodeType, opspec, std::hash<unsigned>> typemap {
				{ Add,      { " + ", 50 } },
				{ Subtract, { " - ", 50 } },
				{ Multiply, { " * ", 60 } },
				{ Divide,   { " / ", 60 } },
				{ Number,   { nullptr, 100 } }
			};

			if (typemap[children.left->type].precedence < typemap[type].precedence) {
				os << "(";
				children.left->print(os);
				os << ")";
			} else {
				children.left->print(os);
			}

			os << typemap[type].symbol;

			if (typemap[children.right->type].precedence <= typemap[type].precedence) {
				os << "(";
				children.right->print(os);
				os << ")";
			} else {
				children.right->print(os);
			}
		}
	}

	// Evaluate a node
	// If the node is a Rational, simplify and return it,
	// else recursively evaluate both children and perform
	// the appropriate operation
	Rational evaluate() const {
		if (type == Number) {
			return simplify(numval);
		}

		static std::unordered_map<NodeType, std::function<Rational(Rational, Rational)>, std::hash<unsigned>> ops {
			{ Add, [](Rational a, Rational b) -> Rational { return { b.denom * a.num + a.denom * b.num, a.denom * b.denom }; } },
			{ Subtract, [](Rational a, Rational b) -> Rational { return { b.denom * a.num - a.denom * b.num, a.denom * b.denom }; } },
			{ Multiply, [](Rational a, Rational b) -> Rational { return { a.num * b.num, a.denom * b.denom }; } },
			{ Divide, [](Rational a, Rational b) -> Rational { return { a.num * b.denom, a.denom * b.num }; } }
		};

		auto rv = ops[type](children.left->evaluate(), children.right->evaluate());
		return simplify(rv);
	}

};

// Treats 'numbers' as a set of integers;
// generates all possible combinations of
// the four arithmetic operations that can
// be formed by using each number exactly once.
static std::vector<std::unique_ptr<Node>>
build_trees(const std::vector<int> &numbers)
{
	// If there's only one element, then the only possible
	// tree is the number itself.
	if (numbers.size() == 1) {
		std::vector<std::unique_ptr<Node>> rv;
		rv.push_back(std::unique_ptr<Node>(new Node(numbers[0])));
		return rv;
	}

	std::vector<std::unique_ptr<Node>> rv;

	const std::array<NodeType, 4> types { Add, Subtract, Multiply, Divide };
	for (auto type : types) {
		for (std::size_t i = 0; i < numbers.size(); i++) {
			// Else, the next possible set of trees is formed
			// by removing one of the numbers from the "set",
			// treating it as the left child of our tree,
			// then generating all the possible trees from
			// the new, smaller set, and treating each of
			// the returned trees as the right child of our tree.
			// Repeat this with each of the 4 operation types
			// (which will be the node type of the returned trees).
			auto children_numbers(numbers);
			children_numbers.erase(children_numbers.begin() + i);

			auto rights = build_trees(children_numbers);

			for (auto &&right : rights) {
				auto left = std::unique_ptr<Node>(new Node(numbers[i]));
				rv.push_back(std::unique_ptr<Node>(new Node(type, std::move(left), std::move(right))));
			}
		}
	}

	return rv;
}


// Test
int main()
{
	// The number we want to reach
	const int target = 926;

	// The set of numbers we're allowed to use
	// TODO: generate trees for all subsets,
	// since we are not obliged to use every number
	auto trees = build_trees({ 75, 2, 8, 5, 10, 10 });

	// Evaluate each expression tree
	for (const auto &tree : trees) {
		auto v = tree->evaluate();
		if (v.num == target and v.denom == 1) {
			tree->print(std::cout);
			std::cout << " = " << tree->evaluate() << "\n";
			// Uncomment this if you don't want all solutions
			// break;
		}
	}

	return 0;
}