arrays - 如何合并字符串数组中有前导和尾随括号的元素？

Question

在 Ruby 中，假设我有一个字符串数组

["a", "(b", "c)", "d", "e"]

如果一个字符串的第一个字符是“(”而另一个字符串的最后一个字符是“)”，我如何合并(中间有一个空格)字符串？在上面的示例中，我希望生成的数组是

["a", "(b c)", "d", "e"]

同样，如果我的数组是

["a", "(b", "e", "c)", "d"]

我想要的结果是

["a", "(b e c)", "d"]

但是如果数组是

["(a", "c"]

或

["c)", "e", "(b"]

我希望数组在第一个实例中保持不变 b/c，没有带有“)”的元素，在第二个实例中，带有“)”的元素位于以“(”开头的元素之前. 我希望这是有道理的。

Answer 1

我的第一个问题是，你是怎么得到这么奇怪的数组的？它看起来像是拆分了一些不应该那样拆分的结果。

我敢肯定有更聪明的方法可以做到这一点，但一个简单的方法是遍历数组并维护一个要连接的项目缓冲区(如果没有找到结束项目，则追加到输出的末尾) :

def regroup(arr)
  out, buf = [], []

  arr.each do |elem|
    if buf.empty? && !elem.start_with?('(')
      out << elem
    else
      buf << elem

      if elem.end_with?(')')
        out << buf.join(' ')

        buf.clear
      end
    end
  end

  out.concat(buf)
end

这种方法的主要问题是它不处理嵌套组。为了支持这一点，您需要一些方法来确保在刷新缓冲区之前打开和关闭项目的数量相等:

def regroup(arr)
  out, buf, count = [], [], 0

  arr.each do |elem|
    if buf.empty? && !elem.start_with?('(')
      out << elem
    else
      buf << elem

      if elem.start_with?('(')
        count += 1
      elsif elem.end_with?(')')
        count -= 1
      end

      if count.zero?
        out << buf.join(' ')

        buf.clear
      end
    end
  end

  out.concat(buf)
end

这应该是非常有效的，因为它是对数组的一次迭代，创建的对象数量最少。不幸的是，它仍然无法处理某些情况，例如如果 ["(a", "(b)", "c)"] 应该返回 ["(a", "(b c)"]。为此，您可能需要递归函数。如果您想查看该解决方案，请告诉我。

更新:实现递归解决方案比我想象的要困难得多。我有一个工作版本，但它太丑了，我不愿意分享!如果我需要回溯，我可能会使用 Amadan 的正则表达式解决方案或类似的解决方案。我还编写了一个带有原始回溯的解决方案版本:

def regroup(arr)
  out, pos = [], 0

  loop do
    should_retry = regroup_worker(arr.drop(pos)) do |elem, size=1|
      out << elem

      pos += size
    end

    break out unless should_retry
  end
end

def regroup_worker(arr)
  buf, count = [], 0

  arr.each do |elem|
    if buf.empty? && !elem.start_with?('(')
      yield elem
    else
      buf << elem

      if elem.start_with?('(')
        count += 1
      elsif elem.end_with?(')')
        count -= 1
      end

      if count.zero?
        yield buf.join(' '), buf.size

        buf.clear
      end
    end
  end

  # we have unbalanced parens, so let the caller consume the "bad" opening
  # paren and try again (returns false if nothing left to do)
  yield buf.first unless buf.empty?
end

regroup(["(a", "(b", "c)"]) # => ["(a", "(b c)"]

希望对您有所帮助!这当然是一个值得思考和尝试解决的有趣问题。