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

Я пишу функцию, которая берет арифметическое инфиксное выражение в кавычках, включающее числа, переменные и операторы, и преобразует его в префиксную нотацию.

Например:

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

будет оценивать

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

or 

(+ (+ 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))))

Это правильный порядок, но круглые скобки отключены из-за приоритета. Я провел некоторое исследование, и мне трудно понять, как его добавить.

Любые отзывы или предложения о том, как реорганизовать мой код, были бы потрясающими. Спасибо!


prefix operator-precedence infix-notation scheme
person user2762848    schedule 24.02.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

По сути, это проблема парсинга. Существует множество различных способов решения этой проблемы, но ни один из них не тривиален, за исключением полностью заключенных в скобки. Но, по-видимому, весь смысл этого заключался в использовании инфикса без круглых скобок.

Если бы я пытался реализовать это быстро, я бы использовал один из существующих пакетов парсера для Racket; возможно, parsack или ragg или более традиционный инструменты-parser.

person John Clements    schedule 24.02.2016
comment
Спасибо! Задание предназначено для класса, и я не думаю, что мы можем использовать ракетку, но я рассмотрю его для получения дополнительной помощи. - person user2762848; 24.02.2016
comment
Если это для класса, ваш инструктор наверняка направляет вас к определенной технике синтаксического анализа...? - person John Clements; 25.02.2016
comment
... или, может быть, она или он просто хочет, чтобы вы сначала разбили его, используя операторы с самым низким приоритетом, а затем подразделили, пока не получите полное дерево? В любом случае, я предполагаю, что конкретная стратегия была описана в задании. - person John Clements; 25.02.2016
comment
да. Я сделал функцию для проверки приоритета. У меня просто проблемы с тем, где применить эту функцию и как. Если у меня есть новый код, где я могу его добавить? В качестве редактирования? Новое в этом. - person user2762848; 25.02.2016