ruby - 如何构建、排序和打印一棵树？

Question

这与其说是特定于语言的问题，不如说是算法困境，但由于我目前正在使用 Ruby，所以我将这样标记它。我已经在这上面花了 20 多个小时，相比之下，如果有人告诉我编写 LaTeX 解析器就像在公园里散步，我绝对不会相信。

我有一个循环来从不同的文件中读取层次结构(以\m 为前缀)

art.tex: \m{Art}
graphical.tex: \m{Art}{Graphical}
me.tex: \m{About}{Me}
music.tex: \m{Art}{Music}
notes.tex: \m{Art}{Music}{Sheet Music}
site.tex: \m{About}{Site}
something.tex: \m{Something}
whatever.tex: \m{Something}{That}{Does Not}{Matter}

我需要按字母顺序对它们进行排序并将它们打印成一棵树

About
    Me (me.tex)
    Site (site.tex)
Art (art.tex)
    Graphical (graphical.tex)
    Music (music.tex)
        Sheet Music (notes.tex)
Something (something.tex)
    That
        Does Not
            Matter (whatever.tex)

在 (X)HTML 中

<ul>
<li>About</li>
<ul>
<li><a href="me.tex">Me</a></li>
<li><a href="site.tex">Site</a></li>
</ul>
<li><a href="art.tex">Art</a></li>
<ul>
<li><a href="graphical.tex">Graphical</a></li>
<li><a href="music.tex">Music</a></li>
<ul>
<li><a href="notes.tex">Sheet Music</a></li>
</ul>
</ul>
<li><a href="something.tex">Something</a></li>
<ul>
<li>That</li>
<ul>
<li>Doesn't</li>
<ul>
<li><a href="whatever.tex">Matter</a></li>
</ul>
</ul>
</ul>
</ul>

在没有 Rails 的情况下使用 Ruby，这意味着至少 Array.sort 和 Dir.glob 可用。

我所有的尝试都是这样形成的(因为这部分应该工作得很好)。

def fss_brace_array(ss_input)#a concise version of another function; converts {1}{2}...{n} into an array [1, 2, ..., n] or returns an empty array
    ss_output = ss_input[1].scan(%r{\{(.*?)\}})
rescue
    ss_output = []
ensure
    return ss_output
end
#define tree
s_handle = File.join(:content.to_s, "*")
Dir.glob("#{s_handle}.tex").each do |s_handle|
    File.open(s_handle, "r") do |f_handle|
        while s_line = f_handle.gets
            if s_all = s_line.match(%r{\\m\{(\{.*?\})+\}})
                s_all = s_all.to_a
                #do something with tree, fss_brace_array(s_all) and s_handle
                break
            end
        end
    end
end
#do something else with tree

Answer 1

重要提示:我现在无法通过 SSH 连接到我的 linux 机器，这意味着我无法测试此代码。连最微小的一点都没有。它可能有愚蠢、明显的语法错误或逻辑，因为我在输入框中从头开始编写它。但它看起来不错......我认为。我下类回家后会检查一下。

SOURCE = <<-INPUT
  art.tex: \m{Art}
  graphical.tex: \m{Art}{Graphical}
  me.tex: \m{About}{Me}
  music.tex: \m{Art}{Music}
  notes.tex: \m{Art}{Music}{Sheet Music}
  site.tex: \m{About}{Site}
  something.tex: \m{Something}
  whatever.tex: \m{Something}{That}{Does Not}{Matter}
INPUT
HREF = '#href'

def insert_leaves(tree,node_list)
  next = node_list[0]
  rest = node_list[1..-1]
  tree[next] ||= {}
  if not rest.empty?
    insert_leaves(tree[next],rest)
  else
    tree[next]
    # recursively, this will fall out to be the final result, making the
    # function return the last (deepest) node inserted.
  end
end

tree = {}

SOURCE.each_line do |line|
  href, folder_string = line.split(': \\m') #=> ['art.tex','{Art}{Graphical}']
  folders = folder_string.scan(/[^{}]+/)     #=> ['Art','Graphical']
  deepest_folder = insert_leaves(tree,folders)
  deepest_folder[HREF] = href
end

# After this insertion, tree looks like this:
#
# {
#   About = {
#     Me = {
#       #href = me.tex
#     }
#     Site = {
#       #href = site.tex
#     }
#   }
#   Art = {
#     Graphical = {
#       #href = graphical.tex
#     }
#     ...
#
# Edge case: No category should be named '#href'.

def recursive_html_construction(branch, html)
  return if branch.keys.reject(HREF).empty? # abort if the only key is
                                            # an href.
  html << '<ul>'
  branch.keys.sort.each do |category|
    next if category == HREF # skip href entries.
    html << '<li>'
    if branch[category].key?(HREF)
      html << "<a href='#{branch[category][HREF]}'> #{category}</a>"
    else
      html << category
    end
    html << '</li>'
    recursive_html_construction(branch[category],html)
  end
  html << '</ul>'
end

html = ""

recursive_html_construction(tree,html)

puts html # => '<ul><li>About</li><ul><li><a href='me.tex'>Me</a></li><li>
          #     <a href='site.tex'>Site</a></li></ul><li>Art</li><ul><li>
          #     <a href='graphical.tex'>Graphical</a></li>...