Stop Them!

4

4 votes
Easy
Problem

The evil magician has sent his army to destroy you. you being the brilliant wizard decided to use evil magician's army against the evil magician himself. you are to calculate minimum number of soldiers you need to convert to neutralize the evil magician. If no army attacks you don't have to convert anyone. if two soldiers say Z are neutralised then [Z] is also neutralized (here Z is neutralized pair [] ). If S and T are both neutralised , then ST (the concatenation of the two) is also neutralised .

all of these strings are neutralised : [], [][], and [[][]]; But none of these: ][, [[][, nor [][.

INPUT

The input is a non-empty strings of opening and closing braces and nothing else. No string has more than 2000 braces. All sequences are of even length.

The last line of the input is made of one or more ’-’ (minus signs.)

OUTPUT

output consists of single integer N for each input line. N is the minimum number of operations needed to convert the given string into a balanced one.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first case both the braces should be converted to neutralize.

In second case the braces are already neutralized , so no change required.

In third case only one brase at second position is to be converted to neutralize the string.

Editor Image

?