0

我想编写一个获取和中缀表达式并将其更改为前缀的函数。首先假设我们只处理 + 运算符，所以我想将表达式 1+1+1 更改为： (+ (+ 1 1) 1)

我想使用 foldl 或类似 foldl 的方式来做到这一点：将列表中的第二个项目（始终是操作数）附加到第一个和第三个（按该顺序）然后我想要我们刚刚的表达式附加成为列表中的第一项，因此我将递归地对列表的其余部分执行相同操作。

我试过以下方法：

(lambda (lst)
       (fold-left (lambda (pmLst)
          `(,((cadr pmLst) ,(car pmLst) (caddr pmLst)) ,(cddr pmLst)))
                        '()
                        lst))

但后来我意识到给 fold-left 的 lambda 必须有 2 个参数，但我想处理列表的前 3 个项目。

我希望我已经说清楚了，因为它有点棘手..

4

1 回答 1

0

Afold不会做你想做的事。如果您想象表达式(5 + 3 + 2)，则使用 fold withproc作为过程执行以下操作：

(proc 2 (proc '+ (proc 3 (proc '+ (proc 5 '())))))

一种方法是创建一个函数，在它们自己的列表中返回奇数和偶数元素，这样'(+ 2 - 3)就变成了(+ -) and (2 3)，然后你可以这样做：

(define (infix->prefix expr)
  (if (pair? expr)
      (let-values ([(ops args) (split (cdr expr))])
        (fold (lambda (op arg acc)
                (list op acc (infix->prefix arg)))
              (car expr)
              ops
              args))
      expr))

然而，两者的大小远远大于滚动您自己的递归：

(define (infix->prefix expr)
    (define (aux lst acc)
      (if (pair? lst)
          (aux (cddr lst)
               (list (car lst)
                     acc
                     (infix->prefix (cadr lst))))
          acc))

    (if (pair? expr)
        (aux (cdr expr) (infix->prefix (car expr)))
        expr))

(infix->prefix '(1 + 2 - 3))
; ==> (- (+ 1 2) 3)

这里没有运算符优先级。一切都严格从左到右。

于 2016-11-24T12:26:21.837 回答