Statement

Do you remember Baby Bob? His older brother, Balanced Benjamin would like to give a gift to his brother. He has a string S of length N, where N is even. The string consists of N/2 opening brackets ("(") and N/2 closing brackets (")"). As Bob likes valid bracket sequences " and "+" characters can be inserted into it so that it becomes a valid mathematical expression. For example, "()(()(()))" is a valid bracket sequence., Benjamin would like to turn S into a valid bracket sequence by swapping (not necessarily adjacent) characters in S. Since he's less mathematically inclined than his younger brother, he asks for your help. Write a program that turns S into a balanced bracket sequence by swapping characters in S using the minimum number of swaps. If there are more than one way to do this, you can output any of them.