Answer to Question #228178 in Algorithms for umme habiba sumi

Question

Consider the following infix expression

Q: ((A+C)*D)ꜛ(B+F/E)+G use POLISH Algorithm to translate Q into its equivalent postfix expression P.

Let A, B, C, D, E, F, G, H be eight data items with the following assigned weights:

Data item: A B C D E F G H

Weight: 20 7 11 17 5 10 24 6

Construct Binary tree using Huffman Algorithm also find the path length of the tree.

Answer 1

1)

S=((A+C)*D)^(B+F/E)+G infis string

RES= "" = postfix string

STACK=""- stack of operations;

2)

S=(A+C)*D)^(B+F/E)+G

RES=""

_STACK=(

3)

S=A+C)*D)^(B+F/E)+G

RES=""

_STACK=((

4)

S=+C)*D)^(B+F/E)+G

RES=A

STACK=((

5)

S=C)*D)^(B+F/E)+G

RES=A

STACK=((+

6)

S=)*D)^(B+F/E)+G

RES=AC

_STACK=((+

7)

_{S=*D)^(B+F/E)+G}

RES=AC+

STACK=(

8)

S=D)^(B+F/E)+G

RES=AC+

STACK=(*

9)

S=)^(B+F/E)+G

RES=AC+D

STACK=(*

10)

S=^(B+F/E)+G

RES=AC+D*

STACK=

11)

S=(B+F/E)+G

RES=AC+D*

STACK=^

12)

_S=B+F/E)+G

RES=AC+D*

_STACK=^(

13)

S=+F/E)+G

RES=AC+D*B

STACK=^(

14)

S=F/E)+G

RES=AC+D*B

STACK=^(+

15)

S=/E)+G

RES=AC+D*BF

STACK=^(+

16)

S=E)+G

RES=AC+D*BF

STACK=^(+/

17)

S=)+G

RES=AC+D*BFE

STACK=^(+/

18)

S=+G

RES=AC+D*BFE/+

STACK=^

19) ^ has bigger priority than +

S=G

RES=AC+D*BFE/+^

STACK=+

20)

S=

RES=AC+D*BFE/+^G

STACK=+

21)

S=

STACK=

RES=AC+D*BFE/+^G+

AC+D*BFE/+^G+ equivalent postfix expression P

Task 2: