Report

DATA STRUCTURE MSc.IT Ali Abdul Karem Habib STACK APPLICATIONS Web browser: stores the addresses of recently visited sites on a stack. Each time a user visits a new site, the address of the site is pushed into the stack of addresses. Use the back button the user can pop pack to previously visited sites! . Text editors: powerful text editors keep text changes in a stack. The user can use the undo mechanism to cancel recent editing operations . ARITHMETIC EXPRESSION An arithmetic expression is one which is evaluated by performing a sequence of arithmetic operations to obtain a numeric value. Levels of Precedence for the usual five binary operations on arithmetic operation Q . Highest: Exponentiation (^) Next Highest: Multiplication (*)and division (/) Lowest: Addition (+) and subtraction (-) PREFIX, POSTFIX & INFIX NOTATION Infix : the operator is placed between operands. Example: (A+B)*C parentheses necessary Prefix: the operator is placed before the operands Example: *+ABC Postfix ( Reveres polish notation): the operator is placed after the operands . Example: AB+C* TRANSFORMING INFIX EXPRESSION INTO PREFIX EXPRESSION (A+B) – (C*D) Step 1 : +AB Step2 : *CD +AB-*CB Prefix :- -+AB*CB TRANSFORMING INFIX EXPRESSION INTO POSTFIX EXPRESSION (A+B) – (C*D) Step 1 : AB+ Step 2 : CD* AB+-CD* Postfix : AB+CD*- TRANSFORM PREFIX TO INFIX : +/*A B C D Note : We will Start the tack operator from the right and the operands from the left . Step 1 : First 2 Operands from the left and first operator from the right . +/(A*B)CD o Step2 : +((A*B)/C)D o Step3 : ((A*B)/C)+D Infix Expression TRANSFORM POSTFIX TO INFIX ABC+– Note :- We will tack the operator from the left and 2 operands from the left also . Step 1 : (A+B)C- Step2 : (A+B)- C EXAMPLE :- INFIX : (7+8)-((6*3)/2)) TRANSFORMED (78+63*2/-) Steps Input Stack 1 7 7 2 8 7 3 + Pop ( 8 and 7 ) push 15 result 4 6 15 6 5 3 15 6 6 * Pop ( 6 and 3 ) push 15 result 18 7 2 15 18 15 9 / pop ( 18 result 8 2 ) push - Pop ( 15 and 9 ) push result 6 TO POSTFIX 8 3 2 Final Result in Stack ASSIGNMENT -41)Convert these INFIX to PREFIX and POSTFIX : A/B–C/D (A + B) ^ 3 – C * D A ^ (B + C) 2)Convert these PREFIX to INFIX and POSTFIX : +–/ABC^DE –+DE/XY ^+23–CD 3)Convert these POSTFIX to INFIX and PREFIX : ABC+– GH+IJ/* AB^CD+ –