0

式を取得して挿入し、それをプレフィックスに変更する関数を書きたいと思います。まず、+ 演算子のみを扱うと仮定して、式 1+1+1 を (+ (+ 1 1) 1) に変更します。

私は foldl または foldl のような問題を使用してそれを行いたい: リストの 2 番目の項目 (常にオペランド) を取得し、最初と 3 番目の項目を (この順序で) 追加してから、先ほどの式を使用したいと思いますリストの最初の項目になるように追加されるので、リストの残りの部分で同じことを再帰的に行います。

私は次のことを試しました：

(lambda (lst)
       (fold-left (lambda (pmLst)
          `(,((cadr pmLst) ,(car pmLst) (caddr pmLst)) ,(cddr pmLst)))
                        '()
                        lst))

しかし、左折に与えられたラムダには2つの引数が必要であることに気付きましたが、リストの最初の3つの項目を処理したいと思います。

少しトリッキーになったので、私が自分自身を明確にしたことを願っています..

4

1 に答える 1

0

foldあなたが望むことをしません。式を想像する場合は、プロシージャとして(5 + 3 + 2)折り畳みを使用して次のようにします。proc

(proc 2 (proc '+ (proc 3 (proc '+ (proc 5 '())))))

方法は、奇数要素と偶数要素を独自のリストに返す関数を作成して、'(+ 2 - 3)次の(+ -) and (2 3)ようにすることです。

(define (infix->prefix expr)
  (if (pair? expr)
      (let-values ([(ops args) (split (cdr expr))])
        (fold (lambda (op arg acc)
                (list op acc (infix->prefix arg)))
              (car expr)
              ops
              args))
      expr))

ただし、両方のサイズは、独自の再帰を単にローリングするよりもはるかに大きくなります。

(define (infix->prefix expr)
    (define (aux lst acc)
      (if (pair? lst)
          (aux (cddr lst)
               (list (car lst)
                     acc
                     (infix->prefix (cadr lst))))
          acc))

    (if (pair? expr)
        (aux (cdr expr) (infix->prefix (car expr)))
        expr))

(infix->prefix '(1 + 2 - 3))
; ==> (- (+ 1 2) 3)

ここには演算子の優先順位はありません。すべてが厳密に左から右です。

于 2016-11-24T12:26:21.837 に答える