Validating Braces Placement for Expression Evaluation

In summary, the code is written to match the problem given the inputs, and it has a time-complexity of ## O(n!) ##.
  • #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:
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,
1638350047610.png


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:
Physics news on Phys.org
  • #2
Look up the Catalan numbers. https://en.wikipedia.org/wiki/Catalan_number The number of different expressions you get with n operators, is Cn.
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!.
 
  • Like
Likes CGandC
  • #3
Here's an example of the recursion tree for the example '6-4x2+3':
1638369970520.png

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?
 
Last edited:
  • #4
@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.
 
Last edited:
  • Like
Likes CGandC
  • #5
CGandC said:
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}) ##?
 
  • #6
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?
 
  • #7
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.
 
  • #8
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.
 
  • #9
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?
 
  • #10
CGandC said:
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 :biggrin:

Having said that, I agree with @willem2: the number of partitions you should be testing is the Catalan number ## C_n ##.
 
  • Like
Likes CGandC
  • #11
Thanks for the help, I have enough explanations now that will indeed satisfy my professor :) that'd be all.
 

Related to Validating Braces Placement for Expression Evaluation

1. What is the purpose of validating braces placement for expression evaluation?

The purpose of validating braces placement for expression evaluation is to ensure that mathematical or logical expressions are correctly evaluated according to the rules of operator precedence. Braces, or parentheses, are used to group sub-expressions and can greatly affect the final result if not placed correctly.

2. How is the validity of braces placement determined?

The validity of braces placement is determined by checking if each opening brace has a corresponding closing brace in the correct position. This is typically done using a stack data structure, where opening braces are pushed onto the stack and closing braces are matched against the top element of the stack. If the stack is empty at the end, the braces are considered valid.

3. What happens if braces placement is not validated?

If braces placement is not validated, the expression may be evaluated incorrectly, leading to incorrect results. This can be particularly problematic in complex mathematical or logical expressions where the order of operations is crucial. In some cases, the expression may even be considered invalid and result in an error.

4. Can braces placement be validated for all types of expressions?

Yes, braces placement can be validated for all types of expressions, including mathematical, logical, and even programming language expressions. The rules for operator precedence may vary depending on the type of expression, but the basic principle of validating braces placement remains the same.

5. How can I validate braces placement for expression evaluation?

There are various methods and algorithms for validating braces placement, but one common approach is to use a stack data structure. This involves iterating through the expression and pushing opening braces onto the stack and matching closing braces against the top element of the stack. If the stack is empty at the end, the braces are considered valid. There are also various online tools and libraries available that can assist with validating braces placement.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
3
Views
974
  • Engineering and Comp Sci Homework Help
Replies
12
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Programming and Computer Science
2
Replies
55
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
Replies
1
Views
1K
  • Special and General Relativity
3
Replies
75
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
660
  • Engineering and Comp Sci Homework Help
Replies
24
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Back
Top