Curly brackets Reversals Count Finder
Given a string S 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.
Examples
- }{{}}{{{ – 3
- {{}}}} – 1
- {{}{{{}{{}}{{ – -1
- {{{{}}}} – 0
Algorithm:
- Base case: When string length is odd return -1
- Take a stack to keep opening and invalid brackets
- Iterate string from beginning to end
- If
stack.top == '{' and string[i] == '}'
then,stack.pop
- Else
stack.push(string[i])
- If
- Set
countOfOpenedBrackets = 0 and countOfClosedBrackets
- Iterate till stack is not empty
- If
stack.pop == '{'
thencountOfOpenedBrackets++
- Else
- countOfClosedBrackets++
- If
- Return (Math.ceil(countOfClosedBrackets / 2) + Math.ceil(countOfOpenedBrackets / 2))
- Why we need Math.ceil, think for this “}{“
Latest Source Code:
Github: CountTheReversals.java
Output:
Count The Reversals of }{{}}{{{ : 3 Count The Reversals of {{}}}} : 1 Count The Reversals of {{}{{{}{{}}{{ : -1 Count The Reversals of {{{{}}}} : 0