Что такое инверсия алгоритма Shunting Yard?

Dijkstra алгоритм Shunting Yard используется для анализа инфиксной нотации и генерации выход RPN.

Я ищу обратное, чтобы превратить RPN в нотацию infix в стиле high-school-math-class, чтобы представлять выражения RPN из базы данных, чтобы проложить пользователей понятным способом.

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

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

Ответ 1

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

Ответ 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)))))))