Случайное дерево в Racket

Question

Я пытаюсь создать случайное дерево из списков в Racket.

Дерево составлено из списка операторов и списка терминалов.

Результат будет выглядеть так:

'(* (+ 2 4) 2) 

Так что список может быть вызвана с помощью функции Eval.

Дальше должен быть установлен максимальный уровень.

Итак, моя догадка заключается в том, что процедура будет выглядеть следующим образом.

(define (make-tree tree level) ...) 

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

В настоящий момент каждый оператор принимает только два параметра (по существу, сгенерированные деревья являются бинарными деревьями), но было бы полезно включить в любой ответ, как развернуть функцию, чтобы включить три или более параметров.

Answer 1

#lang racket 

(define (random-from-list xs) 
    (list-ref xs (random (length xs)))) 

;; A TERMINAL is one if terminal1, terminal2, ... 

(define TERMINALS '(0 1 2 3 4 5 6 7 8 9)) 

(define (random-terminal) 
    (random-from-list TERMINALS)) 

;; An OPERATOR is one of '+ '-, '* '/ . 

(define OPERATORS '(+ - * /)) 

(define (random-operator) 
    (random-from-list OPERATORS)) 

;; A TREE is either 
;;  i) a terminal 
;; or ii) (list operator terminal1 terminal2 ... terminalN) 

(define (random-tree . ignore) 
    (match (random 5)    
    [0 (random-list-tree)]  ; probability 1/5 = 20% 
    [_ (random-terminal)])) 

(define (random-list-tree) 
    (define N (+ 2 (random (+ 3 1)))) ; at least two operands, at most 2+3 
    (cons (random-operator) (build-list N random-tree))) 

Для создания деревьев определенной глубины:

1. generate a tree T 
2. find the depth D of T 
3. if the depth D is of the desired depth return T 
4. otherwise go to 1.