Qual é a inversão do algoritmo Manobras Yard?

Question

Manobras Quintal algoritmo é usado para analisar um infix notação e gerar a saída RPN .

Eu estou procurando o oposto, uma maneira de transformar RPN para a notação infix estilo colegial-math-classe, de modo a representar expressões RPN a partir de um banco de dados para usuários leigos de uma forma compreensível.

Por favor, salve o seu tempo e não cozinhar os mesmos algoritmos, apenas me apontar exemplos de livros didáticos que eu não consigo encontrar. Trabalhando para trás do quintal algoritmo de manobras e usando o meu conhecimento sobre as notações I, provavelmente, vai ser capaz de trabalhar até uma solução. Estou apenas à procura de um atalho rápido, então eu não tem que reinventar a roda.

Oh, e por favor não marcar esta como "dever de casa", I jura eu estou fora da escola já! ; -)

Answer 1

Desde RPN também é conhecido como notação postfix, eu tentei googling converso "postfix para infix" e tem muito poucos resultados. A primeira vários têm exemplos de código, mas eu achei o RubyQuiz entrada particularmente esclarecedor.

Answer 2

Se você não está preocupado com a remoção parênteses redundantes, então o seguinte código Lisp funcionará:

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