Evaluation of postfix expression using stack

data structure

1. ELECTRINICS & COMMUNICATION ENGINEERING DEPARTMENT TOPIC : EVALUATION OF POSTFIX EXPRESSION USING STACK Name : Shubhajit Chatterjee Student Code : BWU/BEC/19/028 Registration Number : 19013000936 of 2019-2020 Roll Number : 19010308024 Course Name :Data Structures and Algorithm Course code : ESC(ECE)301 Programme : Bachelor of Technology in Electronics & Communication Engineering Semester : 3rd

2. ELECTRINICS & COMMUNICATION ENGINEERING DEPARTMENT What is Postfix Expression : The ease of evaluation acts as the driving force for computers to translate an infix notation into a postfix notation. That is, given an algebraic expression written in infix notation, the computer first converts the expression into the equivalent postfix notation and then evaluates the postfix expression . Both these tasks—converting the infix notation into postfix notation and evaluating the postfix expression—make extensive use of stacks as the primary tool. Using stacks, any postfix expression can be evaluated very easily.

3. ELECTRINICS & COMMUNICATION ENGINEERING DEPARTMENT Evaluation rule of a Postfix Expression states : While reading the expression from left to right, push the element in the stack if it is an operand . Pop the two operands from the stack, if the element is an operator (*,+,-,/,.. etc ) and then evaluate it. Push back the result of the evaluation. Repeat it till the end of the expression .

4. ELECTRINICS & COMMUNICATION ENGINEERING DEPARTMENT ALGORITHM FOR POSTFIX EXPRESSION : STEP 1:-  Add ‘#’ to postfix expression. STEP 2:-  Read postfix expression Left to Right until ‘#’ encountered STEP 3:-  If operand is encountered, push it onto Stack [End If] STEP 4:-  If operator is encountered, Pop two elements i ) A->Top element ii) B-> Next to Top element iii) Evaluate B operator A push B operator A onto Stack STEP 5:-  Set  result = pop STEP 6:-  END

5. STEP INPUT OPERATION STACK CALCULATION 1 8 Push 8 2 4 Push 8,4 3 3 Push 8,4,3 4 * Pop(2elements) & evaluate 8 4*3=12 5 Push result(12) 8,12 6 6 Push 8,12,6 7 / Pop(2elements) & evaluate 8 12/6=2 8 Push result(2) 8,2 9 - Pop(2elements) & evaluate Empty 8-2=6 10 Push result(6) 6 11 No more elements(Pop) Empty 6 (Result) ELECTRINICS & COMMUNICATION ENGINEERING DEPARTMENT Evaluate Postfix Expression :843*6/-

6. ELECTRINICS & COMMUNICATION ENGINEERING DEPARTMENT Example : 843*6/- 8 4 3 Push 8,4,3 Stack is empty Top Top Pop 3,4 8 12 4*3=12 Push 12 Top 8 12 6 Push 6 Top 8 Pop 6,12 Top 12/6=2 Push 2 8 2 Top Top 6 8-2=6 Push 6 Pop 2,8 Stack empty Pop6 Ans=6 8 Empty

7. ELECTRINICS & COMMUNICATION ENGINEERING DEPARTMENT THANK YOU