Data Structures — Stack

Stack: • A stack is a linear data structure that follows the LIFO (Last In, First Out) principle — the last element inserted is the first one to be removed. • Think of a stack of plates: you add to the top and remove from the top. Basic Operations: 1. push(item): Add an item to the top of the stack. 2. pop(): Remove and return the top item. Raises an error if stack is empty (underflow). 3. peek() / top(): Return the top item without removing it. 4. is_empty(): Check whether the stack is empty (returns True/False). 5. size(): Return the number of items in the stack. Stack Implementation Using Python List: # Python list has append() (push) and pop() (pop from end) # Using the END of the list as the TOP of the stack. stack = [] # empty stack # Push operation def push(stack, item): stack.append(item) # Pop operation def pop(stack): if is_empty(stack): print('Stack Underflow — stack is empty') return None return stack.pop() # removes and returns last element # Peek operation def peek(stack): if is_empty(stack): return None return stack[-1] # last element without removing # Check if empty def is_empty(stack): return len(stack) == 0 # Size def size(stack): return len(stack) # Example usage: s = [] push(s, 10) push(s, 20) push(s, 30) print(s) # [10, 20, 30] print(peek(s)) # 30 print(pop(s)) # 30 print(s) # [10, 20] Applications of Stack: • Expression evaluation (postfix/prefix) • Undo/redo functionality in editors • Browser back button (history) • Function call stack (recursion) • Balanced parenthesis checking

Problem: Given a string containing '(', ')', '{', '}', '[', ']', determine if the brackets are balanced. • Balanced means: every opening bracket has a corresponding closing bracket in the correct order. • Example: '({[]})' → Balanced; '({[})' → Not balanced; '(((' → Not balanced. Algorithm: 1. Create an empty stack. 2. Scan the string character by character: a. If the character is an opening bracket ('(', '{', '['), PUSH it onto the stack. b. If the character is a closing bracket (')', '}', ']'): - If the stack is empty → NOT balanced (no matching opening bracket). - Pop the top element. If it does NOT match the current closing bracket → NOT balanced. 3. After scanning the entire string: - If the stack is empty → BALANCED (all brackets matched). - If the stack is not empty → NOT balanced (unmatched opening brackets remain). Python Implementation: def is_balanced(expr): stack = [] matching = {')': '(', '}': '{', ']': '['} for char in expr: if char in '({[': # opening bracket stack.append(char) elif char in ')}]': # closing bracket if not stack: # stack is empty — no matching open return False top = stack.pop() if top != matching[char]: # wrong match return False return len(stack) == 0 # True if all brackets matched # Test cases print(is_balanced('({[]})')) # True print(is_balanced('({[})')) # False print(is_balanced('((()')) # False print(is_balanced('[]{}()')) # True print(is_balanced('')) # True (empty string is balanced) Time Complexity: O(n) — one pass through the string. Space Complexity: O(n) — stack can hold at most n/2 elements.

Notations for Arithmetic Expressions: 1. Infix Notation: • The operator is placed BETWEEN the two operands. • This is the notation humans normally use. • Requires parentheses and precedence rules to avoid ambiguity. • Example: A + B * C (means A + (B * C) due to precedence) 2. Prefix (Polish) Notation: • The operator is placed BEFORE the operands. • No parentheses needed — unambiguous. • Example: + A * B C (equivalent to A + B * C) 3. Postfix (Reverse Polish Notation — RPN): • The operator is placed AFTER the operands. • No parentheses needed — unambiguous. • Easier for computers to evaluate using a stack. • Example: A B C * + (equivalent to A + B * C) Evaluating a Postfix Expression Using a Stack: Algorithm: 1. Scan tokens left to right. 2. If token is a NUMBER: push onto stack. 3. If token is an OPERATOR (+, -, *, /): a. Pop the TOP element → operand2 b. Pop the NEXT element → operand1 c. Apply the operator: result = operand1 OP operand2 d. Push result back onto stack. 4. After scanning all tokens: the stack contains the final result. Python Implementation: def evaluate_postfix(expression): stack = [] tokens = expression.split() # split by spaces for token in tokens: if token.lstrip('-').isdigit(): # number (handle negatives) stack.append(int(token)) else: operand2 = stack.pop() operand1 = stack.pop() if token == '+': stack.append(operand1 + operand2) elif token == '-': stack.append(operand1 - operand2) elif token == '*': stack.append(operand1 * operand2) elif token == '/': stack.append(operand1 / operand2) return stack[0] # final result # Test: print(evaluate_postfix('5 3 + 2 *')) # (5+3)*2 = 16 print(evaluate_postfix('4 2 3 * +')) # 4 + (2*3) = 10 Why postfix is preferred in computers: • No need for precedence rules or parentheses — the stack naturally handles order of operations.