recursion - 计算前缀并将其转换为中缀

Question

我在编写将前缀转换为中缀的程序时遇到了一些严重的问题。我已经编写了 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))

它没有明确使用“堆栈”（但递归使用调用堆栈）。