(Python)
# coding=utf-8
.
import itertools
.
.
def all_expressions(generic_expression, operation_combinations):
...."""
....Merges a source expression and combinations of binary operators to generate a list of all possible expressions.
....@param ((str, )) operation_combinations: all combinations of binary operators to consider
....@param str generic_expression: source expression with placeholder binary operators
....@rtype: (str, )
...."""
....expression_combinations = []
....for combination in operation_combinations:
........expression_combinations.append(generic_expression.format(*combination))
....return expression_combinations
.
.
def all_bracketings(expr):
...."""
....Generates all possible permutations of parentheses for an expression.
....@param str expr: the non-bracketed source expression
....@rtype: str
...."""
....if len(expr) == 1:
........yield expr
....else:
........for i in range(1, len(expr), 2):
............for left_expr in all_bracketings(expr[:i]):
................for right_expr in all_bracketings(expr[i + 1:]):
....................yield "({}{}{})".format(left_expr, expr[i], right_expr)
.
.
def num_valid_expressions(num_digits):
...."""Perform all calculations with the given operations and in the range of digits specified.
....@param int num_digits: the number of digits in the expression
....@rtype: int
...."""
....operations = ["+", "-", "*", "/"]
....digit = 9
....operation_iterable = itertools.product(*[operations] * (num_digits - 1))
....operation_combinations = []
....valid_expression_count = 0
....template = " ".join(str(digit) * num_digits)
....for operation in operation_iterable:
........operation_combinations.append(operation)
....for bracketed_expression in all_bracketings(template):
........for expression in all_expressions(bracketed_expression.replace(" ", "{}"), operation_combinations):
............try:
................eval(expression)
................valid_expression_count += 1
............except ZeroDivisionError:
................pass
....return valid_expression_count
.
.
if __name__ == "__main__":
....min_num_digits = 1
....max_num_digits = 6
....operation_set = ["+", "-", "*", "/"]
....for num in range(min_num_digits, max_num_digits + 1):
........print(num_valid_expressions(num))
|