Infix to Postfix,
Prefix
Conversion
Whythere is a need to
convert Infix Strings
to Postfix or Prefix?
Algorithm used
Postfix
Step 1. Push “)” onto STACK, and add “(“ to
end of the A
Step 2. Scan Infix from right to left and repeat
step 3 to 6 for each element of Infix until the
STACK is empty
Step 3. If an operand is encountered add it to
Postfix
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
Postfix, 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 encountered then
a. Repeatedly pop from the STACK and add
to Postfix (each operator on top of stack until
a left parenthesis is encountered)
b. Remove the left parenthesis
Step 7. Exit
Infix to postfix conversion
infixVect
(a+b-c)*d–(e+f)
postfixVect
Infix to postfix conversion
stackVect
infixVect
a+b-c)*d–(e+f)
postfixVect
(
Infix to postfix conversion
stackVect
infixVect
+b-c)*d–(e+f)
postfixVect
a
(
Infix to postfix conversion
stackVect
infixVect
b-c)*d–(e+f)
postfixVect
a
+
(
Infix to postfix conversion
stackVect
infixVect
-c)*d–(e+f)
postfixVect
ab
+
(
Infix to postfix conversion
stackVect
infixVect
c)*d–(e+f)
postfixVect
ab+
-
(
Infix to postfix conversion
stackVect
infixVect
)*d–(e+f)
postfixVect
ab+c
-
(
Infix to postfix conversion
stackVect
infixVect
*d–(e+f)
postfixVect
ab+c-
Infix to postfix conversion
stackVect
infixVect
d–(e+f)
postfixVect
ab+c-
*
Infix to postfix conversion
stackVect
infixVect
–(e+f)
postfixVect
ab+c-d
*
Infix to postfix conversion
stackVect
infixVect
(e+f)
postfixVect
ab+c–d*
-
Infix to postfix conversion
stackVect
infixVect
e+f)
postfixVect
ab+c–d*
(
-
Infix to postfix conversion
stackVect
infixVect
+f)
postfixVect
ab+c–d*e
(
-
Infix to postfix conversion
stackVect
infixVect
f)
postfixVect
+ ab+c–d*e
(
-
Infix to postfix conversion
stackVect
infixVect
)
postfixVect
+ ab+c–d*ef
(
-
Infix to postfix conversion
stackVect
infixVect
postfixVect
ab+c–d*ef+
-
Infix to postfix conversion
stackVect
infixVect
postfixVect
ab+c–d*ef+-
Infix to Prefix
Step 1: Reverse the given Input
String
Step 2: Convert the reversed string
into postfix expression
Step 3: Reverse the Postfix string to
find the required Prefix String.
Examples(Solve using Stack
as well as direct conversion)
(A*B)+C
A +( ( B * C) – ( D/E^F)
*G)
Practice Examples
1. A + ( B + D) / E-F * (
G + H/K)
2. (A – B ) * ( D / E )
3. ( A + B – D )/ (E – F) +
G
Practice Examples(Cont.)
4. A – b / ( c ^ d) + ( e * f)
5. A * (b + c) + (b / d) * a
+z*u
Answer for Question 4 is:
-A+/B^CD*EF +/(-
Answer for Question 5 is:
+*A +b c +* /b d a * z u
Practice Examples(Cont.)
( A + B – D )/ (E – F) + G
Answer:
A B+D-EF-/G
Practice Examples
1) x ^ y / (5 * z) + 10
Ans: x y ^ 5 z * / 10 +
Practice Examples(Cont.)
( A + B) – D + E / (F – G)
+H
Answer:
A B +D- EFG – / + H +
Practice Examples(Cont.)
( A + B) – (D + E )/ (F – G) + (H * I)
Answer:
A B + D E + FG- / - H I * +
Practice Examples(Cont.)
( A + B – D + E )/ (F – G + H
* I * J * K / L) + M
Answer:
AB+D-E+FG-HI*J*K*L/+/M+
