CODEWITHSUNDEEP
schemeprefixinfix-notation
user3277752
user3277752

Reputation: 579

Infix to Prefix conversion scheme

I'm trying to figure out how to convert an infix expression to prefix in Scheme.

I found this post which does what I want but in the opposite direction. What changes when going from infix->prefix instead of prefix->infix?

Edit: I forgot to mention I need to account and handle for variables. For example the input

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

Upvotes: 1

Views: 5735

Answers (1)

uselpa
uselpa

Reputation: 18917

It's rather trivial to modify the algorithm you link to:

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

Testing:

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

This is not a general algorithm though; if you need something more elaborate then please show some examples of conversions you need to do.

EDIT Here's an example code that works for longer expressions but doesn't implement operator precedence:

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

Testing:

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

Upvotes: 2

Related Questions