ラケットRPN検証ツール

Question

私は現在、ラケットで逆ポーランド記法プログラムを作成しようとしています。私は6つの数字と5つの演算子を持ちたいと思います。演算子はリストに-1で表され、数字はリストで-1で表されます。

以下のコードでは、重複のないリストのすべての順列を得ることができます。有効なRPNの場合は、開始時に2つの数字を、最後に1つの演算子が必要なため、リストの先頭に2つの-1を追加し、最後に1を追加します。

;This our original list to create reverse polish notation -1 will represent operators 
;and 1 will represent numbers. It doesnt have two -1's and one 1 because for valid 
;reverse polish notaion it needs to start with two nummbers and end with an operator 
(define start-perm (list -1 -1 -1 -1 1 1 1 1)) 

;This line creates all permutations of the original RPN list and it removes the duplicates 
(define perms (remove-duplicates (permutations start-perm))) 

;This function adds the two 1s to the front of the list and the -1 to the end of the list 
(define (make-rpn l) 
(append (list 1 1) l (list -1))) 

(make-rpn (car perms)) 
; adds 1 1 to start of all permutations and adds -1 to the end of all permutations 
(map make-rpn perms) 

問題は、有効なRPNだけが出力できないことです。研究を通して、スタックが最良のアプローチだと思われますが、このコードに実装されているようです。どんな助けでも大歓迎です。

Answer 1

最も簡単な解決策は、おそらく入力を反転させると、（通常の）ポーランド記法のための再帰下降パーサにそれを渡している。

(define (validate rpn) 
    (define/match (go pn) 
    [(`(1 . ,rest)) rest] 
    [(`(-1 . ,rest)) (let ([rest^ (go rest)]) 
         (and rest^ (go rest^)))] 
    [(else) #f]) 
    (null? (go (reverse rpn)))) 

（さておき、それは記号を使用して明確にされるであろうように、「言いますnumと 'op、1と-1の代わりに）