Join Regular Classroom : Visit ClassroomTech

Bracket Validator – Infytq 2019 Solve

/ Miscellaneous / By

Problem: Find the place where the bracket doesn’t ends properly or the chain breaks.

Input Format: First line contains a single integer, the number of testcases n. Next n line contains a string consists of brackets.

(NOTE: The actual problem didn’t have the number of testcases as input. But for your better convenience we have worked with testcases.)

Sample Input:

3
())
[][][
{{[]}}}

Sample Output: 

3
6
7

Explanation: In the first input “())” third index the bracket closes but it doesn’t have any opening bracket (the chain breaks), the first bracket in position 1 is closed in the second position, Hence the output should be 3.

In the second example “[][][“, bracket in the 5th position opens but doesn’t close anywhere. Hence it returned the position where it should have closed (position of chain break) i.e. 6.

In the last example, the closing bracket in the 7th position is extra. It closes but doesn’t have any opening bracket of it (breaking of the chain). Hence it returned 7.

Solution: We strongly recommend you to try the problem first before moving to the solution.

# Solution of Bracket Validator problem in Python 
# www.codewindow.in 

def validator(str):     # Function validator to check
    st=[]
    count=0
    for a in str:
        if a=='[' or a=='{' or a=='(':
            st.append(a)
            count+=1
            continue
        
        if len(st)==0:
            return count+1
        x=st.pop()
        
        if a==']' and x=='[':
            count+=1
        
        elif a=='}' and x=='{':
            count+=1
        
        elif a==')' and x=='(':
            count+=1
        
        else:
            return count+1
    
    if len(st)==0:
        return 0
    else:
        return count+1

# Driver Code
test_case=int(input());     # Take number of testcases

while(test_case):
    str=input()
    print(validator(str))
    test_case-=1

Input:

3
())
[][][
{{[]}}}

Output:

3
6
7

Follow Us

You Missed