Sunday, May 19, 2024

Algorithm for infix to postfix expression conversion using stack with example.

 Algorithm for infix to postfix expression conversion-


1. Push left parenthesis '(' into the stack and add right parenthesis ')' at the end of infix expression.
2. Scan expressions from left to right and repeat steps from (3) to (6) for each element of expression until the stack will be empty.
3. If a  operand occurred then add it to the post fix expression.
4. If left parenthesis '(' encountered then push it into the stack.
5. If an operator then performed following steps :-
(a) repeatedly pop each operator from stack which has higher or equal precedence then input operator.
(b) push result and then input operator into the stack.
6. If right parenthesis ')' occurred then perform following steps:-
a. Repeatedly pop each operator from stack until left parenthesis '('  will occurred.
b. Remove left parenthesis '(' from stack and do not add it into P.
7. Exit.

Change following infix expression into prefix and postfix expression.

1.) 5/2 + 4^2 * 3
Sol:- Given expression,
I = 5/2 + 4^2 * 3
Prefix :- oab
= 5/2 + 4^2 * 3
= 5/2 + ^42 * 3
= /52 + ^42 * 3
= /52 + *^423
= +/52*^423
Postfix :- abo
= 5/2 + 4^2 * 3
= 5/2 + 42^ * 3
= 52/ + 42^ * 3
= 52/ + 42^3*
= 52/42^3*+
Using Stack:-

Given expression I = 5/2 + 4^2 * 3)

Sr No

Scanned Symbol

Postfix Expression P

Stack

1

---

---

(

2

5

5

(

3

/

5

(/

4

2

5 2

(/

5

+

52/

(+

6

4

52/ 4

(+

7

^

52/ 4

(+^

8

2

52/ 4 2

(+^

9

*

52/ 42^

(+*

10

3

52/ 42^ 3

(+*

11

)

52/42^3*+

---


2.) ((a*b)/c) - d * e/f
Sol:- Given expression,
I = ((a*b)/c) - d * e/f
Prefix:-
((a*b)/c) - d * e/f
= (*ab /c) - d * e/f
= /*abc - d * e/f
= /*abc - *d e/f
= /*abc - /*def
= -/*abc/*def
Postfix :-
= ((a*b)/c)- d * e/f
= (ab* /c) - d * e/f
= ab*c/ - d * e/f
= ab*c/ - de* /f
= ab*c/ - de*f/
= ab*c/de*f/-
Using stack:-

Given expression I = ((a*b)/c)-d*e/f)

Sr No

Scanned Symbol

Postfix Expression P

Stack

1

---

---

(

2

(

---

((

3

(

---

(((

4

a

a

(((

5

*

a

(((*

6

b

a b

(((*

7

)

ab*

((

8

/

ab*

((/

9

c

ab* c

((/

10

)

ab*c/

(

11

-

ab*c/

(-

12

d

ab*c/ d

(-

13

*

ab*c/ d

(-*

14

e

ab*c/ d e

(-*

15

/

ab*c/ de*

(-/

16

f

ab*c/ de* f

(-/

17

)

ab*c/de*f/-

---


3.) ((a&&b) >c) !! ((d!!e) <f)
Sol:- Given expression,
I = ((a&&b) >c) !! ((d!!e) <f)
Prefix:-
= ((a&&b) >c) !! ((d!!e) <f)
= (&&ab >c) !! (!!de <f)
= >&&abc !! <!!def
= !!>&&abc<!!def
Postfix:-
((a&&b) >c) !! ((d!!e) <f)
= (ab&& >c) !! (de!! <f)
= ab&&c> !! de!!f<
= ab&&c>de!!f<!!

4.) (A+((B-C)*(D-E))+F+G) $ (H-J)
Sol:- Given expression,
I = (((A+((B-C)*(D-E))+F)+G) $ (H-J)
Prefix:-
I = (((A+ ((B-C) * (D-E))+F)+G) $ (H-J)
= (((A+(-BC * -DE))+F)+G) $ (H-J)
= (((A + *-BC-DE) +F)+G) $ (H-J)
= ((+A*-BC-DE +F)+G) $ (H-J)
= (++A*-BC-DEF +G) $ -HJ
= +++A*-BC-DEFG $ -HJ
= $+++A*-BC-DEFG-HJ
Postfix:-
= (((A+((B-C) * (D-E))+F)+G) $ (H-J)
= (((A+ (BC- * DE-)) +F)+G) $ (H-J)
= (((A+ BC-DE-*) +F)+G) $ HJ-
= ((ABC-DE-*+ +F)+G) $ HJ-
= (ABC-DE-*+F+ +G) $ HJ-
= ABC-DE-*+F+G+HJ-$

No comments:

Post a Comment

Priority Queue

Priority queue:-  It is a special type of queue which stores group of elements. Each element has a priority number associated with it. Prior...