将字符串解析为树结构？

我想弄清楚如何将这种格式的字符串解析为任意深度的数据结构树。将字符串解析为树结构？

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

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

我已经试过一些这方面的正则表达式玩（如＃“{（[^ {}] *）}”），但我什么都尝试过，似乎“扁平化”树成列表的大名单。我可能从错误的角度来处理这个问题，或者一个正则表达式不适合这项工作。

感谢您的帮助！

来源

2010-09-29 erikcw

请勿对此任务使用正则表达式。更简单的方法是用语法（BNF或EBNF）描述你的字符串，然后编写一个解析器根据语法解析字符串。你可以从你的EBNF和BNF生成一个分析树，所以你自然会得到一个树结构。

你可以像这样开始：

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

注：我很快就写了这件事，所以它可能不完全正确的。但它应该给你一个想法。

来源

2010-09-29 22:39:30

因此，拥有该语法之后，有必要使用解析器生成器来生成基于此语法的解析器，不是吗？此外，解析器应该用一个句子喂，然后树可以被放弃，不是吗？ – bikashg 2011-03-18 17:29:43

@Bikash - 是的，如果你愿意的话，你可以*使用解析器生成器（比如yacc或bison），或者你可以编写自己的递归下降解析器（它非常简单）。如果您使用yacc或bison，则需要编写实际构建树的操作。我不认为yacc /野牛给你自己的树。他们只是识别语法。 – 2011-03-18 18:50:23

，如果你想快速劈：

{与字符[
替换}替换字符用]
更换|字符与空格
希望你不要输入空格。

read它在它所以它出现作为嵌套数组。

ps：我同意reg-ex不能这样做。

PSS：设定*读-EVAL *为假（你不想输入运行它的自我）

来源

2010-09-29 22:45:08

他的示例字符串实际上在其中一个段中包含空格。 – Rayne 2010-09-30 19:09:30

@Rayne：这是在英寸编辑。OP没有包括任何产生的叶子字符串的空间。 – aschepler 2010-09-30 22:01:55

哦。我也在考虑这个解决方案，直到我看到这个空间。然后，我哭了自己睡觉。 – Rayne 2010-10-01 00:14:00

试图匹配一个正则表达式，整个事情是不会让你太远，因为正则表达式最多输出一个匹配的子字符串位置列表，没有树状。你需要一个类似这样的词法分析器或语法：

将输入划分为标记 - 像'{'，'|'和'world'这样的原子片段，然后按顺序处理这些标记。从具有单个根节点的空树开始。

每当您找到{时，请创建并转到子节点。

每当您找到|时，请创建并转至兄弟节点。

每当您找到}，请进入父节点。

每次找到一个单词时，将该单词放在当前叶节点中。

来源

2010-09-29 22:46:53 aschepler

如何解决“{{text} {text}}”的情况？我认为他的字符串有点模糊......所有兄弟节点都应该用“|”分隔。 – 2010-09-29 22:59:10

是的，在这个例子中有一些令人困惑的地方。它看起来像嘿和世界之间的'} {}和地球与再见之间的'} {'造成树中不同深度的兄弟般的关系。我只能猜测这是为什么。（我用自己的算法注意到的另一个问题是：如果{就在一个单词之后，像'globe'一样？）所以这不是一个完整的解决方案，但是“类似的东西”它应该适用于解决这种类型的问题。 – aschepler 2010-09-29 23:09:06

有意义:) – 2010-09-29 23:12:52

您可以使用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 ""}]}

附：这是我的第一个语法语法，它可以更好。另请参阅http://en.wikipedia.org/wiki/Parsing_expression_grammar

来源

2010-10-11 12:09:20 edbond

将字符串解析为树结构？

回答

相关问题