How can I solve The Riddle of Nine 9's programmatically?

Question

How can I solve this riddle programmatically? Could someone help me with some pseudo-code or something?

Nine 9s

Combining nine 9's with any number of the operators +, -, *, /, (, ), what is the smallest positive integer that cannot be expressed?

Hints:

1. The answer isn't zero. You can express zero like this: (9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9). Also, zero isn't a positive integer.

2. The answer isn't one. You can express one like this: 9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9

3. It's not a trick question.

4. Be sure to handle parentheses correctly.

Notes:

• You cannot use exponentiation.
• You cannot concatenate (for example, put two 9's together to make 99).
• The - operator can be used in either its binary or unary form.
• Assume base 10.

---

This is actually a famous puzzle and there are probably many solutions hovering around the internet. I am not sure if any of them is correct or not. Does anybody have a well explained solution?

Answer 1

The answer is 195, here is some Python code that simply builds up all possible expressions by forming new expressions from exp1 OP exp2. It runs in 0.165s on my PC.

exp = [set() for _ in xrange(10)]
exp[0].add(0)
exp[1].update([9, -9])
for i in xrange(1, 10):
  for a in list(exp[i]):
    for j in xrange(i, 10):
      for b in list(exp[j-i]):
        exp[j].update([a+b, a-b, a*b])
        if b != 0:
          exp[j].add(a/b)

n = 0
while n in exp[9]:
  n += 1
print n

---

EDIT: If the answers must be exact integers (and not just the rounded result of integer division) then a check must be done when division is done.

    if ((b != 0) and ((a/b) == float(a)/b)):
      exp[j].add(a/b)

Under this interpretation of the rules, the new answer is 138. (the existing version computes 1386/10 [or -1386/-10] and gets 138)