Разобрать строку в древовидную структуру? - PullRequest
Новая
       57

Разобрать строку в древовидную структуру?

6 голосов
/ 30 сентября 2010

Я пытаюсь выяснить, как разобрать строку в этом формате в древовидную структуру данных произвольной глубины. 

"{{Hello big|Hi|Hey} {world|earth}|{Goodbye|farewell} {planet|rock|globe{.|!}}}"

[[["Hello big" "Hi" "Hey"]
  ["world" "earth"]]
 [["Goodbye" "farewell"]
  ["planet" "rock" "globe" ["."
                            "!"]]]]

Я попытался поиграть с некоторыми регулярными выражениями для этого (например, # "{([^ {}] *)}"), но все, что я пробовал, похоже, "сплющивает" дерево в большой список списки. Я мог бы подойти к этому с неправильной точки зрения, или, может быть, регулярное выражение просто не подходит для работы.

Спасибо за вашу помощь!

Ответы [ 4 ]

9 голосов
/ 30 сентября 2010

Не используйте регулярные выражения для этой задачи. Более простым способом было бы описать вашу строку с помощью грамматики (BNF или EBNF), а затем написать синтаксический анализатор для анализа строки в соответствии с грамматикой. Вы можете генерировать дерево разбора из ваших EBNF и BNF, и, таким образом, вы, естественно, получите древовидную структуру.

Вы можете начать с чего-то вроде этого: 

element      ::= element-type, { ["|"], element-type }
element-type ::= primitive | "{", element, "}"
primitive    ::= symbol | word
symbol       ::= "." | "!"
word         ::= character { character }
character    ::= "a" | "b" | ... | "z"

Примечание: я написал это быстро, и это может быть не совсем правильно. Но это должно дать вам представление.

4 голосов
/ 30 сентября 2010

Попытка сопоставить все с одним регулярным выражением не слишком далеко, так как регулярные выражения выводят в большинстве случаев список совпадающих позиций подстроки, но не в виде дерева.Вам нужен лексер или грамматика, которая выполняет что-то вроде этого:

Разделите входные данные на токены - атомарные части, такие как '{', '|' и 'world', затем обработайте эти токены по порядку.Начните с пустого дерева с одним корневым узлом.

Каждый раз, когда вы найдете {, создайте и перейдите к дочернему узлу.

Каждый раз, когда вы найдете |, создайте и перейдитена одноуровневый узел.

Каждый раз, когда вы найдете }, переходите к родительскому узлу.

Каждый раз, когда вы найдете слово, поместите это слово в текущий листовой узел.

3 голосов
/ 30 сентября 2010

если вы хотите быстрый взлом:

  • замените {символы с [
  • , замените} символы с]
  • замените |символы с пробелами
  • надеюсь, вы не получите ввод с пробелами.

read, поэтому он выглядит как вложенные массивы.

ps: я согласен, что рег-экс не может этого сделать.

pss: установите для * read-eval * значение false (вы не хотите, чтобы ввод выполнялся самостоятельно)

1 голос
/ 11 октября 2010

Вы можете использовать amotoen для построения грамматики и анализа этого: 

(ns pegg.core
  (:gen-class)
  (:use
   (com.lithinos.amotoen
    core string-wrapper))
  (:use clojure.contrib.pprint))

(def input "{{Hello big|Hi|Hey} {world|earth}|{Goodbye|farewell} {planet|rock|globe{.|!}}}")

(def grammar
     {
      :Start :List
      :ws #"^[ \n\r\t]*"
      :Sep "|"
      :String #"^[A-Za-z !.]+"
      :Item '(| :String :List)
      :Items [:Item '(+ [:Sep :Item])]
      :List [:ws "{" '(* (| :Items :Item)) "}" :ws]
      })

(def parser (create-parser grammar))

(defn parse
  [^String input]
  (validate grammar)
  (pprint (parser (wrap-string input))))

Результат: 

pegg.core> (parse input)
{:List [{:ws ""} "{" ({:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "Hello big"}} ([{:Sep "|"} {:Item {:String "Hi"}}] [{:Sep "|"} {:Item {:String "Hey"}}])]}) "}" {:ws " "}]}} {:Items [{:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "world"}} ([{:Sep "|"} {:Item {:String "earth"}}])]}) "}" {:ws ""}]}} ([{:Sep "|"} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "Goodbye"}} ([{:Sep "|"} {:Item {:String "farewell"}}])]}) "}" {:ws " "}]}}])]} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "planet"}} ([{:Sep "|"} {:Item {:String "rock"}}] [{:Sep "|"} {:Item {:String "globe"}}])]} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "."}} ([{:Sep "|"} {:Item {:String "!"}}])]}) "}" {:ws ""}]}}) "}" {:ws ""}]}}) "}" {:ws ""}]}

P.S. Это одна из моих первых грамматических задач, и она может быть лучше. Также см. http://en.wikipedia.org/wiki/Parsing_expression_grammar

...