#!/usr/bin/env python2.2
# Copyright 2002 Matthew Mueller  
# include <GPL>
from __future__ import generators
import re

oporder = {
	'^':4,
	'/':3,
	'*':3,
	'+':2,
	'-':2,
}

def trysubs(numops, tspl):
	for i in range(numops):
		if i>0:
			p = oporder[tspl[(i-1)*2+1]]
		else:
			p = 0
		if i<numops-1:
			n = oporder[tspl[(i+1)*2+1]]
		else:
			n = 0
		c = oporder[tspl[i*2+1]]
		v = tspl[i*2] +	tspl[i*2+1] + tspl[i*2+2]
		if p>=c or n>c:
			v = '('+v+')'
		subtspl = tspl[:i*2] + [v] + tspl[i*2+3:]
		if numops<=2:
			aexpr = ''.join(subtspl)
			pexpr = re.sub(r'\^','**',aexpr) # ^ is xor, ** is pow.
			v = eval(pexpr)
			yield aexpr, v
		else:
			for r in trysubs(numops-1, subtspl):
				yield r

def foobar(exp, result):
	answers = {}
	spl = exp.split(' ')
	numops = len(spl)//2
	matches=totalmatches=total=0
	for exprstr, v in trysubs(numops, spl):
		total+=1
		if v==result:
			totalmatches+=1
			if exprstr not in answers:
				matches+=1
				answers[exprstr] = v
				print exprstr,'=',v
	print matches,'unique solutions(%s total)'%totalmatches,'out of',total,'possibilities'