将带括号的字符串转换为树形结构，Ruby

Question

我有一个字符串"Animals ( Reptiles Birds ( Eagles Pigeons Crows ) )"，需要返回：

a = [
  {
    "Animals" => [
      {
        "Reptiles" => nil
      },
      {
        "Birds" => [
          { "Eagles" => nil },
          { "Pigeons" => nil },
          { "Crows" => nil }
        ]
      }
    ]
  }
]

我不明白如何做到这一点。我在哪里可以找到一些例子或者在谷歌上搜索什么？

- rel1x

---

奇怪，绝对奇怪，有趣！ - Cary Swoveland

这似乎是一个将S表达式转换为JSON格式的练习。我还没有找到基于Ruby的解决方案。 - vsnyc

听起来像作业。 - the Tin Man

Answer 1

我不明白我该怎么做。我在哪里可以找到一些例子或者我可以在谷歌上搜索什么？

使用递归正则表达式是一个选项，特别是如果括号平衡正确：

http://www.regular-expressions.info/recurse.html

如果对你来说太难了，可以使用普通正则表达式递归地遍历字符串。匹配类似以下内容的东西：

[a-z]+ ?([^()]*)

...然后在原始字符串中用占位符替换匹配项。反复执行此操作。

使用解析器是另一种选择。您可以编写一个简单的解析器，或者使用工具例如：

http://thingsaaronmade.com/blog/a-quick-intro-to-writing-a-parser-using-treetop.html

- Denis de Bernardy

Answer 2

这个在你的例子中有效，但我不知道它有多普适。

代码

def arrayify(str)
  eval('['+str.gsub(/(\w+)\s+\(/,'{\1=>[')
     .gsub( /(?!\{)(\w+)\s+/, '{\1=>nil},')  
     .gsub(')', ']}')
     .gsub(/\b(\w+)\b/,"\"\\1\"")+']')
end

例子

str = "Animals ( Reptiles Birds ( Eagles Pigeons Crows ) )"
arrayify(str)
  #=> [{ "Animals"=>[{ "Reptiles"=>"nil"},
  #                  { "Birds"   =>[{ "Eagles" =>"nil" },
  #                                 { "Pigeons"=>"nil" },
  #                                 { "Crows"  =>"nil" }
  #                                ]
  #                  }
  #                 ]
  #    }
  #   ]

Explanation

s1 = str.gsub(/(\w+)\s+\(/,'{\1=>[')
  #=> "{Animals=>[ Reptiles {Birds=>[ Eagles Pigeons Crows ) )"
s2 = s1.gsub( /(?!\{)(\w+)\s+/, '{\1=>nil},')  
  #=> "{Animals=>[ {Reptiles=>nil},{Birds=>[ {Eagles=>nil},{Pigeons=>nil},{Crows=>nil},) )"
s3 = s2.gsub(')', ']}')
  #=> "{Animals=>[ {Reptiles=>nil},{Birds=>[ {Eagles=>nil},{Pigeons=>nil},{Crows=>nil},]} ]}"
s4 = s3.gsub(/\b(\w+)\b/,"\"\\1\"")
  #=> "{\"Animals\"=>[ {\"Reptiles\"=>\"nil\"},{\"Birds\"=>[ {\"Eagles\"=>\"nil\"},{\"Pigeons\"=>\"nil\"},{\"Crows\"=>\"nil\"},]} ]}"
eval('['+s4+']')
  #=> <result in example>

不好意思，我得走了。 "eval"警察要来了。

- Cary Swoveland

Answer 3

这里是一种将字符串转换为数组的方法。

代码：

def arrayify(arr)
  a = split_arr(arr)
  a.map do |h|
    k = h.keys.first
    v = h.values.first
    case v
    when Array then { k => arrayify(v) }
    else { k=>v }
    end
  end
end

def split_arr(arr)
  a = []
  while arr.any?
    word = arr.shift
    if arr.empty? || arr.first != ?(
      a << { word=>nil }
    else
      arr.shift
      close_count = 0
      b = []
      loop do
        token = arr.shift
        case token
        when ?)
          break if close_count == 0
          close_count -= 1
        when ?( then close_count += 1
        end
        b << token
      end
      a << { word=>b }
    end
  end
  a
end

示例

str = "Animals ( Reptiles Birds ( Eagles Pigeons Crows ) ) Foods ( " +
      "Snacks Breakfast ( Pancakes Waffles ) )"

arrayify(str.split)

  #=> [{"Animals"=>[{"Reptiles" =>nil},
  #                 {"Birds"    =>[{"Eagles" =>nil},
  #                                {"Pigeons"=>nil},
  #                                {"Crows"  =>nil}
  #                               ]
  #                 }
  #                ]
  #    },
  #    {"Foods"  =>[{"Snacks"   =>nil},
  #                 {"Breakfast"=>[{"Pancakes"=>nil},
  #                                {"Waffles" =>nil}
  #                               ]
  #                 }
  #                ]
  #    }
  #   ]

- Cary Swoveland