运算符优先级前缀转换 - 方案

Question

我正在编写一个函数，该函数采用带引号的算术中缀表达式，包括数字、变量和运算符，并将其转换为前缀表示法。

例如：

 (infix->prefix '(2 + 3 * x ^ 5 + a))

将评估为

(+ 2 (+ (* 3 (^ x 5)) a))

或

(+ (+ 2 (* 3 (^ x 5))) a)

按优先级顺序，我们有：+,-,*，/和 ^。

这就是我到目前为止所拥有的

 (define (infix->prefix lst) 
   (if (list? lst)
   (if (null? (cdr lst))
      (car lst)
      (list (cadr lst)
            (infix->prefix (car lst))
            (infix->prefix (cddr lst)))
      )
   lst)
  )

这提供了正确的前缀表示法，但没有优先级。它的计算结果为

(+ 2 (* 3 (^ x (+ 5 a))))

这是正确的顺序，但由于优先级，括号已关闭。我已经做了一些研究，很难弄清楚如何添加它。

关于如何重构我的代码的任何反馈或建议都会很棒。谢谢！

Answer 1

本质上，这是解析的问题。有很多不同的方法可以解决这个问题，但没有一个是微不足道的，除了完全括号。但据推测，这样做的全部意义在于使用不带括号的中缀。

如果我试图快速实现这一点，我会使用现有的Racket解析器包之一;也许是Parsack或ragg或更传统的解析器工具。