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

Я пытаюсь понять, как преобразовать инфиксное выражение в префикс в схеме.

Я нашел этот пост, который делает то, что я хочу, но в противоположном направлении. Что изменится при переходе с инфикса->префикса вместо префикса->инфикса?

Изменить: я забыл упомянуть, что мне нужно учитывать и обрабатывать переменные. Например, ввод

'(2 + 3 * a ^ 5 + b)


prefix infix-notation scheme
person user3277752    schedule 27.10.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Довольно тривиально изменить алгоритм, на который вы ссылаетесь:

(define (infix->prefix lst)
  (cond
    ((list? lst) 
     (unless (= 3 (length lst)) (error "not 3 elements"))
     (let ((operand1 (car lst))
           (operator (cadr lst))
           (operand2 (caddr lst)))
       (list operator
             (infix->prefix operand1)
             (infix->prefix operand2))))
    (else lst)))

Тестирование:

> (infix->prefix '(1 + 2))
'(+ 1 2)
> (infix->prefix '(1 + (2 * 3)))
'(+ 1 (* 2 3))
> (infix->prefix '((1 / 4) + (2 * 3)))
'(+ (/ 1 4) (* 2 3))

Однако это не общий алгоритм; если вам нужно что-то более сложное, пожалуйста, покажите несколько примеров конверсий, которые вам нужно сделать.

ИЗМЕНИТЬ Вот пример кода, который работает для более длинных выражений, но не реализует приоритет операторов:

(define (infix->prefix lst)
  (if (list? lst)
      (if (null? (cdr lst))
          ; list with one element -> return element
          (infix->prefix (car lst))
          ; list with more than one element
          (list (cadr lst)
                (infix->prefix (car lst))
                (infix->prefix (cddr lst))))
      ; not a list -> return element
      lst))

Тестирование:

> (infix->prefix '(2 + 3 * a ^ 5 + b))
'(+ 2 (* 3 (^ a (+ 5 b))))
person uselpa    schedule 27.10.2014
comment
Да, это то, что мне нужно, но я забыл добавить в описание, что мне нужно также учитывать возможные переменные. Например, как бы я разобрал строку '(2 + 3 * a ^ 5 + b). - person user3277752; 28.10.2014
comment
Переменные не проблема, например (infix->prefix '(2 + (3 * a))) даст '(+ 2 (* 3 a)). Но что не учитывается, так это 1) выражения из более чем 3 элементов и 2) приоритет операторов. Поэтому, пожалуйста, добавьте несколько полезных примеров (ввод и вывод). - person uselpa; 28.10.2014
comment
ИМХО, приведенная выше программа не может обработать такое выражение, как (инфикс-›префикс '(1 + (2 + 3))), и выдаст результат в виде (+ 1 (2 + 3)). Но мы можем внести небольшую корректировку: (if (null? (cdr lst)) ; list with one element -> return element (car lst) ======› (if (null? (cdr lst)) ; list с одним элементом -> возвращаемый элемент (infix-prefix (car lst)) - person CodingNow; 24.10.2017