Dijkstra的Shunting Yard算法用于解析中缀符号并生成RPN输出。

我正在寻找相反的方法，一种将RPN转换为高中数学类风格的中缀表示法的方法，以便从数据库中表示RPN表达式，以易于理解的方式放置用户。

请节省时间，不要自己动手做算法，只给我指出我似乎找不到的教科书示例。从Shunting Yard算法向后工作，并使用我对记法的了解，我可能可以制定一个解决方案。我只是在寻找快速捷径，因此不必重新发明轮子。

哦，请不要将此标签标记为"作业"，我发誓我已经失学了！ ;-)

解决方案

回答

由于RPN也称为后缀表示法，因此我尝试使用谷歌搜索将"后缀转换为中缀"，并获得了很多结果。前几个有代码示例，但是我发现RubyQuiz条目特别具有启发性。

回答

如果我们不担心删除多余的括号，那么下面的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)))))))