The Parentheses Problem
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.
"()())()" -> "()()()" or "(())()"
"(bla)(ble))(bli)" -> "(bla)(ble)(bli)" or "(bla(ble))(bli)"
")(" -> ""
")))" -> ""
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.
()())()
(bla)(ble))(bli)
)(
)))
(helo)())
(((((
(((()((
)()
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.
()()()
(bla)(ble)(bli)
(helo)()
()
()
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
.
())(
0123
|
V
op: 0
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
.
())(
0123
*
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
.
())(
0123
|
V
dl: 2
op:
The fourth and last position is an opening parenthesis. We remember
that parenthesis in op
like before.
())(
0123
|
V
dl: 2
op: 3
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.
Ruby implementation
#!/usr/bin/env ruby
def balance s
op = [] # opening parentheses
dl = [] # delete these indexes later
s.chars.each_with_index do |c, i|
if c == '(' # `c` is an opening parenthesis
op << i # that we have to remember.
elsif c == ')' # `c` is a closing parenthesis
if op.length == 0 # that does not match an opening parenthesis
dl << i # and therefore we will delete later
else # that corresponds to an opening parenthesis
op.pop # and therefore we forget about both
end
end
end
dl += op # delete later all unmatched opening/closing parentheses
r = '' # result string
di = 0 # index in dl
s.chars.each_with_index do |c, i|
if di < dl.length and dl[di] == i # either skip this character
di += 1
else # or not
r += c
end
end
return r
end
while true
s = readline.strip rescue break
puts balance s
end