recursion - プレフィックスからインフィックスへの計算と変換

Question

プレフィックスをインフィックスに変換するプログラムを作成する際に深刻な問題が発生しています。スタックを使用する 2 つのプログラムを既に作成しましたが、その方法は異なります。1 つは 2 つのスタックを使用し、もう 1 つは再帰的な方法で 1 つを使用しました。しかし、要件では2つのスタック（オペランドと演算子）を使用し、再帰的な方法を使用する必要があるため、正しく実行するのにまだ問題があります。これらの要件の両方を一緒に視覚化するのに深刻な問題があります。アルゴリズムがどのようになるか知っている人はいますか? 単純なアルゴリズムがあれば、本当に命の恩人になります。ありがとうございました

Answer 1

これでできます。

(define (prefix->infix pre)
  (cond ((list? pre)
         (assert (= 3 (length pre)))
         (let ((operator (list-ref pre 0))
               (operand1 (list-ref pre 1))
               (operand2 (list-ref pre 2)))
           (list (prefix->infix operand1)
                 operator
                 (prefix->infix operand2))))
        (else pre)))

> (prefix->infix '(+ 1 2))
(1 + 2)
> (prefix->infix '(+ 1 (* 2 3)))
(1 + (2 * 3))
> (prefix->infix '(+ (/ 1 4) (* 2 3)))
((1 / 4) + (2 * 3))

「スタック」を明示的に使用しません (ただし、再帰はコール スタックを使用します)。