Đảo ngược thuật toán Shunting Yard là gì?

Question

Shunting Yard algorithm của Dijkstra được sử dụng để phân tích cú pháp một ký hiệu infix và tạo ra đầu ra RPN.

Tôi đang tìm cách ngược lại, một cách để biến RPN thành ký hiệu infix kiểu highschool-math-class, để biểu diễn các biểu thức RPN từ cơ sở dữ liệu để đưa người dùng theo cách dễ hiểu.

Hãy tiết kiệm thời gian của bạn và không tự nấu thuật toán, chỉ cho tôi xem các ví dụ về sách giáo khoa mà tôi không thể tìm thấy. Làm việc ngược từ thuật toán Shunting Yard và sử dụng kiến ​​thức của tôi về các ký hiệu có lẽ tôi sẽ có thể giải quyết được một giải pháp. Tôi chỉ đang tìm kiếm một lối tắt nhanh, vì vậy tôi không phải phát minh lại bánh xe.

Ồ, và vui lòng không gắn thẻ tên này là "bài tập về nhà", tôi thề Tôi đã hết giờ học rồi! ;-)

Answer 1

Vì RPN còn được gọi là ký hiệu postfix, tôi đã thử googling convert "postfix to infix" và có khá một vài kết quả. Một số đầu tiên có các ví dụ mã, nhưng tôi thấy số RubyQuiz entry đặc biệt là khai sáng.

Answer 2

Nếu bạn không lo lắng về việc loại bỏ dấu ngoặc không cần thiết, sau đó mã Lisp sau sẽ làm việc:

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