Shunting Yard算法的反演是什么？

Question

Dijkstra的Shunting Yard算法用于解析中缀表示法并生成RPN输出.

我正在寻找相反的方法,将RPN转换为highschool-math-class样式中缀表示法,以便从数据库中表示RPN表达式,以便以可理解的方式为用户提供服务.

请节省您的时间,不要自己做算法,只需指出我似乎无法找到的教科书示例.从Shunting Yard算法向后工作并使用我对符号的了解,我可能能够找到解决方案.我只是在寻找快捷方式,所以我不需要重新发明轮子.

哦,请不要将此标记为"作业",我发誓我已经不在学校了!;-)

Answer 1

由于RPN也称为后缀表示法,我尝试谷歌转换"postfix到中缀"并得到了不少结果.前几个有代码示例,但我发现RubyQuiz条目特别有启发性.

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)))))))