將字符串解析爲樹結構？

我想弄清楚如何將這種格式的字符串解析爲任意深度的數據結構樹。將字符串解析爲樹結構？

"{{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

將字符串解析爲樹結構？

回答

相關問題