テンパズルを解く

テンパズルを解くプログラムをPythonで書いた。

C:\>make10.py 1 1 5 8
8/(1-(1/5))
time: 0.0699999332428 s

のように使う。CPython 2.6で動作を確認した。
仕組みはいたって簡単で、後置記法の式を生成し計算して演算結果が10なら挿入記法に変換して表示するというもの。
そんなに複雑なことはしていないので詳しくは読めば分かる。
from __future__ import divisionとしているのがミソか。
ソースコードを以下に示す。

#!/usr/bin/env python
# coding: utf-8
from __future__ import division
def post2in(expr):
	stack = []
	for elem in expr:
		if elem in ('+', '-', '*', '/'):
			top = stack.pop()
			snd = stack.pop()
			stack.append('('+snd+elem+top+')')
		else:
			stack.append(str(elem))
	return stack.pop()[1:-1]

def gen_expr(nums, size, expr):
	if size - 1 == len(nums) == 0:
		yield expr
	else:
		result = []
		if size >= 2:
			for oper in ('+', '-', '*', '/'):
				for elem in gen_expr(nums[:], size - 1, expr+[oper]):
					yield elem
		for num in set(nums):
			copy = nums[:]
			copy.remove(num)
			for elem in gen_expr(copy, size + 1, expr+[num]):
				yield elem

def calc_postfix_notation(expr):
	stack = []
	for elem in expr:
		if elem == '+':
			stack.append(stack.pop() + stack.pop())
		elif elem == '-':
			stack.append(-stack.pop() + stack.pop())
		elif elem == '*':
			stack.append(stack.pop() * stack.pop())
		elif elem == '/':
			temp = stack.pop()
			if temp == 0: # division by zero
				return 0
			stack.append(stack.pop() / temp)
		else:
			stack.append(elem)
	return stack.pop()

def main():
	from time import time
	from sys import argv
	t = time()
	for expr in gen_expr(map(int, argv[1:]), 0, []):
		if calc_postfix_notation(expr) == 10:
			print(post2in(expr))
	print 'time:', time() - t, 's'

if __name__ == '__main__':
	main()