Wie man das Newick-Tree-Format in Tree wie Hierarchical Javascript-Objekt

Question

konvertieren Ich studiere gerade Newick-Format. https://en.wikipedia.org/wiki/Newick_format Ich habe eine Newick Zeichenfolge eines Baumes

(A,B,(C,D)E)F; 

Wie diese Zeichenfolge in eine hierarchische konvertieren Javascript Objekt wie

tree = { 
    name: 'F', 
    children: [{ 
    name: 'A' 
    }, { 
    name: 'B' 
    }, { 
    name: 'E', 
    children: [{ 
     name: 'C' 
    }, { 
     name: 'D' 
    }] 
    }] 

} 

Answer 1

sollte der Code unten Aufbau korrekt funktionieren mit jedem Eingang ähnlich wie Ihre Beispiel.

Es wird jedoch davon ausgegangen, dass jeder Knoten mit einem einzelnen Zeichen identifiziert wird. Sie müssten es ändern, um längere Symbole zu unterstützen.

Dieser Code ist auch nicht kugelsicher und bricht ohne Warnung bei ungültigen Eingabezeichenfolgen ab.

Die Hauptidee besteht darin, die Zeichenfolge in umgekehrter Reihenfolge zu analysieren und die Knotenhierarchie mithilfe des Stapels Array zu verfolgen.

var newick = '(A,B,(C,D)E)F', 
    stack = [], 
    child, 
    root = [], 
    node = root; 

newick.split('').reverse().forEach(function(n) { 
    switch(n) { 
    case ')': 
     // ')' => begin child node 
     stack.push(node); 
     node = child.children = []; 
     break; 

    case '(': 
     // '(' => end of child node 
     node = stack.pop(); 
     break; 

    case ',': 
     // ',' => separator (ignored) 
     break; 

    default: 
     // assume all other characters are node names 
     node.push(child = { name: n }); 
     break; 
    } 
}); 

Und hier ist eine einfache Funktion, die die resultierende Struktur wird Dump:

var dmp; 

(dmp = function(node, level) { 
    node.forEach(function(n) { 
    console.log(Array(level).join('-') + n.name); 
    n.children && dmp(n.children, level + 1); 
    }); 
})(root, 1); 

Ausgang:

F 
-E 
--D 
--C 
-B 
-A 

Answer 2

Sie könnten unter Teil des ursprünglichen Baumes aussehen wollen und Schreiben eine rekursive Funktion, die die entfernten Buchstaben pro hierarchische Ebene speichert.

Möglicher Starter:

var str = "Z,I,(A,B,(C,D)E)F,G,H"; 

var firstClose = str.indexOf("("); 
var lastClose = str.lastIndexOf(")"); 

console.log(firstClose); 
console.log(lastClose); 

var remainingTree = str.substr(firstClose , lastClose); 
console.log(remainingTree); 

var lastLetterStr = (str.substring(lastClose + 1)); 
var lastLetterArray = lastLetterStr.split(','); 

var firstLetterStr = str.substring(0,firstClose-1) 
var firstLetterArray = firstLetterStr.split(',') 

console.log(lastLetterArray); 
console.log(firstLetterArray); 

gelten die gleichen Schritte, um die remainingTree Zeichenfolge, bis die Zeichenfolge leer ist, und dann das tree Objekt erstellen? Sie werden einige Logik enthalten müssen, damit die Funktion weiß, wie zum Beispiel (C,D) als Kinder E zu assoziieren, wenn das Objekt time

JS Fiddle

Answer 3

können Sie versuchen, NewickJS

Beispiel:

var newick = new Newick('(A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F'); 

Oder können Sie statische Methode verwenden:

var tree = Newick.parse('(A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F'); 

Das Ergebnis:

{ 
    name: "F", 
    branchset: [ 
    { 
     name: "A", 
     length: 0.1 
    }, 
    { 
     name: "B", 
     length: 0.2 
    }, 
    { 
     name: "E", 
     length: 0.5, 
     branchset: [ 
     { 
      name: "C", 
      length: 0.3 
     }, 
     { 
      name: "D", 
      length: 0.4 
     }] 
    }] 
} 

NewickJS at GitHub