Разбор текста к дереву в Racket / Scheme - PullRequest
Новая
       42

Разбор текста к дереву в Racket / Scheme

0 голосов
/ 25 декабря 2018

Я пытаюсь преобразовать свой код C ++ в Racket, так как я изучаю Racket.Мой упрощенный код на C ++: 

struct Node
{
    char value = '\0';
    std::vector<Node> kids;
    explicit Node(char ch) : value(ch) {}
};

void ParseTree(const std::string& tokens, size_t& i, Node& root)
{
    while (i < tokens.size())
    {
        const Token& token = tokens[i++];
        if (token == '<')   // children begin
        {
            ParseTree(tokens, i, root.kids.back());
        }
        else if (token == '>')  // children end, go up
        {
            return;
        }
        else
        {
            root.kids.emplace_back(token);
        }
    }
}

Node ParseTree(const std::string& s)
{
    size_t i = 0;
    Node root('$');
    ParseTree(Parse(s), i, root);
    return root;
}

Очень простой код.Мой перевод на Racket: 

(define (parse-tree tokens)
    (if(empty? tokens)
       '()
       (cond
         [(eq? '< (car tokens))
           (list (parse-tree (cdr tokens)))]
         [(eq? '> (car tokens))
          (parse-tree (cdr tokens))]    ; no return, how to step up?
         [else
          (cons (car tokens)(parse-tree (cdr tokens)))])))

Проблема здесь в том, что я не возвращаюсь в (eq? '> (Автомобильные токены), поэтому новые узлы добавляются внизу. Небольшой тест: 

(parse-tree '(1 < 2 < 3 4 > > Z < X >))

Должно быть: 

'(1 (2 (3 4)) Z (X))

Это: 

'(1 (2 (3 4 Z (X))))

Как это исправить?

1 Ответ

0 голосов
/ 26 декабря 2018

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

Такие проблемы, когда мы должны отслеживать, где мы находимся во вложенной структуре, лучшерешена с использованием структуры данных stack .Я буду использовать list для реализации стека списков со следующим помощником для добавления нового элемента в самый верхний список: 

(define (append-top ele stack)
  (cons (append (car stack) (list ele))
        (cdr stack)))

Теперь для фактического решения.Предполагая, что входной список правильно сформирован с тем же числом < и > и в правильном порядке (проверка ошибок не выполняется): 

(define (parse-tree tokens)
  (let parse ([tokens tokens] [stack '(())])
    (cond [(null? tokens)
           ; solution is at the top of the stack, return it
           (car stack)]
          [(eq? (car tokens) '<)
           ; start new sublist at the top of the stack
           (parse (cdr tokens) (cons '() stack))]
          [(eq? (car tokens) '>)
           ; pop top element of the stack, append it to previous
           ; frame, continue with solution where we left it
           (parse (cdr tokens) (append-top (car stack) (cdr stack)))]
          [else
           ; add current element to top of stack
           (parse (cdr tokens) (append-top (car tokens) stack))])))

Работает, как и ожидалось! 

(parse-tree '(1 < 2 < 3 4 > > Z < X >))
=> '(1 (2 (3 4)) Z (X))
...