Как построить, отсортировать и распечатать дерево своего рода?

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>

использование Ruby без Rails, что означает, что доступны по крайней мере 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>...

Answer 2

Вот рабочее решение в Python после простого помещения всех записей в массив.

import operator
import itertools
def overput(input):
    for betweenput, output in itertools.groupby(input, key=operator.itemgetter(0)):
        yield '<li>'
        yield betweenput
        output = [x[1:] for x in output if len(x) > 1]
        if output:
            yield '<ul>'
            for part in overput(output):
                yield part
            yield '</ul>'
        yield '</li>'

Answer 3

Был вопрос, очень похожий на этот, недавно, посмотрите на мой и другие ответы:

Как справиться с такими рекурсивными родительскими / детскими проблемами?

Answer 4

Я не знаком с Ruby, но вот как это можно сделать на большинстве языков:

1. Создать пустую древовидную структуру.
2. Для каждой строки:
3. Для каждого элемента {} после \ m:
4. Если этот элемент можно найти в дереве на том же уровне, ничего не делать.
5. В противном случае создайте узел дерева, который является дочерним по отношению к предыдущему элементу или корнем, если он является первым
6. В конце строки прикрепите часть foo.tex к самому конечному узлу.

Я не знаю, как это переводится на Ruby, в частности, как там представлена ​​древовидная структура.