Application of Stack For Expression Evaluation by Prakash Zodge DSY 41.pptx

In short...The stack organization is very effective in evaluating arithmetic expressions. Expressions are usually represented in what is known as Infix notation, in which each operator is written between two operands (i.e., A + B)....

1. Topic : “Application of Stack For Expression Evaluation” P.E.S. COLLEGE OF ENGINEERING Name : Zodge Prakash Rajesh Roll No. : B-41 Department : CSE Semester : IV

2. Contents What is Stack? Concept of Stack Stack Operations PUSH & POP ALGORITHMS FOR PUSH & POP ALGORITHM FOR PEEP ARITHMATIC EXPRESSION APPLICATION OF STACK EXPRESSION CONVERSION INFIX, PREFIX & POSTFIX NOTATIONS ALGORITHMS REFERENCES

3. What is Stack? A stack is an Abstract Data Type (ADT) Stack is an important data structure which stores its elements in an ordered manner.

4. Concepts of Stack LIFO data structure

5. Stack Operations PUSH – The process of putting a new data element onto stack is known as a Push Operation. POP – Accessing the content while removing it from the stack, is known as a Pop Operation.  PEEK – Get the data of top element of stack, return the value of the top element

6. PUSH Operation The push operation is used to insert an element in to the stack.

7. POP Operation The pop operation is used to delete the topmost element from the stack.

8. Algorithm for PUSH & POP Algorithm to PUSH an element in a stack Step 1: IF TOP = MAX-1, then PRINT “OVERFLOW” Goto Step 4 [END OF IF] Step 2: SET TOP = TOP + 1 Step 3: SET STACK[TOP] = VALUE Step 4: END Algorithm to POP an element from a stack Step 1: IF TOP = NULL, then PRINT “UNDERFLOW” Goto Step 4 [END OF IF] Step 2: SET VAL = STACK[TOP] Step 3: SET TOP = TOP - 1 Step 4: END

9. Algorithm for PEEP Operation Algorithm for Peep Operation Step 1: IF TOP = NULL, then PRINT “STACK IS EMPTY” Go TO Step 3 [END OF IF] Step 2: RETURN STACK[TOP] Step 3: END

10. Arithmetic Expression Arithmetic expressions have Operands & Operators (+,-,*,/,%) Priority conventions are Brackets [Highest Priority - I] ~ Unary minus [Highest Priority - II] *,/,% [Medium Priority] +,- [Low Priority]

11. Applications of Stack Express Evaluation Ex. 5 * ( 6 + 2 ) Where ( 6 +2 ) = 8  will be evaluated first. Parenthesis Matching Ex. ( a + b ) * ( c + d) Whereas, (a + b * [c + d )  is not a valid expression Expression Conversion Infix, Prefix & Postfix Memory Management

12. Expression Conversion Converting one form of expressions to another is one of the important applications of stacks.

13. Infix Notation Writing an arithmetic expression using infix notation, the operator is placed between the operands. Ex. A+B Here, plus operator is placed between the two operands A and B.

14. Postfix Notation Postfix notation was given by Jan Łukasiewicz The operator is placed after the operands Ex. Infix : ( A + B ) Postfix : A B + A postfix operation does not even follow the rules of operator precedence. No parentheses Ex. Infix : ( A + B ) * C Postfix : A B + C *

15. Prefix Notation The operator is placed before the operands Ex. Infix : A + B Prefix : + A B The expression (A + B) * C is written as: * + A B C in the prefix notation

16. Infix to Postfix Algorithm Scan the infix expression from left to right.  If the scanned character is an operand, output it.  Else,        1  If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.        2  Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)  If the scanned character is an ‘(‘, push it to the stack.  If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.  Repeat steps 2-6 until infix expression is scanned.  Print the output  Pop and output from the stack until it is not empty.

17. Continue…

18. Infix to Prefix Algorithm Step 1: Reverse the infix expression i.e A+B*C will become C*B+A. Note while reversing each ‘(‘ will become ‘)’ and each ‘)’ becomes ‘(‘. Step 2: Obtain the “nearly” postfix expression of the modified expression i.e CB*A+. Step 3: Reverse the postfix expression. Hence in our example prefix is +A*BC.

19. Continue…

20. Postfix to Infix Algorithm While there are input symbol left 1.1 Read the next symbol from the input. If the symbol is an operand 2.1 Push it onto the stack. Otherwise, 3.1 the symbol is an operator. 3.2 Pop the top 2 values from the stack. 3.3 Put the operator, with the values as arguments and form a string. 3.4 Push the resulted string back to stack. If there is only one value in the stack 4.1 That value in the stack is the desired infix string

21. Continue…

22. Postfix to Prefix Algorithm Read the Postfix expression from left to right If the symbol is an operand, then push it onto the Stack If the symbol is an operator, then pop two operands from the Stack  Create a string by concatenating the two operands and the operator before them.  string = operator + operand2 + operand1  And push the resultant string back to Stack Repeat the above steps until end of Prefix expression.

23. Continue…

24. References https://prepinsta.com/ https://www.geeksforgeeks.org/ https://www.tutorialspoint.com/ https://www.faceprep.in/

25. Thank You