Stacks PDF - IT1815

IT1815 Stacks ▪ For Python, use the if not condition, followed by the stack name and a colon. Fundamentals...

IT1815 Stacks ▪ For Python, use the if not condition, followed by the stack name and a colon. Fundamentals Example: A stack is an ordered list in which the last element added is stack = [] the first element retrieved or removed (Last-In, First-Out). if not stack: Example: A stack of Korean dishes: Kimchi, Bibimbap, print("Stack is empty.") Bulgogi, Japchae Japchae Stack Applications Bulgogi Finding palindromes: A palindrome is a string that reads the Bibimbap same in either direction. Ex. level, radar, civic Kimchi Evaluating a postfix expression: A normal expression is in infix Kimchi, the first item added, is placed on the bottom of the notation. In a postfix expression, the operands (variable or stack; japchae, the last item added, is on the top of the stack. number) precede the operators (symbol). During program execution, the stack can be used to store Algorithm: information about the parameters and return points for all the 1. Classify the token (operand or operator). methods that are currently executing. 2. If token is an operand, push it to the stack. Stacks are used by compilers to store information while 3. If token is an operator, perform two (2) pop operations. evaluating expressions. 4. Perform the operation on the two (2) popped operands The methods of the Stack class from the java.util package based on the operator. Push its result to the stack. are used to implement stacks in Java. 5. Repeat until the end of expression. The list methods are used to implement stacks in Python. Example: 6 4 + 9 3 - * The two (2) main stack operations are the following: Token Operation Evaluation Stack o Push – adds an item to the top of the stack 6 Push 6 6 ▪ Method in Java: push() 4 Push 4 6, 4 Stack stack = new Stack(); + Pop 4 then 6 6 + 4 = 10 10 stack.push("Mairo"); Perform + ▪ Method in Python: append() Push result stack = [] 9 Push 9 10, 9 stack.append("Berlin"); 3 Push 3 10, 9, 3 o Pop – removes an item from the top of the stack - Pop 3 then 9 9-3=6 10, 6 ▪ Method in Java and Python: pop() Perform - Other stack operations: Push result o Peek – looks at the item at the top of the stack without * Pop 6 then 10 10 * 6 60 removing it from the stack Perform * Push ▪ Method in Java: peek() result ▪ Syntax in Python: stack_name[-1] 6 4 + 9 3 - * = 60 o Test whether stack is empty ▪ For Java, use the isEmpty() method. 04 Handout 1 *Property of STI  [email protected] Page 1 of 2  IT1815 Converting from infix to postfix Algorithm: 1. Classify the token (operand or operator). 2. If token is an operand, append it to the postfix expression. 3. If token is an operator, push it to the stack if stack is empty or has higher precedence than the operator on the top of the stack. If it has lower or equal precedence, pop the operator from the top of the stack, append it to the postfix expression, and push the current operator to the stack. 4. If a right parenthesis is encountered, pop all the elements until a left parenthesis is encountered. Append all these elements to the postfix expression except the parentheses. 5. Repeat Steps 1 to 4 until the last token. 6. If there are no more tokens, pop all the operators and append to the postfix expression. Example: (6 / 3 + 2) * (9 - 3) Token Operation Stack Postfix ( Push ( ( 6 Append 6 to postfix ( 6 / Push / (, / 6 3 Append 3 to postfix (, / 63 + +