Minimum operations to form a correct bracket expression

The Problem

   We have an expression which consists of opening and closing brackets '('  and ')'. We have 1 operation. We can change any bracket into its reversed one (aka changing this  ')' to this '(' and vice versa). We need to perform the minimum number of operations which can turn it into a correct expression. 

The Solution

 We can solve this using simple Stack of C++ STL. (You can find more info on stack go here). The first thing we need to do is to remove every single correct bracket expression from our given expression. 

For example

1 2 3 4 5 6

} { } { } }

The 2nd and 3rd form a correct expression so we don't need them, that means we can remove them, the same goes for the elements 4 and 5. We will be down to 2 brackets ) ). 

Here is how we will do that

Obviously we can consider a expression correct if there are 2 brackets '( '  and ') ' following one another. For example

 ( ( ) )

When we remove the middle 2 brackets we will be down to an expression ( ) which is also correct.

So here is how stack will help us. We loop over our given string, if the current element is ')' and the top element of the stack is '(' that means that those 2 are correct and we don't need them, otherwise we push teh current element to the stack.

for( i from 0 to the size )

 if(s[i] is ')' and stack.top()=='(')

        continue;

   else

       stack.push(s[i]);

Now we down to a wrong expression which we need to change with minimum number of operations.

I can guarantee that it has this form )))))((((((((( or in other words there are some of this brackets ' )' and after there are some brackets '('. Suppose there are N brackets ')' and M brackets '('. First of all we all understand that the given string must have an even number of elements and the string we just got must have even number of elements as well. Here are 2 things possible If both N and M are even. IN this case we need (N+M)/ operations (by turning the half of those brackets '(' into ')' and turning the half of those ')' brackets into this '(' this, example ))))(( we cant switch the first 2 brackets thus removing the first 4 elements as correct expressions and then change the last element and we get a total correct expression in (N+M)/2 steps. If N and M are both odd ( there is no other case they both either have to be even or odd). Example )))((( then we should switch the middle elements so that we can remove both of them and we will be down to the case were N and M are both even. The total number of operations in this case would be (N+M-2)/2 + 2.

There is a good task in SPOJ which has the same question as this problem.

http://www.spoj.com/problems/ANARC09A/

If you want the full source code of this go here.