infix to prefix

Question

Convert following infix to prefix expression

e^d-a*b^f/g+h*c/i+j-k

Explain each step

Answer 1

Precedence rule : ^ > ( / = * ) > (+ = -)

Step 1 : ^ed - a* ^bf /g + h*c / i + j - k

Step 2 : ^ed -/ *a^bfg + h*c /i +j -k    (Since * , / has same precedence we go by the associativity that is left to right .)

Step 3 : ^ed - / *a ^ bfg + /* hci + j-k

Step 4 : -^ed  / *a ^bfg + / *hci + j-k

Step 5:  + - ^ed /*a^bfg/*hci + j-k

Step 6 : ++-^ed/*a^bfg/*hcij-k

Step 7 : -++-^ed/*a^bfg/*hcijk

Comments

Are you sure you've got it correct?

Shouldn't it be the following? $$-++-\wedge\; ed/*a\wedge bfg/ * hcijk$$

---

Yes pragy you are right thanks for correcting me : Edited :)

---

if i start from end-

 

k

Stack -

kj

Stack -+

 

shouldn't we pop - here as it has the same precedence as compared to + ?

Answer 2

An easy method would be to use a stack. Reverse the infix expression. And if there are parentheses, treat them with opposite meaning i.e. '(' -> ')' and vice versa and convert the reversed string accordingly. Now simply perform infix to postfix conversion. But it is important to observe that the string has been reversed and therefore pay attention to the associativity of the operators while popping. And finally, reverse the resulting string to obtain the prefix expression.

Note: Consider 2^3^4: the right ^ has higher precedence than the left one. They are not considered to have the equal precedence. Also, during conversion from infix to postfix for this example [^,^] is present in the stack at the same time and the left one is not popped. Similarly for infix to prefix, since we reverse the string the higher precedence ^ comes on the left and thus requires popping if such a situation arises. 

INPUT	Stack	O/P
e^d-a*b^f/g+h*c/i+j-k (Reverse)
k-j+i/c*h+g/f^b*a-d^e
+i/c*h+g/f^b*a-d^e	-	kj
/c*h+g/f^b*a-d^e	-,+	kji
c*h+g/f^b*a-d^e	-,+,/	kji
+g/f^b*a-d^e	-,+,/,*	kjich
g/f^b*a-d^e	-,+,+	kjich*/
^b*a-d^e	-,+,+,/	kjich*/gf
*a-d^e	-,+,+,/,^	kjich*/gfb
-d^e	-,+,+,/,*	kjich*/gfb^a
^e	-,+,+,-	kjich*/gfb^a*/d
	-,+,+,-,^	kjich*/gfb^a*/de
		kjich*/gfb^a*/de^-++-
Answer:		-++-^ed/*a^bfg/*hcijk (Reversed)

I have skipped through obvious steps. Also note that +,+ is in the stack at the same time because the higher precedence '+' is on top of the lower precedence one. Hence it should not be popped.

Comments

nice answer..very helpful