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

Question

我希望能够从字符串中删除“未配对”的括号。

也就是说，除非在字符串中有跟在括号后面的“)” ，否则应该删除所有的“（” 。同样地，除非在字符串中有跟在“)”前面的“（”，否则应该删除所有的“）”。

理想情况下，算法还应该考虑嵌套的情况。

例如：

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

- Tom Lehman

Answer 1

不要使用正则表达式，可以考虑使用下推自动机（push-down automata）。可能Ruby正则表达式无法处理此问题，我相信Perl的可以。

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

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

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

在处理结束时，如果seen_parens > 0，则从末尾开始删除相应数量的括号。（使用堆栈或递归可将此步骤合并到上述过程中。）

整个过程的时间复杂度为O(n)，即使有相对较高的开销。

祝你编码愉快。

- user166390

---

确实如此。这个例子在全世界教授不能使用正则表达式解析的语言时都被用作字面上的例子。Ruby的Regexp比正则表达式强大得多，它们实际上可以解析这种语言，但这并不意味着它很容易维护。你可以编写一个简单的递归下降分析器或者下推自动机，所花费的时间甚至比你阅读别人给你的Regexp、更不用说编写自己的Regexp的时间还要短。如果你将Regexp分成多行以便添加注释，也许最终自动机的代码长度甚至比Regexp还要短。 - Jörg W Mittag

感谢提供算法。我的回答（https://dev59.com/KFXTa4cB1Zd3GeqP2o7L#5439883）看起来对您来说正确吗？ - Tom Lehman

Answer 2

以下内容使用Oniguruma。如果您正在使用ruby1.9，则内置了正则表达式引擎Oniguruma。如果您使用的是ruby1.8，请参阅此处：Oniguruma。 更新 我之前懒得自己编写正则表达式，只是复制粘贴了别人的代码，但出现了问题。所以现在我编写了自己的正则表达式，相信它应该可以正常工作了。

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

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

更新2

这更简单。

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

- sawa

---

@pst 前一个实际上出了问题。所以现在，我自己写了一个不同的正则表达式。这次应该没问题了。希望不会出现任何意外。 - sawa

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类的人，因为你永远不应该打开一个标准类。正则表达式对于解析器来说非常脆弱，难以支持。我无法想象在6个月后回到之前的解决方案，并尝试记住它们在做什么！

- Wes

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

- Tom Lehman

---

那么，remove_unmatched_parents 是一个打字错误？我也这么想。 - sawa

Answer 5

算法：

1. 遍历给定的字符串。
2. 在此过程中，使用堆栈跟踪“（”的位置。
3. 如果找到任何“）”，则从堆栈中删除顶部元素。
   • 如果堆栈为空，则从字符串中删除“）”。
4. 最后，我们可以有未匹配括号的位置（如果有）。

Java代码： 请参阅http://a2ajp.blogspot.in/2014/10/remove-unmatched-parenthesis-from-given.html。

- Jyothi Prasad Asapu