Validating Braces Placement for Expression Evaluation

[CGandC]

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:
Mentor note: replaced icode tags with code=python and \code pair.

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?

 

[willem2]

Look up the Catalan numbers. https://en.wikipedia.org/wiki/Catalan_number The number of different expressions you get with n operators, is C_n.
You probably need to multiply the time with a further factor n, to account for the increasing running time of eval() and the string expressions, as the string becomes larger, but you should still be below n!.

 

[CGandC]

Here's an example of the recursion tree for the example '6-4x2+3':

The value inside each node is the string length from index $i$ to index $j$, near each node I wrote the corresponding string that is looked at in the loop. However, I haven't included any time-complexity information in the diagram.

It seems at there will be $\lfloor n/2 \rfloor$ levels ( since we disregard looking at one operation of the string at each level , therefore we'll look at strings of length at-most $n-2*i$ at level $i$ of the tree. )I understood how to analyze the worst case if the time-complexity of each node were $O(1)$, but in this case each node does not necessarily perform $O(1)$ ( since we have a for-loop and we use 'eval'). Suppose the time complexity of a node representing string of length $l$ is $O(l*n)$ ( it is lower, but for the sake of simplicity, we iterate $O(l)$ times and we create a string of length $O(n)$ at each iteration [ where $n$ is length of string ] ).
How can I take care of these factors in the total calculating of the time-complexity of the algorithm?

 

[Mark44]

@CGandC, I fixed your python code in post #1. For extended blocks of code, don't use icode tags. Those are for short bits of code (one line or less). Instead use [code=python] and [/code] for Python code and similar for other languages.

 

[pbuk]

How can I take care of these factors in the total calculating of the time-complexity of the algorithm?

I haven't checked any of your results (that is for you to do), but how much worse do you think $O(n ! n)$ is than $O(n!)$? What about $O(n ! n^{10^9})$?

 

[CGandC]

Well, $O(n!n) \notin O(n!)$ , but that's an upper bound, I need to find a tighter upper bound that will show me my implementation's complexity is at-worst case $O(n!)$
I think the recurrence relation of the above algorithm can be written almost as:
$T(n) = 2 \cdot n_0 \cdot ( T(1) + T(3) + ... + T( n-2) )$ where $n_0$ is the length of $L$.
Base case is $T(1) = 1$
But I haven't learned yet how to solve such recurrence relations.
But do you think this is the correct recurrence relation?

 

[pbuk]

Ah, it's a while since I worked with the theory. I suppose from the definition it is true that $O(n!n) \notin O(n!)$, however this doesn't say anything meaningful about algorithmic complexity: run times that increase like $(n + 1)!$ are no more troublesome than those increasing like $n!$, and $(n + 1)! > n!n$.

None of this helps with your answer I'm afraid, I guess it depends on how rigorous vs practical your professor is. For practical purposes, if we are performing an operation $n!$ times (or $(n+1)!$) then that is the problem whether that operation is constant, linear or any polynomial time.

 

[CGandC]

Here's my analysis for the upper-bound on the time-complexity here:
Suppose that each father node will link to at-most $n-1$ son nodes. And suppose each node in the tree does $O(n)$ work ( that is, they have time complexity as the root-node of the tree ). Thus,
at level 0 there'll be $O(n)$ work
at level 1 there'll be $O(n)*(n-1)$ work ( since there are $n-1$ nodes at-most in this this level and each does $O(n)$ work )
at level 2 there'll be $O(n)*(n-1)*(n-2)$ ( each node in level 1 splits at-most into $n-2$ nodes so the total nodes at level 2 will be $(n-1)*(n-2)$ )

so far the total complexity is $O(n)*(n-1)*(n-2) + O(n)*(n-1) + O(n)$

Continuing in this way, the total time complexity is $O(n * \sum_{k=0}^{n-1} (n-i)! )$ ( we suppose the tree is at-most of height $n$ ).

But I don't know what the term in the sum comes out... so that's a new problem. If it is is true that $O(n * \sum_{k=1}^{n-1} (n-i)! ) \in O(n!)$ then my problem's solved.

 

[CGandC]

Further inquiring the answer by @willem2 , I think I have an upper-bound:
At-each level it is satisfied that an upper-bound on the number of nodes is at-most $\cdot 2^{n+i}$ nodes, there are $n/2$ levels , each level does $O(n)$ work so an upper-bound on the time-complexity is:
$\sum_{k=0}^{n/2} \sum_{j=0}^{2^{n+k}} O(n) = O( n \cdot \sum_{k=0}^{n/2} 2^{n+k} ) = O( 2^n \cdot n \cdot \sum_{k=0}^{n/2} 2^{k} ) = O( n\cdot 2^{3n/2} ) \in O(n\cdot 4^n) \in O(n!)$

What do you think?

 

[pbuk]

What do you think?

With the caveats that I haven't checked that your algorithm works or that your statements regarding its complexity are correct, I think you have probably done enough to satisfy your professor

Having said that, I agree with @willem2: the number of partitions you should be testing is the Catalan number $C_n$.

 

[CGandC]

Thanks for the help, I have enough explanations now that will indeed satisfy my professor :) that'd be all.