Find the prefix and postfix notation for the following infix expression:

 

(a + b – c) * (e / f) – ( g – h/i)

There is a quick way to convert from one notation to another. You start by inserting all the implicit brackets/parentheses that determine the order of evaluation, regardless of what notation the expression is already in. So, taking the expression above and adding these implicit brackets gives:

This is before:
(a + b - c) * (e / f) - ( g - h/i)

This is after adding the implicit parentheses:
( ( ( (a + b) - c) * (e / f)) - ( g - (h/i)))

Now, in order to convert from one notation to another using the bracketed form, you would move the operator in each bracketed expression. Where you move the operator depends on the notation that you want to convert to.

Postfix vs. Prefix Notation

If you want to convert to postfix notation, you would move the operator to the end of the bracketed expression, right before the closing brace. To convert to prefix notation, you would move the operator to the beginning of the bracketed expression, right after the opening brace. So, (h/i) in postfix notation would look like (h i /), and in prefix notation would look like (/ h i ). Do this for every operator in a bracket. So, converting the expression above to prefix notation will give you:

Moving all the operators to the beginning of the 
bracketed expression for prefix notation gives us:
( - ( *  (  - ( + a b) c)  ( / e f))  ( - g ( / h i ) ) )

And finally, removing all the parentheses gives us our final prefix notation:

- * - + a b c / e f - g / h i

Try figuring out how to get the postfix notation on your own using the rules given above. You should get this as your answer:

a b + c - e f / * g h i / - -

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.



FOLLOW Varoon Sahgal, Author of ProgrammerInterviewon