You are given a string that may contain any number of parentheses “(“ and “)”. Remove from the string the minimum number of parentheses so that the remaining parentheses are balanced.

Consider the following examples.

Input. The input file consists of one or more input strings, each on a single line. The input file is terminated by an EOF character. Consider the following example.

Output. The output file consists of an output string for each input line, each on a separate line. For example, the following output corresponds to the previous example input.

# Solution

The time and space complexity of the proposed solution are both O(n).

Consider the string ())( from left to right. Given that the first position is an opening parenthesis, remember that position in stack of opening parentheses that are unmatched op.

The second position is a closing parenthesis. We match it with the opening parenthesis that we found before and therefore remove the opening parenthesis from op.

The third position is again a closing parenthesis. This time we don’t have an opening parenthesis that matched and so we remember this position for later deletion in list dl.

The fourth and last position is an opening parenthesis. We remember that parenthesis in op like before.

We don’t have any more parenthesis to match that last opening parenthesis because we are at the end of the string. So, it makes sense to remove that last opening parenthesis together with anything in list dl. By doing so we get string (), a balanced string with the minimum number of parentheses removed.