1

入力 1:

(decompose '(* 1 2 3 4))

出力 1:

'(* 1 (* 2 (* 3 4)))

入力2

(decompose '(+ 1 2 3 (* 5 6 7)))

出力2

'(+ 1 (+ 2 (+ 3 (* 5 (* 6 7)))))

誰かがこれについてアイデアを持っていますか?

4

3 に答える 3

2

評価と同じ方法ですが、結果を出力する代わりに、使用される式を出力するだけです。

ラケットでテストされた私の実装は次のとおりです。

(define (decompose expr)
  (define (expand x)
    (if (list? x)
        (decompose x)
        x))
  (define oper (car expr))
  (let next ((args (map expand (cdr expr))))
    (if (<= (length args) 2)
        (cons oper args)
        (list oper (car args) (next (cdr args))))))
于 2012-12-10T01:32:51.457 に答える
1

あなたがあなた自身の解決策を投稿したのを見るので、私の完全な答えを示しても大丈夫だと思います。相互再帰的なプロシージャのペアとして、別の可能な実装を次に示します。このソリューションではlengthorを使用する必要がなくlist?（リストを不必要にトラバースする必要がある場合があります）、初等関数のみを使用するという事実が気に入っています（ foldr、、、またはその他の高階関数は必要ありません）。reversemap

(define (decompose lst)
  (if (or (null? lst)                     ; if the list is empty
          (null? (cdr lst))               ; or has only one element
          (null? (cddr lst)))             ; or has only two elements
      lst                                 ; then just return the list
      (process (car lst)                  ; else process car of list (operator)
               (cdr lst))))               ; together with cdr of list (operands)

(define (process op lst)
  (cond ((null? (cdr lst))                ; if there's only one element left
         (if (not (pair? (car lst)))      ; if the element is not a list
             (car lst)                    ; then return that element
             (decompose (car lst))))      ; else decompose that element
        ((not (pair? (car lst)))          ; if current element is not a list
         (list op                         ; build a list with operator,
               (car lst)                  ; current element,
               (process op (cdr lst))))   ; process rest of list
        (else                             ; else current element is a list
         (list op                         ; build a list with operator,
               (decompose (car lst))      ; decompose current element,
               (process op (cdr lst)))))) ; process rest of list

それはあなたの例、そしていくつかのために働きます：

(decompose '(* 1 2 3 4))
=> '(* 1 (* 2 (* 3 4)))

(decompose '(+ 1 2 3 (* 5 6 7)))
=> '(+ 1 (+ 2 (+ 3 (* 5 (* 6 7)))))

(decompose '(+ 1 (* 4 5 6) 2 3))
=> '(+ 1 (+ (* 4 (* 5 6)) (+ 2 3)))

(decompose '(+ 1 2 3 (* 5 6 7) 8))
=> '(+ 1 (+ 2 (+ 3 (+ (* 5 (* 6 7)) 8))))

(decompose '(+ 1 2 3 (* 5 6 7) (* 8 9 10) (* 11 12 (- 1))))
=> '(+ 1 (+ 2 (+ 3 (+ (* 5 (* 6 7)) (+ (* 8 (* 9 10)) (* 11 (* 12 (- 1))))))))
于 2012-12-10T03:30:07.670 に答える
0

Chris Jester-Youngのソリューションから変更:

(define (decompose x)
  (if (pair? x)
      (let ((operator (car x))
            (expanded-x (map decompose x)))
        (let decompose-helper ((operands (cdr expanded-x)))
          (if (<= (length operands) 2)
              (cons operator operands)
              (list operator (car operands) (decompose-helper (cdr operands))))))
      x))
于 2012-12-10T01:53:53.167 に答える