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

与评估它的方式相同，但不是输出结果，而是简单地输出将使用的表达式。

这是我的实现，在 Racket 上进行了测试：

(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、reverse或map任何其他高阶过程）。

(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 回答