Curly brackets Reversals Count Finder

1 Reply

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])
  • Set countOfOpenedBrackets = 0 and countOfClosedBrackets
  • Iterate till stack is not empty
    • If stack.pop == '{' then
      • countOfOpenedBrackets++
    • Else
      • countOfClosedBrackets++
  • 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
Author: Hrishikesh Mishra