Преобразование префикса приоритета оператора - Схема

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 или более традиционный parser-tools.