pile_file.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b719be1f",
   "metadata": {},
   "source": [
    "# Pile et File - Cours"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e390e046",
   "metadata": {},
   "source": [
    "## Ex 1 : classe Pile (par tableau redimensionnable)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "dc75c68c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Pile_TR:\n",
    "    \"\"\"structure de pile par tableau redimensionnable\"\"\"\n",
    "    def __init__(self):\n",
    "        self.contenu = []\n",
    "        \n",
    "    def est_vide(self):\n",
    "        return len(self.contenu) == 0\n",
    "    \n",
    "    def empiler(self, v):\n",
    "        self.contenu.append(v)\n",
    "        \n",
    "    def depiler(self):\n",
    "        if self.est_vide():\n",
    "            raise IndexError(\"dépiler 1 pile vide\")\n",
    "        return self.contenu.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "cecb9142",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Pile_TR()\n",
    "A.est_vide()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5c6cf4ad",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.empiler(10)\n",
    "A.empiler(12)\n",
    "A.empiler(8)\n",
    "A.est_vide()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "52a8f222",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 12, 8]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(A.contenu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9042bf61",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 12]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.depiler()\n",
    "list(A.contenu)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58459903",
   "metadata": {},
   "source": [
    "## Ex 2 : classe Pile (par classe Cellule)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "4a34f455",
   "metadata": {},
   "outputs": [],
   "source": [
    "# programme 25 (en lien avec l'exercice n° 61 et 62)\n",
    "class Cellule:\n",
    "    \"\"\"une cellule d'une liste chaînée\"\"\"\n",
    "    def __init__(self, v, s):\n",
    "        self.valeur = v\n",
    "        self.suivant = s\n",
    "\n",
    "class Pile_C:\n",
    "    \"\"\"structure de pile\"\"\"\n",
    "    def __init__(self):\n",
    "        self.contenu = None\n",
    "\n",
    "    def est_vide(self):\n",
    "        return self.contenu is None\n",
    "\n",
    "    def empiler(self, v):\n",
    "        self.contenu = Cellule(v, self.contenu)\n",
    "\n",
    "    def depiler(self):\n",
    "        if self.est_vide():\n",
    "            raise IndexError(\"depiler sur une pile vide\")\n",
    "        v = self.contenu.valeur\n",
    "        self.contenu = self.contenu.suivant\n",
    "        return v\n",
    "\n",
    "def creer_pile():\n",
    "    return Pile_C()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "b9a33493",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "B = Pile_C()\n",
    "B.empiler(10)\n",
    "B.empiler(12)\n",
    "B.empiler(8)\n",
    "B.contenu.valeur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "69bd915d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "B.depiler()\n",
    "B.contenu.valeur"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f11dc828",
   "metadata": {},
   "source": [
    "## Ex 3 : classe File (par tableau redimensionnable)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7b008bf1",
   "metadata": {},
   "outputs": [],
   "source": [
    "class File_TR:\n",
    "    \"\"\"structure de pile par tableau redimensionnable\"\"\"\n",
    "    def __init__(self):\n",
    "        self.contenu = []\n",
    "        \n",
    "    def est_vide(self):\n",
    "        return len(self.contenu) == 0\n",
    "    \n",
    "    def empiler(self, v):\n",
    "        self.contenu.append(v)\n",
    "        \n",
    "    def depiler(self):\n",
    "        if self.est_vide():\n",
    "            raise IndexError(\"dépiler 1 pile vide\")\n",
    "        return self.contenu.pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "84978e91",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = File_TR()\n",
    "A.est_vide()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a2221871",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.empiler(10)\n",
    "A.empiler(12)\n",
    "A.empiler(8)\n",
    "A.est_vide()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "efb63245",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 12, 8]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(A.contenu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "3219c039",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[12, 8]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.depiler()\n",
    "list(A.contenu)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25ac9572",
   "metadata": {},
   "source": [
    "## Ex 4 : classe File (avec 1 chaîne mutable)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "8421b696",
   "metadata": {},
   "outputs": [],
   "source": [
    "class File_CM:\n",
    "    \"\"\"structure de file\"\"\"\n",
    "    def __init__(self):\n",
    "        self.tete = None\n",
    "        self.queue = None\n",
    "\n",
    "    def est_vide(self):\n",
    "        return self.tete is None\n",
    "\n",
    "    def ajouter(self, x):\n",
    "        c = Cellule(x, None)\n",
    "        if self.est_vide():\n",
    "            self.tete = c\n",
    "        else:\n",
    "            self.queue.suivant = c\n",
    "        self.queue = c\n",
    "\n",
    "    def retirer(self):\n",
    "        if self.est_vide():\n",
    "            raise IndexError(\"retirer sur une file vide\")\n",
    "        v = self.tete.valeur\n",
    "        self.tete = self.tete.suivant\n",
    "        if self.tete is None:\n",
    "            self.queue = None\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "99c37722",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C.tete = 10\n",
      "C.queue = 8\n"
     ]
    }
   ],
   "source": [
    "C = File_CM()\n",
    "C.ajouter(10)\n",
    "C.ajouter(12)\n",
    "C.ajouter(8)\n",
    "print(f\"C.tete = {C.tete.valeur}\")\n",
    "print(f\"C.queue = {C.queue.valeur}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "8ed97b9d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C.tete = 12\n",
      "C.queue = 8\n"
     ]
    }
   ],
   "source": [
    "C.retirer()\n",
    "print(f\"C.tete = {C.tete.valeur}\")\n",
    "print(f\"C.queue = {C.queue.valeur}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a4ef1be",
   "metadata": {},
   "source": [
    "## Ex 5 : classe File (avec 2 piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "46e2b42d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class File_2P:\n",
    "    \"\"\"structure de file\"\"\"\n",
    "    def __init__(self):\n",
    "        self.entree = creer_pile()\n",
    "        self.sortie = creer_pile()\n",
    "\n",
    "    def est_vide(self):\n",
    "        return self.entree.est_vide() and self.sortie.est_vide()\n",
    "\n",
    "    def ajouter(self, x):\n",
    "        self.entree.empiler(x)\n",
    "\n",
    "    def retirer(self):\n",
    "        if self.sortie.est_vide():\n",
    "            while not self.entree.est_vide():\n",
    "                self.sortie.empiler(self.entree.depiler())\n",
    "        if self.sortie.est_vide():\n",
    "            raise IndexError(\"retirer sur une file vide\")\n",
    "        return self.sortie.depiler()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "5bf86f1d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = File_2P()\n",
    "D.ajouter(10)\n",
    "D.ajouter(12)\n",
    "D.ajouter(8)\n",
    "D.retirer()\n",
    "D.sortie.contenu.valeur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "da00c35c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D.ajouter(15)\n",
    "D.ajouter(20)\n",
    "D.ajouter(6)\n",
    "D.retirer()\n",
    "D.sortie.contenu.valeur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "ba68ac51",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D.retirer()\n",
    "D.retirer()\n",
    "D.sortie.contenu.valeur"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0eb59c86",
   "metadata": {},
   "source": [
    "— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1796796",
   "metadata": {},
   "source": [
    "# Pile et File - Exercices"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf84843a",
   "metadata": {},
   "source": [
    "## Ex 61 : consulter, vider, taille d'une Pile"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "97d8ba5e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# programme 25 (en lien avec l'exercice n° 61 et 62)\n",
    "import copy\n",
    "\n",
    "class Cellule:\n",
    "    \"\"\"une cellule d'une liste chaînée\"\"\"\n",
    "    def __init__(self, v, s):\n",
    "        self.valeur = v\n",
    "        self.suivant = s\n",
    "\n",
    "class Pile:\n",
    "    \"\"\"structure de pile\"\"\"\n",
    "    def __init__(self):\n",
    "        self.contenu = None\n",
    "\n",
    "    def est_vide(self):\n",
    "        return self.contenu is None\n",
    "\n",
    "    def empiler(self, v):\n",
    "        self.contenu = Cellule(v, self.contenu)\n",
    "\n",
    "    def depiler(self):\n",
    "        if self.est_vide():\n",
    "            raise IndexError(\"depiler sur une pile vide\")\n",
    "        v = self.contenu.valeur\n",
    "        self.contenu = self.contenu.suivant\n",
    "        return v\n",
    "\n",
    "    def consulter(self):\n",
    "        if self.est_vide():\n",
    "            raise IndexError(\"consulter sur une pile vide\")\n",
    "        return self.contenu.valeur\n",
    "\n",
    "    def vider(self):\n",
    "        self.contenu = None\n",
    "    \n",
    "    def taille(self):\n",
    "        # calcul en O(n) où n est longueur de la pile (on parcours la pile pour connaître sa longueur)\n",
    "        A = copy.copy(self)\n",
    "        # noter qu'il faut faire une copie de la pile avant de travailler dessus\n",
    "        # problème résolu dans l'ex 62\n",
    "        if A.contenu == None:\n",
    "            return 0\n",
    "        else:\n",
    "            A.depiler()\n",
    "            return 1 + A.taille()\n",
    "        \n",
    "def creer_pile():\n",
    "    return Pile()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "2bb375f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = Pile()\n",
    "A.empiler(10)\n",
    "A.empiler(12)\n",
    "A.empiler(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "d807516d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "print(A.contenu.valeur)\n",
    "print(A.consulter())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "79a1b38f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    },
    {
     "ename": "IndexError",
     "evalue": "consulter sur une pile vide",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "Input \u001b[1;32mIn [45]\u001b[0m, in \u001b[0;36m<cell line: 3>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m A\u001b[38;5;241m.\u001b[39mvider()\n\u001b[0;32m      2\u001b[0m \u001b[38;5;28mprint\u001b[39m(A\u001b[38;5;241m.\u001b[39mcontenu)\n\u001b[1;32m----> 3\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[43mA\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mconsulter\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m)\n",
      "Input \u001b[1;32mIn [26]\u001b[0m, in \u001b[0;36mPile.consulter\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m     26\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mconsulter\u001b[39m(\u001b[38;5;28mself\u001b[39m):\n\u001b[0;32m     27\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mest_vide():\n\u001b[1;32m---> 28\u001b[0m         \u001b[38;5;28;01mraise\u001b[39;00m \u001b[38;5;167;01mIndexError\u001b[39;00m(\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mconsulter sur une pile vide\u001b[39m\u001b[38;5;124m\"\u001b[39m)\n\u001b[0;32m     29\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mcontenu\u001b[38;5;241m.\u001b[39mvaleur\n",
      "\u001b[1;31mIndexError\u001b[0m: consulter sur une pile vide"
     ]
    }
   ],
   "source": [
    "A.vider()\n",
    "print(A.contenu)\n",
    "print(A.consulter())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "bf19a362",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Pile()\n",
    "A.empiler(10)\n",
    "A.empiler(12)\n",
    "A.empiler(8)\n",
    "A.taille()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "69f6d8f6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.consulter()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d2001a8",
   "metadata": {},
   "source": [
    "— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0a053bd",
   "metadata": {},
   "source": [
    "## Ex 62 : idem ex 61 avec un attribut taille"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ac15d44c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# programme 25 (en lien avec l'exercice n° 61 et 62)\n",
    "\n",
    "class Cellule:\n",
    "    \"\"\"une cellule d'une liste chaînée\"\"\"\n",
    "    def __init__(self, v, s):\n",
    "        self.valeur = v\n",
    "        self.suivant = s\n",
    "\n",
    "class Pile:\n",
    "    \"\"\"structure de pile\"\"\"\n",
    "    def __init__(self):\n",
    "        self.contenu = None\n",
    "        self._taille = 0\n",
    "\n",
    "    def est_vide(self):\n",
    "        return self.contenu is None\n",
    "\n",
    "    def empiler(self, v):\n",
    "        self.contenu = Cellule(v, self.contenu)\n",
    "        self._taille += 1\n",
    "\n",
    "    def depiler(self):\n",
    "        if self.est_vide():\n",
    "            raise IndexError(\"depiler sur une pile vide\")\n",
    "        v = self.contenu.valeur\n",
    "        self.contenu = self.contenu.suivant\n",
    "        self._taille -= 1\n",
    "        return v\n",
    "\n",
    "    def consulter(self):\n",
    "        if self.est_vide():\n",
    "            raise IndexError(\"consulter sur une pile vide\")\n",
    "        return self.contenu.valeur\n",
    "\n",
    "    def vider(self):\n",
    "        self.contenu = None\n",
    "    \n",
    "    def taille(self):\n",
    "        return self._taille\n",
    "        \n",
    "def creer_pile():\n",
    "    return Pile()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "45cff785",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = Pile()\n",
    "A.empiler(10)\n",
    "A.empiler(12)\n",
    "A.empiler(8)\n",
    "A.taille()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5d1dc40",
   "metadata": {},
   "source": [
    "— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0543412",
   "metadata": {},
   "source": [
    "## Ex 63 : calculatrice polonaise inverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "08733594",
   "metadata": {},
   "outputs": [],
   "source": [
    "def eval_polonaise_inverse(s):\n",
    "    pile = Pile()\n",
    "    for e in s.split(\" \"):\n",
    "        if e == \"+\" or e == \"*\":\n",
    "            x = pile.depiler()\n",
    "            y = pile.depiler()\n",
    "            z = x+y if e == \"+\" else x*y\n",
    "            pile.empiler(z)\n",
    "        else:\n",
    "            pile.empiler(int(e))\n",
    "    res = pile.depiler()\n",
    "    assert pile.est_vide()\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "a6fb2bdf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "texte = \"1 2 3 * + 4 *\"\n",
    "# ( 1 + 2 * 3 ) * 4 = 28\n",
    "eval_polonaise_inverse(texte)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d1aeea1",
   "metadata": {},
   "source": [
    "— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b7b4b18",
   "metadata": {},
   "source": [
    "## Ex 64 : parenthèse associée"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "4749c665",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ouvrante_associee(s, f):\n",
    "    pile = Pile()\n",
    "# attention erreur dans le corrigé du livre\n",
    "    for i in range(f-1):\n",
    "# attention erreur dans le corrigé du livre\n",
    "        if s[i] == \"(\":\n",
    "            pile.empiler(i)\n",
    "        elif s[i] == \")\":\n",
    "            pile.depiler()\n",
    "    return pile.depiler()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "7ffc6e82",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "31\n",
      ")\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "texte = \"( ( ( 1 + 2 * 3 ) * 4 )= (28) )\"\n",
    "print(len(texte))\n",
    "print(texte[30])\n",
    "ouvrante_associee(texte, 30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "402ba3a1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "31\n",
      ")\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "texte = \"( ( ( 1 + 2 * 3 ) * 4 )= (28) )\"\n",
    "print(len(texte))\n",
    "print(texte[28])\n",
    "ouvrante_associee(texte, 28)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aadf6a5e",
   "metadata": {},
   "source": [
    "— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1660228",
   "metadata": {},
   "source": [
    "## Ex 65 : chaîne bien parenthésée"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "3e2e559f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bonne_parenthese(s):\n",
    "    assoc = { \")\":\"(\" , \"]\":\"[\" }\n",
    "    pile = Pile()\n",
    "    for c in s:\n",
    "        if c == \"(\" or c == \"[\":\n",
    "            pile.empiler(c)\n",
    "        elif c == \")\" or c == \"]\":\n",
    "            if pile.est_vide() or pile.depiler() != assoc[c]:\n",
    "                return False\n",
    "    return pile.est_vide()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "e70b0c82",
   "metadata": {},
   "outputs": [],
   "source": [
    "texte = \"( [ ( 1 + 2 * 3 ) * 4 ] = (28) )\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "e7d04b9a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bonne_parenthese(texte)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "b055cf2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "texte = \"( [ ( 1 + 2 * 3 * 4 ] = (28) )\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "b3afc3dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bonne_parenthese(texte)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}