运维开发网
广告位招商联系QQ:123077622
 
广告位招商联系QQ:123077622

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

运维开发网 https://www.qedev.com 2020-07-29 14:49 出处:网络 作者:运维开发网整理
我想从字符串中删除“un-partnered”括号. 即,在字符串中的某个地方,所有(除非它们后面跟着,否则应该删除).同样地,所有)之前都没有(字符串中的某个地方应该被移除). 理想情况下,算法也会考虑嵌套. 例如.: "(a)".remove_unmatched_parents # => "(a)" "a(".remove_unmatched_parents # => "a" ")a(".re
我想从字符串中删除“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),即使开销相对较高

快乐的编码.

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消