{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Stacks\n", "\"Open\n", "\n", "http://openbookproject.net/thinkcs/python/english3e/stacks.html\n", "\n", "- container adapters or abstract data type (ADT) that may use list or linked-list as containers to hold data\n", "- specifically designed to operate as a LIFO (last-in-first-out) or FILO (first-in-last-out) data structure \n", " - last item added is the first to be removed\n", "- built-in alternative: deque - https://docs.python.org/3/library/collections.html#collections.deque\n", " \n", "## The Stack ADT\n", "- an ADT is defined by the operations that can be performed on it, called an interface.\n", "- interface of stack consists of the following basic operations:\n", " - \\__init__ - initialize a new empty stack\n", " - \\__len__ - returns length/size of the stack\n", " - push - add a new item to the stack\n", " - pop - remove and return last item that was added to the stack\n", " - is_empty - check if the stack is empty" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implementing stack with Python list\n", "- Python list provides a several methods that we can take advantage of to emulate Stack ADT" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "class Stack:\n", " def __init__(self):\n", " self.items = []\n", " \n", " def __len__(self):\n", " return len(self.items)\n", " \n", " def push(self, item):\n", " self.items.append(item)\n", " \n", " def pop(self):\n", " return self.items.pop()\n", " \n", " def is_empty(self):\n", " return len(self.items == 0)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Applications of stack" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "s = Stack()\n", "s.push(54)\n", "s.push(45)\n", "s.push('+')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## visualize stack with pythontutor\n", "https://goo.gl/Q4wZaL" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import IFrame\n", "src = \"\"\"\n", "http://pythontutor.com/iframe-embed.html#code=class%20Stack%3A%0A%20%20%20%20def%20__init__%28self%29%3A%0A%20%20%20%20%20%20%20%20self.items%20%3D%20%5B%5D%0A%20%20%20%20%0A%20%20%20%20def%20__len__%28self%29%3A%0A%20%20%20%20%20%20%20%20return%20len%28self.items%29%0A%20%20%20%20%0A%20%20%20%20def%20push%28self,%20item%29%3A%0A%20%20%20%20%20%20%20%20self.items.append%28item%29%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20def%20pop%28self%29%3A%0A%20%20%20%20%20%20%20%20return%20self.items.pop%28%29%0A%20%20%20%20%0A%20%20%20%20def%20is_empty%28self%29%3A%0A%20%20%20%20%20%20%20%20return%20len%28self.items%20%3D%3D%200%29%0A%20%20%20%20%20%20%20%20%0As%20%3D%20Stack%28%29%0As.push%2854%29%0As.push%2845%29%0As.push%28'%2B'%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=false&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\n", "\"\"\"\n", "IFrame(src, width=900, height=500)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## using a stack to evaluate postfix notation\n", "- infix notation: 1 + 2\n", "- prefix notation: + 1 2\n", "- postfix notation: 1 2 +\n", " - operator follows the operands\n", " - no need to use parenthesis to control oder of operations\n", "- algorithm steps:\n", " 1. starting at the beginning of the expression, get one term/token (operator or operand) at a time\n", " a. if the term is an operand, push it on the stack\n", " b. if the term is an operator, pop two operands off the stack, perform the operation on them, and push the result back on the stack\n", " 2. When you get to the end of the expression, there should be exactly one operand left on the stack, the result." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "# given a postfix notation such as: 56 47 + 2 *, the following function evaluates the result using Stack ADT\n", "def eval_postfix(expr):\n", " tokens = expr.split()\n", " stack = Stack()\n", " for token in tokens:\n", " token = token.strip()\n", " if not token:\n", " continue\n", " if token == '+':\n", " s = stack.pop() + stack.pop()\n", " stack.push(s)\n", " elif token == '*':\n", " prod = stack.pop() * stack.pop()\n", " stack.push(prod)\n", " # /, and - are left as exercise\n", " else:\n", " stack.push(int(token))\n", " \n", " return stack.pop()\n", " " ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "206\n" ] } ], "source": [ "print(eval_postfix('56 47 + 2 *'))" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "206" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# which is same as: (56 + 47) * 2 in infix notation\n", "eval('(56 + 47) * 2')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## exercises\n", "1. Write a function that converts infix notation to postfix notation, e.g., given infix notation $4 - 2 + 3$ the program should output corresponding postfix notation $4 \\ 2 - 3\\ +$\n", "\n", "## Following Kattis problems can be solved using Stack\n", "1. Backspace problem: https://open.kattis.com/problems/backspace\n", "- Game of throwns: https://open.kattis.com/problems/throwns\n", "- Even Up Solitaire: https://open.kattis.com/problems/evenup\n", "- Working at the Restaurant: https://open.kattis.com/problems/restaurant\n", "- Pairing Socks: https://open.kattis.com/problems/pairingsocks\n", "- Find stack-based problems in Kattis: https://cpbook.net/methodstosolve search for stack" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" } }, "nbformat": 4, "nbformat_minor": 2 }