stack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack is FIFO abstract data structure "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class ArrayStack:\n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return len(self._data) == 0\n",
    "    \n",
    "    def push(self, e):\n",
    "        self._data.append(e)\n",
    "        \n",
    "    def top(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "        return self._data[-1]   # the last item in list\n",
    "    \n",
    "    def pop(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "        return self._data.pop()\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "False\n",
      "5\n",
      "True\n",
      "9\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "S = ArrayStack( )\n",
    "S.push(5)\n",
    "S.push(3)\n",
    "print(len(S))\n",
    "print(S.pop( ))\n",
    "print(S.is_empty( ))\n",
    "print(S.pop( ))\n",
    "print(S.is_empty( ))\n",
    "S.push(7)\n",
    "S.push(9)\n",
    "print(S.top( ))\n",
    "S.push(4)\n",
    "print(len(S))\n",
    "print(S.pop( ))\n",
    "S.push(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Analyze the array-based stack implementation\n",
    "<pre>\n",
    "|  Operation    |   Running Time|\n",
    "|---------------|---------------|\n",
    "|  S.push(e)    |   O(1)*       |\n",
    "|  S.pop()      |   O(1)*       |\n",
    "|  S.top()      |   O(1)        |\n",
    "|  S.is_empty() |   O(1)        |\n",
    "|  S.len()      |   O(1)        |\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reserving capacity stack\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack usage "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def reserve_file(filename):\n",
    "    s = ArrayStack()\n",
    "    original = open(filename)\n",
    "    for line in original:\n",
    "        s.push(line.rstrip('\\n'))\n",
    "    original.close()\n",
    "    \n",
    "\n",
    "    \n",
    "    output = open(filename, 'w')\n",
    "    while not s.is_empty():\n",
    "        output.write(s.pop() + '\\n')\n",
    "    output.close()\n",
    "    \n",
    "reserve_file('test_file.txt')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def match_parentheses(expr):\n",
    "    lefty = '[({'\n",
    "    righty = '])}'\n",
    "    \n",
    "    s = ArrayStack()\n",
    "    for c in expr:\n",
    "        if c in lefty:\n",
    "            s.push(c)\n",
    "        elif c in righty:\n",
    "            if s.is_empty():\n",
    "                return False\n",
    "            if righty.index(c) != lefty.index(s.pop()):\n",
    "                return False\n",
    "    \n",
    "    return s.is_empty()\n",
    "\n",
    "match_parentheses('{[(5+3)/2 - 3] + (4-1)*2}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def match_html_tag(raw):\n",
    "    s = ArrayStack()\n",
    "    \n",
    "    j = raw.find('<')\n",
    "    while j != -1:\n",
    "        k = raw.find('>', j+1)\n",
    "        if k == -1:\n",
    "            return False\n",
    "        tag = raw[j+1:k]\n",
    "        if not tag.startswith('/'):\n",
    "            s.push(tag)\n",
    "        else:\n",
    "            if s.is_empty():\n",
    "                return False\n",
    "            if tag[1:] != s.pop():\n",
    "                return False\n",
    "        j = raw.find('<', k+1)\n",
    "    \n",
    "    return s.is_empty()\n",
    "\n",
    "aaa='''<body>\n",
    "<center>\n",
    "<h1> The Little Boat </h1>\n",
    "</center>\n",
    "<p> The storm tossed the little\n",
    "boat like a cheap sneaker in an\n",
    "old washing machine. The three\n",
    "drunken fishermen were used to\n",
    "such treatment, of course, but\n",
    "not the tree salesman, who even as\n",
    "a stowaway now felt that he\n",
    "had overpaid for the voyage. </p>\n",
    "<ol>\n",
    "<li> Will the salesman die? </li>\n",
    "<li> What color is the boat? </li>\n",
    "<li> And what about Naomi? </li>\n",
    "</ol>\n",
    "</body>'''\n",
    "raw = '''<a> aaaa </a>'''\n",
    "\n",
    "match_html_tag(aaa)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### Stack with max length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Full(Exception):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "class ArrayStackMaxLength:\n",
    "    def __init__(self, maxlen):\n",
    "        self._maxlen = maxlen\n",
    "        self._data = [] \n",
    "        \n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return __len__() == 0\n",
    "        \n",
    "    def push(self, e):\n",
    "        if self.__len__() == self._maxlen:\n",
    "            raise Full('Stack is full')\n",
    "        self._data.append(e)\n",
    "        \n",
    "    def top(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "        return self._data[-1]\n",
    "    \n",
    "    def pop(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "        self._data.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "s = ArrayStackMaxLength(2)\n",
    "s.push(1)\n",
    "s.push(2)\n",
    "#s.push(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Reserve stack elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<__main__.ArrayStack object at 0x7f7b3c4a3cc0>\n",
      "<__main__.ArrayStack object at 0x7f7b3c4a3cc0>\n"
     ]
    }
   ],
   "source": [
    "def transfer(S, T):\n",
    "    \"\"\"Transfer all elements from stack S to stack T, so that element that starts at the top of S\n",
    "    is first to be inserted onto T, and the element at the bottom of S ends up at the top of T\"\"\"\n",
    "    while not S.is_empty():\n",
    "        elem = S.top()\n",
    "        T.push(elem)\n",
    "        S.pop()\n",
    "        \n",
    "        \n",
    "def reserve_elements(S):\n",
    "    \"\"\"Reserve elements order\"\"\"\n",
    "    T = ArrayStack()\n",
    "    transfer(S,T)\n",
    "    transfer(T,S)\n",
    "    \n",
    "S = ArrayStack()\n",
    "S.push(1)\n",
    "S.push(2)\n",
    "S.push(3)\n",
    "print(S)\n",
    "\n",
    "reserve_elements(S)\n",
    "\n",
    "print(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Match html tag which has attributes\n",
    "Trong bài toán này lỗi thường gặp gồm:\n",
    "- Tìm \">\" nhưng không tìm \" \" để so sánh trường hợp nào gặp trước\n",
    "- Trường hợp đặc biệt có \">\" nhưng không có \" \" thì phải gán k = vị trí \">\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "def match_html_tag_extend(raw):\n",
    "    S = ArrayStack()\n",
    "    j = raw.find('<')\n",
    "    \n",
    "    while j != -1:\n",
    "        k = raw.find('>', j + 1)\n",
    "        if k > raw.find(' ', j+1) and raw.find(' ', j+1) != -1:\n",
    "            k = raw.find(' ', j+1)\n",
    "\n",
    "        if k == -1:\n",
    "            return False\n",
    "        tag = raw[j+1:k]\n",
    "        \n",
    "        if not tag.startswith('/'):\n",
    "            S.push(tag)\n",
    "        else:\n",
    "            if S.is_empty():\n",
    "                return False\n",
    "\n",
    "            if not tag[1:] == S.pop():\n",
    "                return False\n",
    "        \n",
    "        j = raw.find('<',k+1)\n",
    "        \n",
    "    return S.is_empty()\n",
    "        \n",
    "raw = '''<body>\n",
    "<center>\n",
    "<h1> The Little Boat </h1>\n",
    "</center>\n",
    "<p name='hoanghamobile'> The storm tossed the little\n",
    "boat like a cheap sneaker in an\n",
    "old washing machine. The three\n",
    "drunken fishermen were used to\n",
    "such treatment, of course, but\n",
    "not the tree salesman, who even as\n",
    "a stowaway now felt that he\n",
    "had overpaid for the voyage. </p>\n",
    "<ol>\n",
    "<li> Will the salesman die? </li>\n",
    "<li> What color is the boat? </li>\n",
    "<li> And what about Naomi? </li>\n",
    "</ol>\n",
    "<table padding=\"3\" cell=\"2\">\n",
    "<row> aaa </row>\n",
    "</table>\n",
    "</body>'''\n",
    "\n",
    "print(match_html_tag_extend(raw))\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### Enumerating permutation "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Bài toán: Liệt kê tất cả các hoán vị của tập n phần tử từ 1 tới n. \n",
    "\n",
    "Thuật toán: \n",
    "    Sử dụng thuật toán Fisher-Yates là phương pháp sinh để liệt kê các hoán vị. Do các phần tử có tính thứ tự nên hoán vị đầu tiên sẽ là <1, 2, ..., n> và hoán vị cuối cùng là <n, n-1, ..., 2, 1>. \n",
    "Hoán vị sinh ra sau sẽ lớn hơn hoán vị hiện tại, hơn thế nữa chỉ vừa đủ lớn hơn theo nghĩa không có một hoán vị nào khác có thể xen vào giữa hai hoán vị đó.\n",
    "\n",
    "Giả sử hoán vị hiện tại là <3, 2, 6, 5, 4, 1>, xét 4 phần tử cuối, ta thấy chúng được xếp theo thứ tự giảm dần, điều đó có nghĩa là dù ta có hoán vị các phần tử này thế nào thì vẫn bé hơn hoán vị hiện tại. Như vậy ta phải xét đến x[1]=2, thay nó bằng một giá trị khác. Ta sẽ thay bằng giá trị nào?, không thể là 1 được vì sẽ được hoán vị bé hơn, không thể là 3 vì x[0]=3 đã được chọn. Còn lại các giá trị 4, 5, 6. Vì cần một hoán vị vừa đủ lớn nên ta chọn x[1]=4, còn các giá trị x[2], x[3], x[4], x[5] sẽ lấy trong {2, 6, 5 ,1}. Cũng vì tính vừa đủ lớn nên ta sẽ lấy hoán vị nhỏ nhất của 4 số này là 1,2,5,6. Tức hoán vị mới là <3,4,1,2,5,6>.\n",
    "\n",
    "Nhận xét giữa hai hoán vị trên ta có thuật toán như sau:\n",
    "Xác định đoạn cuối giảm dần dài nhất, tìm phần tử x[i] đứng liền trước đoạn cuối đó. \n",
    "    \n",
    "    Nếu tìm thấy chỉ số i trên, tìm trong đoạn cuối giảm dần phần tử x[k] nhỏ nhất thỏa mãn x[k] > x[i]. Do đoạn cuối giảm dần, điều này thực hiện bằng cách tìm từ cuối dãy lên đầu dãy gặp chỉ số k đầu tiên thỏa mãn x[k] > x[i].\n",
    "        Đảo giá trị x[i], x[k]\n",
    "        Lật ngược thứ tự đoạn cuối từ x[i+1] tới x[k] trở thành tăng dần.\n",
    "    Nếu không tìm thấy tức là toàn dãy đã sắp giảm dần, đây là hoán vị cuối cùng."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def printPermutation(X):\n",
    "    for i in X:\n",
    "        print(i, end=\" \")\n",
    "    print(\"\\n\")\n",
    "        \n",
    "\n",
    "def permutation(X):\n",
    "    printPermutation(X)\n",
    "    n = len(X)\n",
    "    if n == 0:\n",
    "        return\n",
    "    \n",
    "    while True:\n",
    "        i = n - 2\n",
    "        while X[i] > X[i+1] and i >= 0:\n",
    "            i -= 1\n",
    "    \n",
    "        if i == -1:\n",
    "            return\n",
    "        else:\n",
    "            k = n-1\n",
    "            while X[i] > X[k]:\n",
    "                k -= 1\n",
    "            X[i], X[k] = X[k], X[i]\n",
    "            \n",
    "            Y=X[i+1:n]\n",
    "            Y.reverse()\n",
    "            X[i+1:n]=Y\n",
    "\n",
    "            printPermutation(X)\n",
    "        \n",
    "        \n",
    "permutation([])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### Enumerating subset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Liệt kê tất cả các tập con của tập hợp gồm n phần tử. Phương pháp sinh ở đây sẽ liệt kê theo thứ tự từ điển. Ta sẽ liệt kê các phần tử theo dạng nhị phân từ 0 tới n với mỗi bit 1 tương đương với phần tử ở vị trí đấy xuất hiện trong tập con."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "def listSubset(X):\n",
    "    n = len(X)\n",
    "    Y = [0 for i in range(n)]\n",
    "    \n",
    "    print(Y)\n",
    "    \n",
    "listSubset([1, 2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}