12

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

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

请节省您的时间，不要自己编写算法，只需向我指出我似乎找不到的教科书示例。从Shunting Yard 算法向后工作，并利用我对符号的了解，我可能能够找到一个解决方案。我只是在寻找一个快速的捷径，所以我不必重新发明轮子。

哦，请不要将其标记为“作业”，我发誓我已经离开学校了！;-)

4

2 回答 2

7

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

于 2008-09-17T19:52:50.457 回答
6

如果您不担心删除多余的括号，那么下面的 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)))))))
于 2008-09-17T19:59:53.217 回答