球拍RPN验证器

Question

我目前正在尝试在球拍中创建一个反向波兰语符号程序。我希望在列表中有6个数字和5个operators.Numbers表示为-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。)