Stack

Stack Use-cases

1. Post-fix expression evaluation
2. Pre-fix expression evaluation

Post-fix expression evaluation

1. Traverse the given expression left to right
2. if number/operand encountered –>push to stack
3. if operator (+ – * /) encounter –> pop top 2 operand and perform operation –>push the result back to stack
4. repeat steps 2,3 till single operand remains as result

Example :

Input: str = “100 200 + 2 / 5 * 7 +”
Output: 757

Steps explained with diagram:

• https://www.geeksforgeeks.org/evaluation-of-postfix-expression/

Pre-fix expression evaluation

1. Traverse the given expression right to left
2. if number/operand encountered –>push to stack
3. if operator (+ – * /) encounter –> pop top 2 operand and perform operation –>push the result back to stack
4. repeat steps 2,3 till single operand remains as result

Example :

Input : -+8/632
Output : 8

Input : -+7*45+20
Output : 25

Steps explained with diagram:

https://www.geeksforgeeks.org/evaluation-prefix-expressions/