converting Infix to prefix conversion

Question

Recently I have went through some sites, for converting the Infix to Prefix notation and finally got tucked up.

I have given the steps which I have done..

Ex:- (1+(2*3)) + (5*6) + (7/8)

Method 1:- (Manual Conversion without any algorithm):-

Step1: (1+(*23)) + (*56) + (/78)  

Step2: (+1*23) + (*56) + (/78) 

Step3: +(+1*23)(*56) + (/78) 

Step4: +[+(+1*23)(*56)](/78) 

Step5: +++1*23*56/78            **--- Final Ans -----** 

Method 2:-

As per the site http://scanftree.com/Data_Structure/infix-to-prefix

Step1: Reverse it:-
       ) 8 / 7 ( + ) 6 * 5 ( + ) ) 3 * 2 ( + 1 ( 

Step2: Replace the '(' by ')' and vice versa:
       ( 8 / 7 ) + ( 6 * 5 ) + ( ( 3 * 2 ) + 1 ) 

Step3: Convert the expression to postfix form:-
       8 7 / 6 5 * + 3 2 * 1 + + 

Step4: Reverse it
       + + 1 * 2 3 + * 5 6 / 7 8     --- Final Ans -----

So, here I got totally hanged.

Could any one please provide some light on following things:-

1. On where I went wrong in the above 2 methods
2. Which is the right answer

so I can able to understand the concept more better.

Answer 1

The Manual conversion is correct because when we reverse the infix expression to calculate the prefix, the associativity of the expression changes from left to right to right to left which is not considered in the algorithm and often it is ignored.

Example: expression:5-3-2 :infix to prefix(manual conversion) (-5 3)-2 -(- 5 3) 2 - - 5 3 2

now by the algorithm(if associativity not changed) reverse expression: 2 - 3 - 5

postfix: 2 3 - 5 -

again reverse to get prefix: - 5 - 3 2

now see if we ignored the associativity, it made a huge difference

now if we change the associativity from left to right to right to left:

then :

reverse expression: 2 - 3 - 5

postfix: 2 3 5 - - (like a^b^b to postfix: abc^^ because it is also right associative)

reverse - - 5 3 2

Answer 2

(b * b - 4 * a * c ) / (2 * c) EQUATION--1;
Now I will solve this mathematically by substituting different variables, and doing 2 terms at time.
=> x=bb* ; y=4a* ; z=2c*
these above are the substitution of first time, use in eq 1
( x - y * c )/(z)
again doing the substitutions with new variables.
=> i=yc* ;
(x - i)/z
=> j=xi-;
j/z
Now this here is the base case solve it then substitute back all the variables accordingly.
jz/
Now back substitution

xi- 2c* /
bb* yc * - 2c* /

bb* 4a* c * -2a*/

Answer 3

Your method is not correct, look at the comment, it says that ( a + b ) + c = a + ( b + c ) . What about (a + b) * c? (a + b) * c != a + (b * c). According to your manual algorithm, you put the last + is placed to the front. It is not correct. If you use * instead of last + , where did you put it ? Just think about that, then you can easily find the problem with your algorithm. Another algorithm for solving this problem is just parenthesis it before proceeding. Replace every left parenthesis with the operator inside it. Example, ((1+(2*3)) + ((5*6) + (7/8))) then it become ++1*23+*56+/78. Your algorithm is correct if the precedence of the operator inside is same. If it is not it will fail.

NOTE : Your answer can also be obtained by the arrangement of parenthesis. (((1+(2*3)) + (5*6)) + (7/8)) then it becomes +++1*23*56/78. But if the last one is * instead of + then it doesn't work.