I'm trying to write a function which get:

1. An integer. (s)
2. A list with integers separated by math symbols.(L)

By using recursion to determinate if the value of s can be calculate from the list by placing braces. Any ideas for a solution? I thought about using eval() function.

for example: L = [6,'-',4,'*',2,' ',3] s=10 Return: True, since: (6-4)*(2 3)=10

L = [6,'-',4,'*',2,' ',3] s=1 Return: True, since: (6-(4*2)) 3=1

L = [6,'-',4,'*',2,' ',3] s=100 Return: False, since there is no valid way to place braces in L which will lead to a solution of 100.

Thanks :)

CodePudding user response：

Let's describe the recursion in words, I think it is better to understand, we just need to define exactly what it does, it is really like induction.

rec function: get an input a list of numbers and return all the combinations of braces(examples later).

base: list with one element, for example [3], the function return (3) which is the only combination. or list with 3 element which simply returns (2 3)

assumption: we can solve it for a list of size N -2, for your example:[6,'-',4,'',2,' ',3] N = 7, so we can solve it for list with size 5 [4,'',2,' ',3] and we will get all the combinations:

1. (4*2) (3)
2. (4) * (2 3)

Step: solve it for N! what we need to do is to go over all the combination we got from the rec call(if we are on N = 7, its simply 1 and 2 from the example) and we only need to do the following things for each combination: put the current number next to the most left number and operate on it, or put it before the braces and put braces on all the expressions, for our example:

from option 1 we get 2 new options

6 -( (4*2) (3) )

(6 - 4*2) (3)

from option 2 we get 2 new options

(6-4) * (2 3)

6 - ( (4) * (2 3))

now the rec function returned all the combinations, we can call eval on each of them to check the result

CodePudding user response：

Full app below.
Works with any formula length. Parenthesis give order of operators, so we test all combinations.
Testing all permutations of n operators is n!
with 3 operators as in sample it's 6 tests.
for 8 operators, it will be 40320 ...
The code doesn't stop when the searched value is found as it could be several manner to obtain the same result.

All possible results are shown at the end.
For the given formula : ---- all possible results : {1, 7, 10, -14, -5}

Enjoy

from itertools import permutations

formula = [6,'-',4,'*',2,' ',3] ;
searchedValue = 10 ;

# operators are on odd positions . 
operatorsPositions = list(range(1,len(formula),2)) # [1, 3, 5]
# prepare all permutations eq all parenthesis order . return an array of tuple
permut = list(permutations(operatorsPositions))
print("**** {0} permutations to be tested ****".format(len(permut)))
print(permut)


# around an operator , two operands . return result
def calcAround(aFormula,position):
 op1 = aFormula[position -1]
 op2 = aFormula[position  1]
 operator = aFormula[position]
 # optional trace operation
 # print("calculate ({0:2d} {1} {2:2d})".format(op1,operator,op2));
 if (operator == "-"): return op1-op2;
 if (operator == " "): return op1 op2;
 if (operator == "*"): return op1*op2;
 if (operator == "/"): return op1/op2;
 #--------------------

# 'op1', 'operator', 'op2'  replaced by result in formula
def reduceAtPosition(someformula,position):
    result = calcAround(someformula,position);
    formulaNew =[];
    for i in range (0,position-1): formulaNew.append(someformula[i]);
    formulaNew.append(result);
    for i in range (position 2,len(someformula)):formulaNew.append(someformula[i]);
    return formulaNew;

# ------- main part --------
#  set to store unique possible results 
allResults = set(())
# try each permutation of operators order 
for aTest in permut: 
  aPermut = list(aTest) # better to have an array in place of tuple
  print('----------------')
  # make a new copy each tour 
  lTempo = formula.copy()
  print("operators sequence: {0}".format(aPermut))

  while(len(aPermut)>0):
    print(lTempo)
    anOpIndice = aPermut[0]
    lTempo = reduceAtPosition(lTempo,anOpIndice);
    # remove first done 
    aPermut = aPermut[1:]  
    for i in range(0,len(aPermut)):
      if (aPermut[i]>anOpIndice): aPermut[i] -= 2
  # 
  final = lTempo[0]
  print("result: {0}".format(final))
  # to respond to question 
  if(final == searchedValue): 
    print('*** found {0} with order or operators positions: {1} '.format(final,aTest))
  
  allResults.add(final)
print('---- all possible results : {0}'.format(allResults))

Console results:

**** 6 permutations to be tested ****
[(1, 3, 5), (1, 5, 3), (3, 1, 5), (3, 5, 1), (5, 1, 3), (5, 3, 1)]
----------------
operators sequence: [1, 3, 5]
[6, '-', 4, '*', 2, ' ', 3]
[2, '*', 2, ' ', 3]
[4, ' ', 3]
result: 7
----------------
operators sequence: [1, 5, 3]
[6, '-', 4, '*', 2, ' ', 3]
[2, '*', 2, ' ', 3]
[2, '*', 5]
result: 10
*** found 10 with order or operators positions: (1, 5, 3) 
----------------
operators sequence: [3, 1, 5]
[6, '-', 4, '*', 2, ' ', 3]
[6, '-', 8, ' ', 3]
[-2, ' ', 3]
result: 1
----------------
operators sequence: [3, 5, 1]
[6, '-', 4, '*', 2, ' ', 3]
[6, '-', 8, ' ', 3]
[6, '-', 11]
result: -5
----------------
operators sequence: [5, 1, 3]
[6, '-', 4, '*', 2, ' ', 3]
[6, '-', 4, '*', 5]
[2, '*', 5]
result: 10
*** found 10 with order or operators positions: (5, 1, 3) 
----------------
operators sequence: [5, 3, 1]
[6, '-', 4, '*', 2, ' ', 3]
[6, '-', 4, '*', 5]
[6, '-', 20]
result: -14
---- all possible results : {1, 7, 10, -14, -5}