CODEWITHSUNDEEP
racketpostfix-mtaprefix
Dilanlius
Dilanlius

Reputation: 7

racket postfix to prefix

I have a series of expressions to convert from postfix to prefix and I thought that I would try to write a program to do it for me in DrRacket. I am getting stuck with some of the more complex ones such as (10 (1 2 3 +) ^).

I have the very simple case down for (1 2 \*) → (\* 1 2). I have set these expressions up as a list and I know that you have to use cdr/car and recursion to do it but that is where I get stuck.

My inputs will be something along the lines of '(1 2 +).

I have for simple things such as '(1 2 +):

(define ans '())
(define (post-pre lst)
  (set! ans (list (last lst) (first lst) (second lst))))

For the more complex stuff I have this (which fails to work correctly):

(define ans '())
(define (post-pre-comp lst)
  (cond [(pair? (car lst)) (post-pre-comp (car lst))]
        [(pair? (cdr lst)) (post-pre-comp (cdr lst))]
        [else (set! ans (list (last lst) (first lst) (second lst)))]))

Obviously I am getting tripped up because (cdr lst) will return a pair most of the time. I'm guessing my structure of the else statement is wrong and I need it to be cons instead of list, but I'm not sure how to get that to work properly in this case.

Upvotes: 0

Views: 750

Answers (2)

uselpa
uselpa

Reputation: 18917

Were you thinking of something like this?

(define (pp sxp)
  (cond
    ((null? sxp) sxp)
    ((list? sxp) (let-values (((args op) (split-at-right sxp 1)))
                   (cons (car op) (map pp args))))
    (else sxp)))

then

> (pp '(1 2 *))
'(* 1 2)
> (pp '(10 (1 2 3 +) ^))
'(^ 10 (+ 1 2 3))

Upvotes: 1

Alexis King
Alexis King

Reputation: 43842

Try something like this:

(define (postfix->prefix expr)
  (cond
    [(and (list? expr) (not (null? expr)))
     (define op (last expr))
     (define args (drop-right expr 1))
     (cons op (map postfix->prefix args))]
    [else expr]))

This operates on the structure recursively by using map to call itself on the arguments to each call.

Upvotes: 0

Related Questions