c# - 为 Unity3d 编写最简单的 newick 解析器(c# 或 Actionscript)

Question

我正在尝试弄清楚如何读取许多动物物种的 Newick 文件，但我一直无法找到一种“逻辑方法/过程”来用简单的编程语言对 Newick 字符串进行排序。我可以阅读 C#、AS、JS、GLSL 和 HLSL。

我找不到任何简单的资源，wiki 文章甚至没有谈论递归。如何解析 newick 的伪代码非常棒，但我找不到。

有谁知道在 Unity3d 中读取 newick 文件的最快方法？您能否帮助我走上正确的轨道，以便通过逻辑过程对 newick 代码进行分类，即:

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

分支长度数暂时不重要。

目标项目文件:

        (
            (
                (
                    (
                        (
                            (
                                Falco_rusticolus:0.846772,
                                Falco_jugger:0.846772
                            ):0.507212,
                            (
                                Falco_cherrug:0.802297,
                                Falco_subniger:0.802297
                            ):0.551687
                        ):0.407358,
                        Falco_biarmicus:1.761342
                    ):1.917030,
                    (
                        Falco_peregrinus:0.411352,
                        Falco_pelegrinoides:0.411352
                    ):3.267020
                ):2.244290,
                Falco_mexicanus:5.922662
            ):1.768128,
                Falco_columbarius:7.69079
        )

Answer 1

如果您没有形式语法方面的背景，那么实现解析器可能会很困难。所以最简单的方法似乎是使用解析器生成器，例如 ANTLR , 然后你只需要熟悉语法符号即可。你可以generate a parser written in C#从语法。

幸运的是，您可以在线找到新的语法:here .

更新:

如果您执行了上述操作，那么您将得到如下内容:

public class Branch
{
    public double Length { get; set; }
    public List<Branch> SubBranches { get; set; } = new List<Branch>();
}
public class Leaf : Branch
{
    public string Name { get; set; }
}

public class Parser
{
    private int currentPosition;
    private string input;

    public Parser(string text)
    {
        input = new string(text.Where(c=>!char.IsWhiteSpace(c)).ToArray());
        currentPosition = 0;
    }
    public Branch ParseTree()
    {
        return new Branch { SubBranches = ParseBranchSet() };
    }
    private List<Branch> ParseBranchSet()
    {
        var ret = new List<Branch>();
        ret.Add(ParseBranch());
        while (PeekCharacter() == ',')
        {
            currentPosition++; // ','
            ret.Add(ParseBranch());
        }
        return ret;
    }
    private Branch ParseBranch()
    {
        var tree = ParseSubTree();
        currentPosition++; // ':'
        tree.Length = ParseDouble();
        return tree;
    }
    private Branch ParseSubTree()
    {
        if (char.IsLetter(PeekCharacter()))
        {
            return new Leaf { Name = ParseIdentifier() };
        }

        currentPosition++; // '('
        var branches = ParseBranchSet();
        currentPosition++; // ')'
        return new Branch { SubBranches = branches };
    }        
    private string ParseIdentifier()
    {
        var identifer = "";
        char c;
        while ((c = PeekCharacter()) != 0 && (char.IsLetter(c) || c == '_'))
        {
            identifer += c;
            currentPosition++;
        }
        return identifer;
    }
    private double ParseDouble()
    {
        var num = "";
        char c;
        while((c = PeekCharacter()) != 0 && (char.IsDigit(c) || c == '.'))
        {
            num += c;
            currentPosition++;
        }
        return double.Parse(num, CultureInfo.InvariantCulture);
    }
    private char PeekCharacter()
    {
        if (currentPosition >= input.Length-1)
        {
            return (char)0;
        }
        return input[currentPosition + 1];
    }
}

可以这样使用:

var tree = new Parser("((A:1, B:2):3, C:4)").ParseTree();

顺便说一句，上面的解析器实现了以下语法，没有任何类型的错误处理:

Tree -> "(" BranchSet ")"   
BranchSet -> Branch ("," Branch)*   
Branch -> Subtree ":" NUM
Subtree -> IDENTIFIER | "(" BranchSet ")"