Given a string consisting only of opening and closing curly brackets '{' and '}' find
out the minimum number of reversals required to make a balanced expression.
If it cannot be balanced, then print -1.
Example 1:
4
}{{}}{{{
{{}}}}
{{}{{{}{{}}{{
{{{{}}}}
>> 3
>> 1
>> -1
>> 0
The above problem includes inputs T, exp representing testcases and expression.
Complexity Analysis :
def minReverse(exp):
if len(exp)%2!=0:
return -1
c=0
op=0
for e in exp:
if e=='}' and op==0:
op=1
c+=1
elif e=='}':
op-=1
else:
op+=1
if op%2!=0:
return -1
else:
return c+op//2
if __name__ == '__main__':
T = int(input())
for _ in range(T):
exp=input()
print(minReverse(exp))