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

Question

我想从字符串中删除“未配对”的括号。

即，所有 ( 都应该被删除，除非它们后面跟有 ) 字符串中的某处。同样，字符串中某处前面没有 ( 的所有 ) 都应该被删除。

理想情况下，算法也会考虑嵌套。

例如：

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

Answer 1

也许可以考虑下推自动机，而不是正则表达式。 （我不确定 Ruby 正则表达式是否可以处理这个问题，我相信 Perl 可以）。

一个（非常简单的）过程可能是：

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

1. 如果它不是“（”或“）”，则将其附加到输出
2. 如果它是“（”，则增加一个 saw_parens 计数器并添加它
3. 如果它是“)”并且 saw_parens > 0，添加它并减少 saw_parens。否则跳过它。

在该过程结束时，如果 saw_parens > 。 0 然后从末尾开始删除那么多括号。 （这一步可以使用栈或者递归的方式合并到上面的过程中。）

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

Happy编码。

Answer 2

下面使用oniguruma。如果您使用 ruby​​1.9，Oniguruma 是内置的正则表达式引擎。如果您使用的是 ruby​​1.8，请参阅：oniguruma。

更新

我太懒了，只是复制并粘贴别人的正则表达式。好像有问题。

所以现在，我自己写了。我相信现在应该可以了。

class String
    NonParenChar = /[^\(\)]/
    def remove_unmatched_parens
        self[/
            (?:
                (?<balanced>
                    \(
                        (?:\g<balanced>|#{NonParenChar})*
                    \)
                )
                |#{NonParenChar}
            )+
        /x]
    end
end

• (?regex1) 将（子）正则表达式 regex1 命名为 name，并使其可以被调用。
• ?g 将是代表 regex1 的子正则表达式。请注意，?g 并不代表与 regex1 匹配的特定字符串，而是代表 regex1 本身。事实上，可以将 ?g 嵌入到 (?...) 中。

更新2

这更简单。

class String
    def remove_unmatched_parens
        self[/
            (?<valid>
                \(\g<valid>*\)
                |[^()]
            )+
        /x]
    end
end

Answer 3

构建一个简单的 LR 解析器：

tokenize, token, stack = false, "", []

")(a))(()(asdf)(".each_char do |c|
  case c
  when '('
    tokenize = true
    token = c
  when ')'
    if tokenize
      token << c 
      stack << token
    end
    tokenize = false
  when /\w/
    token << c if tokenize
  end
end

result = stack.join

puts result

运行收益：

wesbailey@feynman:~/code_katas> ruby test.rb
(a)()(asdf)

我不同意人们修改 String 类，因为你永远不应该打开标准类。正则表达式对于解析器来说非常脆弱并且难以支持。我无法想象六个月后回到以前的解决方案并试图记住他们在做什么！

Answer 4

这是我的解决方案，基于 @pst 的算法：

class String
  def remove_unmatched_parens
    scanner = StringScanner.new(dup)
    output = ''
    paren_depth = 0

    while char = scanner.get_byte
      if char == "("
        paren_depth += 1
        output << char
      elsif char == ")"
        output << char and paren_depth -= 1 if paren_depth > 0
      else
        output << char
      end
    end

    paren_depth.times{ output.reverse!.sub!('(', '').reverse! }
    output
  end
end

Answer 5

算法：

1. 遍历给定的字符串。
2. 执行此操作时，跟踪堆栈中的“(”位置。
3. 如果找到任何“)”，则从堆栈中删除顶部元素。
   • 如果堆栈为空，则从字符串中删除“)”。
4. 最后，我们可以得到不匹配的大括号的位置（如果有的话）。

Java代码：
当前@ http://a2ajp.blogspot.in/2014 /10/remove-unmatched-parenthesis-from-given.html