球拍RPN驗證器

Question

我目前正試圖在球拍中創建一個逆波蘭表示法程序。我想要有6個數字和5個運算符。數字在列表中用-1表示，而運算符在列表中用1表示。

在下面的代碼中，我可以得到沒有重複列表的所有排列。我在列表的前面添加兩個-1，最後添加一個-1，這是因爲對於有效的RPN，它需要在開始時有兩個數字，在末尾有一個運算符。

;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。）