逆转Shunting Yard算法是什么？

Question

Dijkstra的Shunting Yard算法用于解析中缀表达式并生成RPN输出。

我正在寻找相反的方法，即将RPN转换为高中数学课程风格的中缀表达式，以便以可理解的方式向数据库中的普通用户表示RPN表达式。

请节省您的时间，不要自己编写算法，只需指向我无法找到的教科书示例。从Shunting Yard算法开始倒推，并利用我的有关符号的知识，我可能能够找到解决方案。我只是在寻找一个快速捷径，这样我就不必重新发明轮子。

哦，请不要将此标记为“作业”，我 swear 我已经毕业了！;-)

- Hanno

---

这里有一些关于这个主题的有趣资料：https://stackoverflow.com/questions/19052960/converting-from-postfix-to-infix - Kaplan

Answer 1

由于RPN也被称为后缀表示法，我尝试搜索“将后缀转换为中缀”，并获得了很多结果。前几个结果都有代码示例，但我发现RubyQuiz条目特别有启发性。

- Bill the Lizard

Answer 2

如果您不担心去除多余的括号，那么以下Lisp代码将起作用：

(defun rpn-to-inf (pre)
  (if (atom pre)
      pre
      (cond ((eq (car (last pre)) 'setf)
         (list (rpn-to-inf (first pre)) '= (rpn-to-inf (second pre))))
        ((eq (car (last pre)) 'expt)
         (list (rpn-to-inf (first pre)) '^ (rpn-to-inf (second pre))))
        (t (list (rpn-to-inf (first pre)) 
             (car (last pre)) 
             (rpn-to-inf (second pre)))))))

- Paul Reiners

---

Lisp 中的一种实现可能会输出过多的括号。在许多层面上绝对是非常出色的...... - Wander Nauta