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

发布时间：2020-12-17 01:48:56 所属栏目：百科来源：网络整理

导读：我想从字符串中删除“un-partnered”括号. 即,在字符串中的某个地方,所有(除非它们后面跟着,否则应该删除).同样地,所有)之前都没有(字符串中的某个地方应该被移除). 理想情况下,算法也会考虑嵌套. 例如.： "(a)".remove_unmatched_parents # = "(a)""a(".rem

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

即,在字符串中的某个地方,所有(除非它们后面跟着,否则应该删除).同样地,所有)之前都没有(字符串中的某个地方应该被移除).

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

例如.：

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

解决方法

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

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

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

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

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

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

快乐的编码.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!