CODEWITHSUNDEEP
recursionconvertersprefixinfix-notationstack
user2258295
user2258295

Reputation: 21

Calculating and converting prefix to infix

I'm having some serious problems writing a program that convert prefix to infix. I have already written 2 programs which use stacks but do so differently - one used two stacks, the other used one with a recursive method. But I'm still having problems correctly doing it since the requirements demands that it use two stacks (operand and operator) and use a recursive method. I'm having serious problems visualizing both of those requirements together. Does anyone knows what the algorithm would look like? if i could simply have an algorithm, it would really be a life saver. Thank you

Upvotes: 1

Views: 2679

Answers (1)

GoZoner
GoZoner

Reputation: 70165

This does it.

(define (prefix->infix pre)
  (cond ((list? pre)
         (assert (= 3 (length pre)))
         (let ((operator (list-ref pre 0))
               (operand1 (list-ref pre 1))
               (operand2 (list-ref pre 2)))
           (list (prefix->infix operand1)
                 operator
                 (prefix->infix operand2))))
        (else pre)))

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

It doesn't use 'stacks' explicitly (but the recursions use a call stack).

Upvotes: 2

Related Questions