Algorithm: (Dynamic Programming with a little twist)

Let S(i) = set of all "reasonable" result that can be created with "i" number of DIGIT

Let B(i) = set of all numbers that can be created with "i" number of of DIGIT without using any operation. (i.e. for i = 1, DIGIT = 4, 0.4, 0.4' = 0.444444...)

S(i) = B(i) Union {Binary operation on S(j) and S(k) where j+k=i} Union {Unary operation on S(i)}

Data Structure

S(i), the set of all valid number, is store in a balanced binary search tree.

Each number is hashed to a pointer to a node (that represent its equation). In other words, every nodes is indexed by a hash table. Each node has the following properties,

Member:

priority: store the priority of each entry, this is used to determine bracket and break tie

entry: store the content, such as "*", "fact", "44", etc.

ptrLEFT: pointer to left node

ptrRIGHT: pointer to right node

NOTE: this is not a binary tree, but an acyclic graph, because a single node often has multiple parent

This data structure to express equation is prefered over binary tree

Use a lot less memory

Much easier to update when a simpler representation is found. For instance

Assuming we have, 20 = 4 / sqrt(4%), and 80 = 4 * 20 = 4 * (4 / sqrt(4%))

In my program, when 20 is updated to 20 = 4! - 4, everything else that use 20 is updated automatically, thus 80 = 4 * (4! - 4). Because 80 is a node where "entry = *" "ptrLEFT = pointer to node 4" "ptrRIGHT = pointer to node 20"