CS201 Data Structures and Algorithm Design Lecture 6 PDF

CS201 Data Structures and Algorithm Design Lecture 6 Stack ADT Faculty of Computers Science & Artificial Intelligence  Lecture’s Contents Stack: Introduction. Stack Mechanism. Stack Operations. Some Applications of Stacks....

CS201 Data Structures and Algorithm Design Lecture 6 Stack ADT Faculty of Computers Science & Artificial Intelligence  Lecture’s Contents Stack: Introduction. Stack Mechanism. Stack Operations. Some Applications of Stacks. Implementing a Stack.  Using a List (Array).  Using a Linked List. Prefix, Infix, Postfix Notation. Convert Prefix, Infix, Postfix. Exercises. Evaluate Postfix expressions using stacks. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 2  Stack: Introduction A stack is a linear data structure of ordered items such that items can be inserted and removed only at one end. A stack is an Abstract Data Type (ADT). The order may be LIFO (Last In First Out) or FILO (First In Last Out). There are many real-life examples of a stack: Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 3  Stack Mechanism Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 4  Some Applications of Stacks 1) Expression Conversion: An expression can be represented in prefix, postfix or infix notation. Stack can be used to convert one form of expression to another. 2) Expression Evaluation: Stack is used to evaluate prefix, postfix and infix expressions. 3) Syntax Parsing: Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. 4) Parenthesis Checking: Stack is used to check the proper opening and closing of parenthesis. 5) String Reversal: Stack is used to reverse a string. We push the characters of string one by one into stack and then pop characters from stack. 6) Implement undo operation in an editor. 7) Implementing function calls (including recursion). Method calls are placed onto a stack :  Call  push, return  pop) Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 5  Stack Operations Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 6  Stack Operations The operations of stack data structure work as follows:  A pointer called TOP is used to keep track of the top element in the stack.  When initializing the stack, the stack is empty when (TOP == -1)  For pushing, increase the TOP value (TOP = TOP + 1) and place the new element in the position pointed to by TOP.  On popping, reduce Top value by 1 (TOP = TOP - 1)  Note:  Before pushing, check if the stack is already full.  Before popping, we check if the stack is already empty. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 7  Stack Operations Stack underflow:- When we try to pop an item off the stack when the stack is empty. Stack overflow:- When we try to push an item into the stack when the stack is full. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 8  Implementing a Stack There are two ways we can implement a stack: 1) Using a List or an array (List). 2) Using a linked list. 1) Implementing a stack using a list or an array is fairly easy:-  The bottom of the stack is at stack  The top of the stack is at stack [top-1]  Push onto the stack at stack [top] , top ++  Pop off of the stack at stack [top-1], top -- In the context of the stack ADT, we can adapt Python’s list class using the correspondences shown in next Table. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 9  Implementing a Stack (Cont.) There are two ways we can implement a stack: 1) Using a List or an array (List). 2) Using a linked list. 2) Implementing a stack using a linked list isn’t that bad either…:-  Store the items in the stack in a linked list.  The top of the stack is the head node, the bottom of the stack is the end of the list.  Push by adding to the front of the list.  Pop by removing from the front of the list. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 10  Implementing a Stack using a List top=0 smax=int(input("Enter Maximum size of stack: ")) Program to implement a stack using a list def createStack(): stack=[] Enter Maximum size of stack: 5 return stack Enter the elements: alaa def Push(stack,item): alaa Pushed to stack stack.append(item) Add more element (0 /1):1 print(item, " Pushed to stack") stack=createStack() Enter the elements: Omar ch=1 Omar Pushed to stack while ch != 0: Add more element (0 /1):1 if top Null stack.push(30) stack.push(50) Top element: 50 # Displaying the stack Popped element: 50 stack.display() Popped element: 30 # Peeking at the top element Top --> 20 -> 10 -> Null print("\nTop element:", stack.peek()) # Popping elements from the stack print("Popped element:", stack.pop()) print("Popped element:", stack.pop()) # Displaying the updated stack stack.display() Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 18  Prefix, Infix, Postfix Notation In infix form an operator is written in between two operands  6 + 4 8 + 2 * 5 – (5+3) In Prefix an operator is written before (Follows) the two operands, notation was introduced by the Polish logician (Lukasiewicz) , and is sometimes called “Polish notation”. 4*5  *45 In Postfix an operator is written after (precedes) operands, this notation is sometimes called “Reverse Polish Notation” or RPN. 8/2  82- Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 19  Prefix, Infix, Postfix Notation Infix notation: Operator appears between operands:  2+35  2 + 3 * 4 2 + (3 * 4 ), Prefix notation: Operator precedes operands:  +235  + 2 * 3 5 + 2 * 3 5 + 2 15 17 Postfix notation: Operator follows operands:  23+5  2 3 * 5 + 2 3 * 5 + 6 5 + 11 Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 20  Convert Prefix, Infix, Postfix Answer: With postfix and prefix notations, parentheses are no longer needed! Infix postfix prefix a+b*c abc*+ +a*bc (a + b) * c ab+c* *+abc a + (b * c) abc*+ +a*bc Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 21  Exercise 1 Convert From Infix to Postfix and Prefix 1) A + B * C / D 2) (A + B) * (C / D) 3) A * B / C 4) 5 + 8 – 2 5) 4 + 3 * 5 6) 7 * (10 – 6) + 5 Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 22  Answer 1) A + B * C / D Postfix  A B C * D / + Prefix  + A / * B C D ---------------------------------------------------------------------------------------------------------------- 2) (A + B) * (C / D) Postfix  A B + C D / * Prefix  * + A B / C D ---------------------------------------------------------------------------------------------------------------- 6) 7 * (10 – 6) + 5 Postfix  7 10 6 - * 5 + Prefix  + * 7 - 10 6 5 Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 23  Exercise 2 Convert from Postfix to Infix and Prefix 1) 3 r – 2) 1 3 r – + 3) 4 5 – a b + * 4) s t * 1 3 r - + + 5) v w x y z * – + * 6) A B C * / D – Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 24  Answer 1) 3 r - Infix  3 - r Prefix  - 3 r ------------------------------------------------------------ 4) s t * 1 3 r - + + Infix  s * t + 1 + ( 3 – r) Prefix  + + * s t 1 – 3 r Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 25  Convert the following Table Infix Postfix Prefix +AB AB+CD+* A–B/(C*D^E) 2-3*4+5 234*5+- Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 26  Evaluate Postfix expressions using stacks Evaluate the following Expression using Stack: 45+72-* To evaluate the postfix expression using a stack we use the following algorithm: If current character is operand then  push it into the stack. If current character is operator:  popped the 2 values from stack.  put the operator between two operands  push in the stack Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 27  Evaluate Postfix expressions using stacks Evaluate the following Expression using Stack: 45+72-* Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 28  Exercise Evaluate the following expression in postfix : 623+–382/+*2^3+  Final answer is:  49  51  52  7  None of these Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 29  Exercises True or False Questions: 1) In Stack, insertion operation is known as Push whereas deletion operation is known as Pop ( T / F ) 2) When function calls another function then the details of previous function are stored in Stack ? (T / F ) Choose the correct output for the following questions: 1) Which of the following can be used to implement stack? A) Array or List B) Linked List C) Tree D) A or B 2) The term Push and Pop is related to A) Queue B) Linked List C) Tree D) Stack 3) Process of inserting an element in stack is called ____________ A) Create B) Insert C) Push D) Pop 4) Which statement is correct with respect to stack? A) It is a primitive data structure B) It is a LIFO data structure C) It is a First in first out (FIFO) structure D) All of the above Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 30  Exercises Choose correct output for the following sequence of operations. A) 8 5 2 5 1 B) 8 5 5 2 1 C) 8 2 5 5 1 D) 8 1 2 5 5 Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 31  Exercises Choose correct output for the following sequence of operations. A) 2 1 2 2 2 B) 2 1 2 2 1 C) 2 2 1 1 2 D) 2 2 1 2 2 Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 32  Using Stack for Matching Parentheses We can use a stack for testing for pairs of matching delimiters, we consider arithmetic expressions that may contain various pairs of grouping symbols, such as:- Parentheses: “(” and “)” Braces: “{” and “}” Brackets: “[” and “]” Each opening symbol must match its corresponding closing symbol. For example, a left bracket, “[,” must match a corresponding right bracket, “],” as in the expression [(5+x)-(y+z)]. The following examples further illustrate this concept:  Correct: ( ){[]}  Correct: ( )(( )){([( )])}  Correct: ((( )(( )){([( )])}))  Incorrect: )(( )){([( )])}  Incorrect: ({[])}  Incorrect: ( Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 33  Using Stack for Matching Parentheses def matchexpr(expr): def createStack(): lefty = "({[" # opening delimiters stack=[] righty = ")}]" Please Enterclosing # respective an Expression delims to evalute: (){}[()] return stack S = createStack() ( Pushed to stack def isEmpty(stack): for c in expr: { Pushed to stack s=len(stack) if c in lefty: [ Pushed to stack if s==0: return True Push(S,c) (# push left to Pushed delimiter stack on stack else: return False elif c in righty: your expression (){}[()] is good... if isEmpty(S): def Push(stack,item): return False # nothing to match with stack.append(item) if righty.index(c) != lefty.index(Pop(S)): print(item, " Pushed to stack") return False # mismatched def Pop(stack): return True # were all symbols matched? if isEmpty(stack): return "stack underflow" stack=createStack() return stack.pop() st=input("Please Enter an Expression to evalute: ") if matchexpr(st): print("your expression {} is good...".format(st)) else: print("your expression {} is Not good...".format(st)) Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 34