Что такое инверсия алгоритма Шунтирующего двора?

Question

Алгоритм Дейкстры Шунтирующий двор используется для анализа инфиксной записи и генерирования RPN выходных данных.

Я ищу противоположный способ превращения RPN в инфиксную нотацию в стиле highschool-math-class для представления выражений RPN из базы данных для понятного понимания пользователей.

Пожалуйста, сэкономьте свое время и не придумывайте алгоритм самостоятельно, просто укажите мне примеры из учебников, которые я не могу найти. Работая в обратном направлении от алгоритма Shunting Yard и используя мои знания об обозначениях, я, вероятно, смогу найти решение. Я просто ищу быстрый способ, поэтому мне не нужно изобретать велосипед.

О, и, пожалуйста, не помечайте это как "домашнюю работу", я клянусь Я уже вне школы! ; -)

Answer 1

Поскольку RPN также известен как постфиксная нотация, я попробовал поискать преобразование "постфикс в инфикс" и получил довольно много результатов. Первые несколько имеют примеры кода, но я нашел запись RubyQuiz особенно интересной.

Answer 2

Если вы не беспокоитесь об удалении лишних скобок, тогда будет работать следующий код на Лиспе:

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