eShikshak

SPREAD YOUR KNOWLEDGE

You are here: Data Structure STACK Convert Infix to Prefix Expression

Convet Infix to Prefix Expression

User Rating: / 0
PoorBest 
Algorithm to Convert Infix to Prefix Form

Suppose A is an arithmetic expression written in infix form. The algorithm finds equivalent prefix expression B.

Step 1. Push “)” onto STACK, and add “(“ to end of the A

Step 2. Scan A from right to left and repeat step 3 to 6 for each element of A until the STACK is empty

Step 3. If an operand is encountered add it to B

Step 4. If a right parenthesis is encountered push it onto STACK

Step 5. If an operator is encountered then:

a. Repeatedly pop from STACK and add to B each operator (on the top of STACK) which has same or higher precedence than the operator.

b. Add operator to STACK

Step 6. If left parenthesis is encontered then

a. Repeatedly pop from the STACK and add to B (each operator on top of stack until a left parenthesis is encounterd)

b. Remove the left parenthesis

Step 7. Exit

For example : A $ B * C - D + E / F / ( G + H )

Comments  

 
+12 # Krishh 2011-08-06 15:52
It`s a superb website for all kind of programing. Just refer it once may be u will boost in tht subject!!!!!!!! !!!!!!
Reply | Reply with quote | Quote
 
 
-1 # aj 2012-03-01 05:50
we need a source code of it in c++
Reply | Reply with quote | Quote
 
 
0 # aj 2012-03-01 05:59
we need a source code of that
Reply | Reply with quote | Quote
 
 
+3 # Santanu Bera 2012-12-16 14:04
Step 6 a is wrong. It will be "untill right parenthesis is encountered" instead of "left parenthesis is encountered". Please correct the step 6.
Reply | Reply with quote | Quote
 
 
+1 # apoorva 2013-01-22 14:54
need examples and explanation
Reply | Reply with quote | Quote
 
 
+2 # Mitali Ahuja 2013-03-17 11:49
though algorithm is provided but there is a need for explanation by quoting an example.
Reply | Reply with quote | Quote
 
 
+2 # rakesh 2013-07-31 22:48
a-b/(c*d^e)
Reply | Reply with quote | Quote
 
 
+2 # ilai 2013-08-12 21:22
really its superbbbb
Reply | Reply with quote | Quote
 
 
+1 # vneugopal 2013-09-01 16:37
It is quiet easy than you think. follow that reverse the given expression --> convert infix-to-postfix--> reverse obtained result. This will be your answer.
Reply | Reply with quote | Quote
 
 
0 # kousi 2013-09-24 16:01
it is very super
Reply | Reply with quote | Quote
 

Add comment