从字符串中删除不匹配的括号

Question

我想从字符串中删除"un-partnered"括号.

也就是说,(除非它们跟)在字符串中的某处,否则应该删除所有内容.同样,应该删除字符串中某个地方)之前的所有内容(.

理想情况下,算法也会考虑嵌套.

例如:

"(a)".remove_unmatched_parents # => "(a)"
"a(".remove_unmatched_parents # => "a"
")a(".remove_unmatched_parents # => "a"

Answer 1

而不是正则表达式,或许考虑下推自动机.(我不确定Ruby正则表达式是否可以处理这个,我相信Perl可以).

一个(非常简单的)过程可能是:

对于输入字符串中的每个字符:

1. 如果它不是'('或')',那么只需将它附加到输出
2. 如果它是'('增加一个seen_parens计数器并添加它
3. 如果它是')' 并且 seen_parens> 0,则添加它并减少seen_parens.否则跳过它.

在该过程结束时,如果seen_parens> 0,则从末尾开始删除那么多parens.(此步骤可以使用堆栈或递归合并到上面的过程中.)

O(n)即使开销相对较高,整个过程也是如此

快乐的编码.