{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Pila (*Stack*) DMA (Datu Mota Abstraktua)\n", "\n", "\"Stack\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Pila (*Stack*) DMA (Datu Mota Abstraktua)\n", "\n", "* LIFO (*Last-In First-Out*) motako elementu sorta lineala eta dinamikoa.\n", " * Gehitzen den azkeneko elementua, ateratzen den lehenengoa.\n", " * Ezin dira azken elementuaren *azpitik* dagoen elementuak atzitu.\n", "* Pilaren **oinarria**: gehitutako lehen elementua\n", "* Pilaren **gailurra**: gehitutako azken elementua\n", "* Erabilpenak: funtzioak, analizatzaileak, espresioen ebaluazioak..." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Oinarrrizko eragiketak:\n", "* Hutsik dagoeneko pila berria **sortu/hasieratu**\n", "* **push**: elementu berri bat gehitu\n", "* **top**: gailurreko elementua kontsultatu\n", "* **pop**: gailurreko elementua atera\n", "* **len**: elementu kopurua\n", "* **isEmpty**: hutsik dagoen kontsultatu\n", " * [bool()](https://docs.python.org/3/library/stdtypes.html#truth) ere erabil dezakegu → **len**" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "%%html\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "\"Stack\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Erabilpen adibide bat: elementu segida bat aztekoz aurrera jarri\n", "\n", "```python\n", "def myReversed(it):\n", " s = Stack()\n", " for x in it :\n", " s.push(x)\n", " z = []\n", " #while not s.isEmpty() :\n", " while s :\n", " z.append(s.pop())\n", " return z\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Gainera...\n", "\n", "* Funtzio eraikitzaileari iteragarri bat emateko aukera bagenu: `Stack(it)` \n", " * → iteragarriko elementu guztiak pilari gehitu\n", "* `Stack` objektuak iteragarriak balira\n", " * → zeharkatu ahala, elementu guztiak atera" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "```python\n", "def myReversed(it):\n", " return Stack(it)\n", "```\n", "\n", "→ **Interesgarria litzateke bi propietate hauek inplementatzea**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Stack klasea inplementatzen" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "* Pila bat inplementatzeko egitura egokia: **zerrenda** (**list**)\n", " * Oinarria → list[0]\n", " * Gailurra → list[-1] " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* `Stack.push` → `list.append`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* `Stack.pop` → `list.pop`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* `len(Stack)` → `len(list)`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* `iter(Stack)` $\\not \\Rightarrow$ `iter(list)`" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "class Stack(object):\n", "\n", " def __init__(self,it):\n", " pass\n", " \n", " def push(self,value):\n", " pass\n", "\n", " def top(self):\n", " pass\n", " \n", " def pop(self):\n", " pass\n", " \n", " def __len__(self):\n", " pass\n", " \n", " def __iter__(self):\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "class Stack(object):\n", "\n", " def __init__(self,it=()):\n", " #self.z = []\n", " # for x in it :\n", " # self.push(x) (edo self.z.append(x))\n", " self.z = list(it)\n", " \n", " def push(self,value):\n", " pass\n", " \n", " def top(self):\n", " pass\n", " \n", " def pop(self):\n", " pass\n", " \n", " def __len__(self):\n", " pass\n", " \n", " def __iter__(self):\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "class Stack(object):\n", "\n", " def __init__(self,it=()):\n", " self.z = list(it)\n", " \n", " def push(self,value):\n", " self.z.append(value)\n", " \n", " def top(self):\n", " pass\n", " \n", " def pop(self):\n", " pass\n", " \n", " def __len__(self):\n", " pass\n", " \n", " def __iter__(self):\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "class Stack(object):\n", "\n", " def __init__(self,it=()):\n", " self.z = list(it)\n", " \n", " def push(self,value):\n", " self.z.append(value)\n", " \n", " def top(self):\n", " return self.z[-1]\n", " \n", " def pop(self):\n", " pass\n", " \n", " def __len__(self):\n", " pass\n", " \n", " def __iter__(self):\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "class Stack(object):\n", "\n", " def __init__(self,it=()):\n", " self.z = list(it)\n", " \n", " def push(self,value):\n", " self.z.append(value)\n", " \n", " def top(self):\n", " return self.z[-1]\n", " \n", " def pop(self):\n", " return self.z.pop()\n", " \n", " def __len__(self):\n", " pass\n", " \n", " def __iter__(self):\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "class Stack(object):\n", "\n", " def __init__(self,it=()):\n", " self.z = list(it)\n", " \n", " def push(self,value):\n", " self.z.append(value)\n", " \n", " def top(self):\n", " return self.z[-1]\n", " \n", " def pop(self):\n", " return self.z.pop()\n", " \n", " def __len__(self):\n", " return len(self.z)\n", " \n", " def __iter__(self):\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "class Stack(object):\n", "\n", " def __init__(self,it=()):\n", " self.z = list(it)\n", " \n", " def push(self,value):\n", " self.z.append(value)\n", " \n", " def top(self):\n", " return self.z[-1]\n", " \n", " def pop(self):\n", " return self.z.pop()\n", " \n", " def __len__(self):\n", " return len(self.z)\n", " \n", " def __iter__(self):\n", " # hustu egin behar dugu!!!\n", " #return iter(self.z[::-1])\n", " # kontuz honekin..\n", " #return iter(list(self))\n", " x = list()\n", " while self.z :\n", " x.append(self.z.pop())\n", " #while self :\n", " # x.append(self.pop()) \n", " return iter(x)\n", " \n", " def __iter__(self):\n", " return (self.pop() for _ in range(len(self)))\n", " \n", " def __iter__(self):\n", " while self :\n", " yield self.pop()\n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "s = Stack(range(10))\n", "print(len(s))\n", "#print(list(s))\n", "print(*s)\n", "print(len(s))\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "s = Stack()\n", "for i in \"aeiou\":\n", " s.push(i)\n", " print(f'top: {s.top()} len: {len(s)}')\n", "print('-----')\n", "while s :\n", " x = s.pop()\n", " print(f'pop: {x} len: {len(s)}')" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "s = Stack()\n", "for i in \"aeiou\":\n", " s.push(i)\n", " print(f'top: {s.top()} len: {len(s)}')\n", "print('-----')\n", "for x in s:\n", " print(f'pop: {x} len: {len(s)}')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Eta `str` ?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "* `print(Stack(\"aeiou\"))` :" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "```\n", "---\n", "'u'\n", "'o'\n", "'i'\n", "'e'\n", "'a'\n", "---\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "class Stack(object):\n", "\n", " def __init__(self,it=()):\n", " self.z = list(it)\n", " \n", " def push(self,value):\n", " self.z.append(value)\n", " \n", " def top(self):\n", " return self.z[-1]\n", " \n", " def pop(self):\n", " return self.z.pop()\n", " \n", " def __len__(self):\n", " return len(self.z)\n", " \n", " def __iter__(self):\n", " return (self.pop() for _ in range(len(self)))\n", " \n", " def __str__(self):\n", " return '\\n'.join(['---'] + [repr(x) for x in self.z[::-1]] + ['---'])\n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "s = Stack(\"aeiou\")\n", "print(s)\n", "print(len(s))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "print(Stack([1,2,3,'kaixo',1.3]))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Eta `repr` ?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "* `s == eval(repr(s))` bete dadin saiatu\n", " * `Stack([., ., ., ...])` erabili\n", " * `==` → `__eq__()`" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "class Stack(object):\n", "\n", " def __init__(self,it=()):\n", " self.z = list(it)\n", " \n", " def push(self,value):\n", " self.z.append(value)\n", " \n", " def top(self):\n", " return self.z[-1]\n", " \n", " def pop(self):\n", " return self.z.pop()\n", " \n", " def __len__(self):\n", " return len(self.z)\n", " \n", " def __iter__(self):\n", " return (self.pop() for _ in range(len(self)))\n", " \n", " def __str__(self):\n", " return '\\n'.join(['---'] + [repr(x) for x in self.z[::-1]] + ['---'])\n", " \n", " def __repr__(self):\n", " return f'Stack({repr(self.z)})'\n", " \n", " def __eq__(self,other):\n", " return type(other) == Stack and self.z == other.z\n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "s = Stack([1,2,3,'kaixo',1.3,(5,6),[64,24,(23,234,265)]])\n", "print(s)\n", "print(repr(s))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "s == eval(repr(s)) , s == Stack() , s == Stack(range(10)) , s == \"kaixo\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## InFixu - PostFixu adierazpenak " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* **InFixu**: $\\;\\;a \\; + \\; b \\; * \\; c \\; = \\; a + (b * c)$\n", " * Eragilea eragigaien **artean**\n", " * Espresioak ezkerretik eskuinera ebaluatzen dira, baina...\n", " * Eragileen lehentasuna: `* , /` → `+ , -`\n", " * Parentesiek lehentasuna alda dezakete:\n", " * $a + b * c \\; \\not = \\; (a + b) * c$\n", " * Notazio matematikoan erabilia" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "* **PostFixu**: $\\;\\;a \\; b \\; c \\; * \\; + \\; \\equiv \\; a + b * c\\;\\;$ edo $\\;\\;b \\; c \\; * \\; a \\; + \\; \\equiv \\; b * c + a$\n", " * Eragilea bi eragigaien **atzetik**\n", " * Espresioak ezkerretik eskuinera exekutatzen dira\n", " * Ez dago eragile lehentasunik\n", " * → Automatikoki prozesatzeko adierazpen aproposa\n", " * Kalkulagailu zientifiko batzuetan erabilia" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "| InFix | PostFix |\n", "|:-----------------:|:-------------:|\n", "| A + B | A B + |\n", "| A + B * C | A B C * + |\n", "| (A + B) * C | A B + C * |\n", "| A + B * C + D | A B C * + D + |\n", "|  (A + B) * (C + D)  |  A B + C D + *  |\n", "| A * B + C * D | A B * C D * + |\n", "| A + B + C + D | A B + C + D + |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Postfixu adierazpenen ebaluazioa\n", "\n", "* Oso erraza **Pila** baten bidez\n", "* Algoritmoaren sarrera: elementu sekuentzia\n", " * Eragigaiak\n", " * Eragileak\n", "* Algoritmoaren irteera: emaitza" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### PostFixu Ebaluazio Algoritmoa:\n", "\n", "* Elementu sekuentzia zeharkatu\n", " * eragigaia → pilara\n", " * eragilea\n", " * pilatik bi eragigai atera\n", " * eragiketaren emaitza → pilara\n", "* Pilako elementu bakarra **emaitza** da." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Adibidea**: $\\;\\;3 \\;\\; 4 \\; + \\; 10 \\;\\; * \\;\\; \\equiv \\;\\; (3+4) * 10$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "\"Stack\"" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# sarrerako sekuentzia: 3 4 + 10 *\n", "s = Stack()\n", "# 3 --> pilara\n", "s.push(3)\n", "# 4 --> pilara\n", "s.push(4)\n", "# + --> bi eragileak atera eta emaitza pilara\n", "b = s.pop()\n", "a = s.pop()\n", "s.push(a+b)\n", "# 10 --> pilara\n", "s.push(10)\n", "# * --> bi eragileak atera eta emaitza pilara\n", "b = s.pop()\n", "a = s.pop()\n", "s.push(a*b)\n", "# EMAITZA: pilako gailurra (elementu bakarra dago)\n", "e = s.pop()\n", "\n", "print(e,len(s))" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# sarrera: hutsunez banandutako karaktere katea\n", "def eval_postfix(txt):\n", " s = Stack()\n", " for x in txt.split():\n", " if x in '+-*/' :\n", " b = s.pop()\n", " a = s.pop()\n", " if x == '+' :\n", " s.push(a+b)\n", " elif x == '-' :\n", " s.push(a-b)\n", " elif x == '*' :\n", " s.push(a*b)\n", " else :\n", " s.push(a/b)\n", " else :\n", " s.push(eval(x))\n", " return s.pop()" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "70 70\n", "44.0 44.0\n", "44.0 44.0\n", "44.0 44.0\n" ] } ], "source": [ "print(((3+4)*10), eval_postfix('3 4 + 10 *'))\n", "print(((7+3)*8/2+4), eval_postfix('7 3 + 8 * 2 / 4 +'))\n", "print((8*(7+3)/2+4), eval_postfix('8 7 3 + * 2 / 4 +'))\n", "print((4+8*(7+3)/2), eval_postfix('4 8 7 3 + * 2 / +'))\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Parentesirik gabeko InFixuak → PostFixu\n", "\n", "* Oso erraza **Pila** baten bidez\n", "* Algoritmoaren sarrera: elementu sekuentzia (eragileak + eragigaiak)\n", "* Algoritmoaren irteera: elementu sekuentzia (eragileak + eragigaiak)\n", " * Espresio InFixuan eragigaien ordena berdina izango da" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### InFixuak → PostFixu (parentesirik gabe) Algoritmoa:\n", "\n", "* Elementu sekuentzia zeharkatu\n", " * eragigaia → irteera sekuentzira\n", " * eragilea\n", " * gailurreko lehentasun berdineko edo handiagoko eragileak → irteera sekuentzira\n", " * → eragilea pilara\n", "* Pilako elementu guztiak → irteera sekuentzira" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Adibidez:** `1 * 2 + 3 * 4` → `1 2 * 3 4 * +`" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# Sarrerako sekuentzia: 1 * 2 + 3 * 4\n", "s = Stack()\n", "z = []\n", "# 1 --> irteerara\n", "z.append(1)\n", "# * --> pilako lehentasun handiko eragileak irteerara eta eragile hau pilara\n", "print(len(s) == 0)\n", "s.push('*')\n", "# 2 --> irteerara\n", "z.append(2)\n", "# + --> pilako lehentasun handiko eragileak irteerara eta eragile hau pilara\n", "print(s.top() == '*')\n", "z.append(s.pop())\n", "print(len(s) == 0)\n", "s.push('+')\n", "# 3 --> irteerara\n", "z.append(3)\n", "# * --> pilako lehentasun handiko eragileak irteerara eta eragile hau pilara\n", "print(s.top() == '+')\n", "s.push('*')\n", "# 4 --> irteerara\n", "z.append(4)\n", "# pila hustu\n", "z.extend(s)\n", "\n", "print(z,len(s))" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# sarrera: hutsunez banandutako karaktere katea\n", "# irteera: hutsunez banandutako karaktere katea\n", "def infix2postfix(txt):\n", " s = Stack()\n", " z = []\n", " priority = {'*':2 , '/':2 , '+':1 , '-':1}\n", " for x in txt.split():\n", " if x in '+-*/' :\n", " px = priority[x]\n", " while s and priority[s.top()] >= px :\n", " z.append(s.pop())\n", " s.push(x)\n", " else :\n", " z.append(x)\n", " z.extend(s)\n", " return ' '.join(z)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "scrolled": true, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A + B --> A B +\n", "A + B * C --> A B C * +\n", "A + B * C + D --> A B C * + D +\n", "A * B + C * D --> A B * C D * +\n", "A + B + C + D --> A B + C + D +\n", "A / B * C / D --> A B / C * D /\n", "A / B * C + D * E - F / G --> A B / C * D E * + F G / -\n" ] } ], "source": [ "frogak='''\n", "A + B\n", "A + B * C\n", "A + B * C + D\n", "A * B + C * D\n", "A + B + C + D\n", "A / B * C / D\n", "A / B * C + D * E - F / G\n", "'''\n", "for x in frogak.strip().split('\\n') :\n", " print(f'{x} --> {infix2postfix(x)}')" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "17052.1\n", "34.1 254 67 * +\n", "17052.1\n" ] } ], "source": [ "x = \"34.1 + 254 * 67\"\n", "print(eval(x))\n", "print(infix2postfix(x))\n", "print(eval_postfix(infix2postfix(x)))" ] } ], "metadata": { "celltoolbar": "Slideshow", "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.6" }, "rise": { "autolaunch": false, "footer": "

Konputaziorako Sarrera

", "scroll": true } }, "nbformat": 4, "nbformat_minor": 2 }