Ch21-Stacks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stacks\n",
    "<a href=\"https://colab.research.google.com/github/rambasnet/FDSPython-Notebooks/blob/master/Ch23-Stacks.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>\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",
       "        <iframe\n",
       "            width=\"900\"\n",
       "            height=\"500\"\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",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.IFrame at 0x1049d97f0>"
      ]
     },
     "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
}