Algorithms to convert the infix to postfix

[.BZU.]

23rd September, 2008

Data Structure

Algorithms to convert the infix to postfix:
Symbols used
SS è Scanned symbol(jis symbol pa operation ho gas wo scanned symbol kehlay ga.i.e a+b ma jab ham “a” ko dekhen gy to wo scanned symbol ho ga.isi trha apni bari pa “+” or phir “b”)
PE è Post Expression
OS è Operator Stack
Steps of Algorithms:
Step 1:-
If SS is operand

• Push in the P.E

Step 2:-
If SS is “( )”
·Push in OS
Step 3:-
If scanned symbol is “)” (closing paranthesis)

• Move elements from OS to P.E until ‘(’(beginning parenthesis) is found
• Also remove “ ( “

Step 4:-
If SS is operator
·If empty(OS) or Top(OS) is “(”
Put it into OS
Else
·If priority of (SS)>= priority of top(OS)
Push it to OS
Else
Move elements from OS to PE until priority (SS)<priority of Top(OS)
Or Top(OS) is “(”
Or Top(OS) is empty
·Push SS to OS
Step 5:-
If SS is #
Move all elements from OS to PE
If
è(a+b) / (c*d-e)
Is a given expression then

Ø(expression ko dekhen to is ma scanned symbol “(” ha.jo k operator ha.
Algorithem k mutabic is ka 4th step true ho gaya to phir is ko ham O.S ki traf push kr den gyn )
O.S:

(






P.E:












Øab SS hmara pas “a” ha jo k algorithem ha or algorithem k 1st step k mutabic is ko ham P.E ki traf push kr den gyn.

O.S
(







P.E
a








Øab “+” hmary pas SS ha.ya ak operator ha .4th step ko consider krty huy is kjo O.s ma push jkr den gyn.
O.S

(
+






P.E

a
















Øab hmary pas SS “b ” ha jo k ak operand ha to 1st step k mutabic isko P.E ma push kr dety han
O.S

(
+






P.E

a
b






Øab SS ‘ )’ ha to algoriithem ka 3rd step k mutabic Os sa element P.E ki traf move krana han yahan tk k ‘(’ na a jay.phir “(” ko OS ma sa remove kr dena ha.
ØAgr ham is step ko dekhen to ab hamre pas ‘)’ SS ha.to OS k elements ko PE ki traf move kraty han.’+’ P.E ma chala jay ga.algorihem k mutabic jb ‘(’ ay ga to is ko remove kr den gen or Os k elements ko move krana bhi khatam kr den gen.
ØJb esa kren gay to hmare pas postfix ma kch esa ay ga…
O.S
(ya empty ho jay ga coz ‘+’ to P.e ma chala gaya or ‘(’ ko remove kr dea gaya).









P.E

a
b
+





·Ab SS ma / ha.ya ak operator ha.Algorithm k 4th step k mutabic
“(If empty (OS) or Top (OS) is “(”Put it into OS” isko OS ma daal dyn gy.
O.S

/







P.E

a
b
+














Ø(expression ko dekhen to is ma scanned symbol “(” ha.jo k operator ha.
Algorithem k mutabic is ka 4th step true ho gaya to phir is ko ham O.S ki traf push kr den gyn )
O.S:

/
(





P.E:

A
b
+







Øab SS hmara pas “c” ha jo k algorithem ha or algorithem k 1st step k mutabic is ko ham P.E ki traf push kr den gyn.

O.S
/
(






P.E
a
b
+
c



·ab “*” hmary pas SS ha.ya ak operator ha .4th step ko consider krty huy is kjo O.s ma push jkr den gyn.is ma bhi ham “If empty(OS) or Top(OS) is “(”
Put it into OS” is point ko consider kren gy.hmara pas top(OS) ma ‘(’ than a so…
O.S

/
(
*





P.E

a
b
+
c



Øab SS hmara pas “d” ha jo k algorithem ha or algorithem k 1st step k mutabic is ko ham P.E ki traf push kr den gyn.

O.S
/
(
*





P.E
a
b
+
c
d










ab “-” hmary pas SS ha.ya ak operator ha .4th step ko consider krty han.is step k point ko dekhen jis ma likha ha k” Move elements from OS to PE until priority (SS)<priority of Top(OS)
Or Top(OS) is “(”
Or Top(OS) is empty
ØPush SS to OS”.pura step parhen or phir is mentioned point kpa ghor kren.
Ø“*” P.E ma move kr jay ga.is k bad top(OS) “(” ha to movement ko yahin rokta han.and “-” ko OS ma push kr dety han.
O.S

/
(






P.E

a
B
+
C
d
*

Øab SS hmara pas “e” ha jo k algorithem ha or algorithem k 1st step k mutabic is ko ham P.E ki traf push kr den gyn.

O.S
/
(
-












P.E
a
b
+
c
d
*
e







Øab SS ‘ )’ ha to algoriithem ka 3rd step k mutabic Os sa element P.E ki traf move krana han yahan tk k ‘(’ na a jay.phir “(” ko OS ma sa remove kr dena ha.
ØAgr ham is step ko dekhen to ab hamre pas ‘)’ SS ha.to OS k elements ko PE ki traf move kraty han.’’ Or ya k .algorihem k mutabic jb ‘(’ ay ga to is ko remove kr den aen or Os k elements ko move krana bhi bad kr den gen.
ØJb esa kren gay to hmare pas postfix ma kch esa ay ga…
O.S
( yahan per OS ma “-” P.E ki traf chala jay ga.is k bad “(“ a jata ha isko remove kr k movement ko yahin rok dena ha.).

/











P.E

a
b
+
c
d
*
e
-

All Credit goes to Madiha..

Download the attachment for easy understanding

[BSIT07-01]

Thnx Madiha & bzu