-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathStack-Minimum bracket Reversal
79 lines (73 loc) · 1.96 KB
/
Stack-Minimum bracket Reversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
For a given expression in the form of a string, find the minimum number of brackets that can be reversed in order to make the expression balanced. The expression will only contain curly brackets.
If the expression can't be balanced, return -1.
Example:
Expression: {{{{
If we reverse the second and the fourth opening brackets, the whole expression will get balanced. Since we have to reverse two brackets to make the expression balanced, the expected output will be 2.
Expression: {{{
In this example, even if we reverse the last opening bracket, we would be left with the first opening bracket and hence will not be able to make the expression balanced and the output will be -1.
Input Format :
The first and the only line of input contains a string expression, without any spaces in between.
Output Format :
The only line of output will print the number of reversals required to balance the whole expression. Prints -1, otherwise.
Note:
You don't have to print anything. It has already been taken care of.
Constraints:
0 <= N <= 10^6
Where N is the length of the expression.
Time Limit: 1sec
Sample Input 1:
{{{
Sample Output 1:
-1
Sample Input 2:
{{{{}}
Sample Output 2:
1
************************************************Code**********************************************
import java.util.Stack;
public class Solution {
public static int countBracketReversals(String input) {
if(input.length()%2!=0)
return -1;
Stack<Character> stk = new Stack<>();
for(int i=0;i<input.length();i++)
{
if(input.charAt(i)=='{')
{
stk.push('{');
}
else if(input.charAt(i)=='}')
{
if(stk.isEmpty() || stk.peek()=='}')
{
stk.push('}');
}
else if(stk.peek()=='{')
{
stk.pop();
}
}
}
int cnt=0;
while(stk.size()!=0)
{
char c1=stk.pop();
char c2=stk.pop();
if(c1==c2)
{
if(c2=='{')
c2='}';
if(c1=='}')
c1='{';
cnt++;
}else
{
c1='{';
c2='}';
cnt++;
cnt++;
}
}
return cnt;
}
}