LINUX.ORG.RU

Парсинг дерева

 ,


0

1

Всем привет! Столкнулся с задачей, но никак не могу понять как ее сделать. В общем, есть формат Tree(Описание Формата) Вкратце - это строка, в которой есть символы \n, \t, пробелы и т.д Т.е вида

"access\n\ttime =2014-10-10\n\turl =labuda.com\n\tip =8.8.8.8\nerror\n\tunknown\n\t\terror =fuck"
В человеческом представлении будет:
access
    time =2014-10-10
    url =labuda.com
    ip =8.8.8.8
error
    unknown
        error =fuck
Я хочу ее научиться парсить, т.е на выходе получать что-то типа:
[Node(access, [Node(time, 2014-10-10), Node(url, labuda.com), Node(ip, 8.8.8.8)]), Node(error, [Node(unknown, [Node(error, fuck)])])]
Пока что я дошел до того, что могу получить все Node:
class Node
{
    String name;
    String content;
    Node [] chlrn;
    int indent;
 
    Node()
    {
        this.name = null;
        this.content = null;
        this.indent = 0;
    }
 
    Node(String values,String  name, int indent)
    {
        this.name = name;
        this.content = values;
        this.indent = indent;
    }
    void printNode()
    {
        System.out.println("Name: " + name + ", Value: " + content + ", Indent: " + indent);
    }
}
 
 
public class Main {
 
    public static void main(String[] args)
    {
        //Example string
        String str = "access\n\ttime =2014-10-10\n\turl =labuda.com\n\tip =8.8.8.8\nerror\n\tunknown\n\t\terror =fuck";
 
        String [] strArr = str.split("\n");
 
 
        Pattern p = Pattern.compile("^([ \\t]*)([^=]*)(?:=(.*))?$");
        Matcher m;
 
        List<Node> lstNode = new ArrayList<Node>();
        List<Node> lstNodeAns = new ArrayList<Node>();
 
        for(int i = 0; i < strArr.length; i++)
        {
            //System.out.println(i + " " + strArr[i]);
            String line = strArr[i];
            m = p.matcher(line);
 
            if (!m.find())
                continue;
 
            String indent = m.group(1);   // отступы
            String key = m.group(2);     // узел
            String value = m.group(3);   //значение
 
            //System.out.println(indent + key + value);
            //System.out.println(indent.length());
            Node nde = new Node(value, key, indent.length());
            lstNode.add(nde);
        }
}
Name: access , Value: null, Indent: 0
Name: time , Value: 2014-10-10, Indent: 1
Name: url , Value: labuda.com, Indent: 1
Name: ip , Value: 8.8.8.8, Indent: 1
Name: error, Value: null, Indent: 0
Name: unknown, Value: null, Indent: 1
Name: error , Value: fuck, Indent: 2
Где indent - это отступ(по которому и надо определять вложенность, как мне кажется). key - это узел, а value - его значение. Т.е я распарсил и получил все узлы дерева, но как реализовать правильную вложенность(принадлежность) узла к узлу?

Буду очень благодарен за помощь!


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

Если отступов стало больше - ставь её родительской у текущей и меняй запомненную.

Если отступов столько же, ставь родительской ту же, что и у последней добавленной ноды в списке

Если отступов стало меньше, высчитывай на сколько, и проходи столько же по иерархии родительских.

Adonai ★★★
()

Другой вариант (один предложили выше) на псевдокоде:

class TreeReader
{
    private String str;
    private Node root;
    
    TreeReader(String str)
    {
        this.str = str;
        root = readTree(0);
    }
    
    public Node getTree()
    {
        return root;
    }
    
    private Node readTree(int level)
    {
        final Node node = readNode();
    
        int nextLevel = getLevel();
        while (nextLevel == level + 1) {
            final Node child = readTree(level + 1);
            node.addChild(child);
            nextLevel = getLevel();
        }
    
        if (nextLevel > level) {
            throw new RuntimeError("Broken tree");
        }
    
        return node;
    }
    
    private int getLevel()
    {
        return <number of leading tabulation characters in str>;
    }

    private Node readNode()
    {
        <parse str>;
        <advance str>;
    }
}
Древовидные структуры обычно хорошо дружат с рекурсией.

xaizek ★★★★★
()
Ответ на: комментарий от aarexer

Ну тут два варианта. Можно и массив (главное чтобы ноды помнили, где чей родитель), так удобнее будет, например, сохранять дерево обратно в файл - просто идти по массиву от начала к концу и расставлять отступы согласно ссылкам на родителей, а можно и сделать

class Node 
{ 
    Node parentNode;
    List<Node> childNodes;
    String content;
}
А потом создать корневой нод и цеплять уже всё к нему.

Adonai ★★★
()
Последнее исправление: Adonai (всего исправлений: 1)
Ответ на: комментарий от aarexer

Аа, я понял. Ты про последнее предложение? Иерархию ты сам и создашь в процессе обхода по дереву, цепляя детей к запомненной ноде. Представь, три раза меняется отступ в большую сторону - у тебя получатся три ноды, каждая следующая имеет родителем предыдущую. А потом вдруг отступ уменьшается до одного - и тебе нужно будет пройти 3-1=2 раза по иерархии родителей, то есть от ноды3 к ноде2 и ещё раз к ноде1, и вуаля, ты снова цепляешь детей к первой ноде, как и нужно при отступе в единицу.

Adonai ★★★
()
Последнее исправление: Adonai (всего исправлений: 2)

Столкнулся с задачей

Ааа!! ПТУ-шный практикум что-ле ? Такой формат выдумывают разве-что аффторы учёбников чтоб подготовить студиозусов ко всяким TableModel/TreeModel :-)

ps/ формат должен раскладываться чахлым AWK`ом в вид «/node1/node2.../nodeN/property = value» строки за 4 или ввоще однострочником..

pps/ лишняя или недостающая (и кстате невидимая) \t будет ломать парсер пораждая неоднозначности.

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

Такой формат выдумывают разве-что аффторы учёбников

Уже б json показывали - написаный для него парсер может когда-нибудь учащемуся пригодиться...

invy ★★★★★
()
Ответ на: комментарий от MKuznetsov

Было бы неплохо, если бы ты показал, как уложить такое в 4 строки. У меня не получается. Задача есть задача. Про лишнюю табуляцию ты прав.

aarexer
() автор топика
Ответ на: комментарий от Adonai

Да, спасибо, я понял и так и сделал. Спасибо!

aarexer
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.