Consider that in a reqular bracket sequence the amount of '(' and ')' must be equal. Let x be the amount of '(' and y be the amount of ')'. In case that x>y, you will have to pay the cost of placing ')' x-y times. In the opposite case, vice versa. Then let z be the amount of '?' left over. Just add z/2 * (c1+c2) where c1 and c2 are the costs of '(' and ')'. Because half will be opened and half will be closed. All of this assumes that a regular bracket sequence is achievable, so before this you just have to check if it actually is. If it is achievable, which is trivial to check, the greedy works because of the reasoning above.