Data Structures & Algorithms
101009/IT200C (Module 2)
S2 CU
Mr. Tinku Soman Jacob
Asst. Prof IT
RSET
1
Index
• Infix to Prefix Expression Conversion
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 2
Infix to Prefix Expressions conversion
• Rule – Operators are taken out of the stack as long as their incoming
operator’s priority is less than instack priority.
• Eg: A-B+C*D/E -> E/D*C+B-A -> EDC*/BA-+ -> +-AB/*CDE
3
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous)
Infix to Prefix Expressions conversion
• Eg: A-(B+C)*D/E -> E/D*)C+B(-A -> EDCB+*/A- -> -A/*+BCDE
4
Conversion of infix expression to prefix
• Start
• Read expression to exp.
• Reverse the exp.
• Repeat following steps until exp[i]==‘\0’
• If exp[i]==operand, print exp[i].
• Else
• If stack is empty or contains a left parenthesis’)‘, push the incoming operator onto stack
• If exp[i]== ‘)‘, push to stack.
• If exp[i]== ‘(’ pop from stack till ‘)‘ and print operators.
• If prec(exp[i]) > prec(stack[top]), push onto stack.
• If prec(exp[i]) < prec(stack[top]), pop and print stack[top] until condition false, then push(exp[i])
• If equal precedence, use associativity rules
• R to L pop and print stack[top] until condition false, then push(exp[i])
• L to R then push incoming operator.
• If exp[i]==‘\0’, pop and print all operators in the stack.
• Finally, reverse_S2the resultant expression.
CU_Module-2
101009/IT200C Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 5
Expression conversion-Tutorial
1. A – (( B+C) * D)/E
2. P+Q/R-S
3. A*(B+C) * D
4. (A+B)*D+E/(F+A*D)+C
5. (A+(B*C-(D/E-F)*G)*H)
6. (m-n)/p*q+r ^ s*t
7. ((A/(B-D+E))*(F-G)*H)
Infix to Postfix and Prefix Conversion
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 6