- #1

CGandC

- 326

- 34

- Homework Statement
- Given a list L of positive numbers, among them the strings '+','*','-', we'll think of the list as a mathematical expression of addition, subtraction and multiplication between numbers.

For example, the list ##L ##=[6,'-',4,'*',2,'+',3] will represent the expression: 6-4*2+3 .

Given such a list ## L## and a whole number ## s ## evaluate if the number ##s## we'll want to find if there exists a way to place parenthesis on the mathematical expression that represents ## L ## such that the value of the expression according to the rules of parenthesis precedence will be equal to ## s ##.

For example, for the given ## L ## above and ## s= 10 ##:

(6-4)*(2+3) = 10

Also, we can get to ## s=1 ## by:

( 6 - ( 4*2 ) ) +3 =1

Implement the function valid_braces_placements(s,L) that recieves a whole number ## s ## and a list ## L ## as given above and returns True if there exists an appropriate parenthesis placement and returns False otherwise.

Note: the function must be of time complexity ## O(n!) ##.

- Relevant Equations
- Hint: one can use python's built-in function "eval"

( https://docs.python.org/3/library/functions.html#eval )

Note: it occurs that the even indexes in ## L ## ( start from 0 ) will always be positive integers, the odd indexes will be one of the strings '+','*' or '-' , and the list will be of odd length greater than or equal to 3

Here's what I've done:

Note: I'm not sure if the above code is properly indented in this site as in python's IDLE, the code is supposed to be as follows,

## (a_1' a_2' ... a_{k-1}' ) ## can be thought of

## a_k' ## can be thought of

## ( a_{k+1}'...a_n' ) ## can be thought of

I think the implementation I gave is correct ( I tried it on different inputs ) but I'm not sure if it's time complexity is ## O(n!) ##. I tried drawing the recursion tree and I got that there are ## n ## levels, each level ## i ## has ## n-i ## nodes, and the input to each node is an odd number. Yet, the work of each node ( time-complexity of each node ) is ## O(m) ## where ## m ## is the value in the node.

Basically what I did in the implementation is I looked at every possible legal parenthesis placement , which has to be of the form ## (A) p (B) ## where ## A ,B ## are expressions and ## p ## is an operation ( is one of +,-,* ) and eventually when I'm left with an expression without any operations in it, I'd evaluate the string to see if it matches ## s ##.

**Mentor note: replaced icode tags with code=python and \code pair.**
Python:

```
def valid_braces_placement(s, L):
if len(L)==0:
return False
string = ''
for element in L:
string = string + str(element)
D = ['+','-','*']
return valid_braces_placement_rec(s,string,0,len(L),D)def valid_braces_placement_rec(s,string,i,j,D):
if i >= j:
if eval(string)==s:
return True
else:
for k in range(i,j):
if string[k] in D:
st = string[0:i] + '(' + string[i:k] + ')' + string[k] + '(' + string[k+1:] + ')'
A = valid_braces_placement_rec(s,st,i+1,k,D) ## ( i ) + 1
B = valid_braces_placement_rec(s,st,k+4,j+2,D) ## ( k + 1 ) + 3
if A==True or B==True:
return True
return False
```

Note: I'm not sure if the above code is properly indented in this site as in python's IDLE, the code is supposed to be as follows,

**Reasoning**: Let ## \tau ## be a solution to the problem ## P(s,L) ##. ( ## P(s,L) ## stands for the problem above given the inputs ## s,L ## ) Then there has to exist a string ## a_1' a_2' ... a_{k-1}' a_i' a_{k+1}'...a_n' ## made from ## L ## plus parenthesis inside it, such that there exists index ## k ## such that ## s = eval( (a_1' a_2' ... a_{k-1}' ) a_k' ( a_{k+1}'...a_n' ) ) ## where ## a_k' ## is an operation belonging to ## \{ '+','-','*' \} ##.__The link between the reasoning and the algorithm implementation is that:__## (a_1' a_2' ... a_{k-1}' ) ## can be thought of

`A = valid_braces_placement_rec(s,L,st,i+1,k,D)`

( I had to start from index ## i+1 ## because I added a '(' parenthesis from the left to the string. similarly, the final index I look at is index ## k ## because I've added a ')' parenthesis to the left of the operation at index ## k ## )## a_k' ## can be thought of

`string[ k]`

( it is one of the operations '+','-','*' )## ( a_{k+1}'...a_n' ) ## can be thought of

`B = valid_braces_placement_rec(s,L,st,k+4,j+2,D)`

( I had to start from index ## k+4 ## because I added a 3 parenthesis from the start of the string and I want to look at the position right after the operation and right after the parenthesis '(' was added after it. for almost similar reasons the final index I'm looking at is index ## j + 2 ## )I think the implementation I gave is correct ( I tried it on different inputs ) but I'm not sure if it's time complexity is ## O(n!) ##. I tried drawing the recursion tree and I got that there are ## n ## levels, each level ## i ## has ## n-i ## nodes, and the input to each node is an odd number. Yet, the work of each node ( time-complexity of each node ) is ## O(m) ## where ## m ## is the value in the node.

Basically what I did in the implementation is I looked at every possible legal parenthesis placement , which has to be of the form ## (A) p (B) ## where ## A ,B ## are expressions and ## p ## is an operation ( is one of +,-,* ) and eventually when I'm left with an expression without any operations in it, I'd evaluate the string to see if it matches ## s ##.

**Question**: Can you please help as to determine the time-complexity of the above implementation? And if it does not satisfy ## O(n!) ## complexity, then how to change my code in order to be at the wanted time-complexity?
Last edited by a moderator: