{
"cells": [
{
"cell_type": "markdown",
"id": "8fdc643f",
"metadata": {},
"source": []
},
{
"cell_type": "markdown",
"id": "ed639e9f",
"metadata": {},
"source": [
"# INF TC1 - Algorithmes et structures de données\n",
"\n",
"## Exercices"
]
},
{
"cell_type": "markdown",
"id": "fca7f37a",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"id": "2f1f2dcd-96a9-45ef-90a6-4ad488635679",
"metadata": {},
"source": [
"# Stacks and queues"
]
},
{
"cell_type": "markdown",
"id": "b9bd540c-dd15-49ac-bfbd-f2e758688a85",
"metadata": {
"tags": []
},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"id": "03a0653e-65c2-4e79-9e83-31765cf19098",
"metadata": {},
"source": [
"## Exercise 1: Reverse a string using a Stack\n",
"\n",
"_Use the `Stack` below to reverse a string given as input._"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4932473d-2734-4e81-b777-ca10decfd9e8",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"class Stack:\n",
" def __init__(self):\n",
" self.items = []\n",
"\n",
" def push(self, item):\n",
" self.items.append(item)\n",
"\n",
" def pop(self):\n",
" if not self.is_empty():\n",
" return self.items.pop()\n",
"\n",
" def peek(self):\n",
" if not self.is_empty():\n",
" return self.items[-1]\n",
"\n",
" def is_empty(self):\n",
" return len(self.items) == 0"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8b77ae34-ef7c-4664-94e0-8928156f2224",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "128a37273e0e5da052abe4bf08bb1c27",
"grade": false,
"grade_id": "cell-5b0828e97507162e",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def reverse_string(s):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "63719c8e-f60c-4544-8e41-cb6380ae4bcf",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"reverse_string(\"Hello\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "81e93620-0664-4a9d-ba5f-894937c9769e",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"assert reverse_string(\"Hello\") == \"olleH\" "
]
},
{
"cell_type": "markdown",
"id": "81df9b1e-cfe5-4b69-96a5-c8065259cc7d",
"metadata": {},
"source": [
"## Exercise 2: Check if a word is a palindrom (using a Stack)\n",
"_A palindrome is a sequence of characters that reads the same forward and backward._"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "cf6fbdd5-53c5-45c2-a0c5-a5ed845c4f81",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "048d788477e620bf78240329c0dd8771",
"grade": false,
"grade_id": "is_palindrome",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def is_palindrome(s):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "586bafba-2fbb-4833-b2e3-609db9b28fbf",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"is_palindrome(\"ABA\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d0005a10-9152-4aa5-a94b-fcbff1bd2281",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "4165b33ba9b75546b0edd15216e61e4f",
"grade": true,
"grade_id": "correct_is_palindrome",
"locked": true,
"points": 0,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"assert is_palindrome(\"ABA\")"
]
},
{
"cell_type": "markdown",
"id": "f767bf25-9f4f-4a0d-8cb9-b729bbec5c27",
"metadata": {},
"source": [
"## Exercise 3: Implement a min-heap\n",
"\n",
"Use a `PriorityQueue` to return the smallest element when using `pop` of a stack (or a queue). "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ddcccaf6-d235-4327-826f-7a62a4c23f28",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"from queue import PriorityQueue"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2da2db1e-f55d-43b4-877f-96ef944818e8",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"# how to use the modue\n",
"priority_queue = PriorityQueue()\n",
"priority_queue.put((3, 'apple'))\n",
"priority_queue.put((1, 'banana'))\n",
"priority_queue.put((2, 'cherry'))\n",
"element = priority_queue.get()\n",
"print(element)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "804ea32d-5bf8-42b9-ae52-6318b26f4065",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "7f6b90fc037aa2a24fa9ce3b4dfca6dd",
"grade": false,
"grade_id": "cell-4b9a5ecdee87514e",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1b2d28c4-277b-44fa-b7e8-590aa00f8f70",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"min_heap = MinHeap()\n",
"min_heap.insert(5)\n",
"min_heap.insert(3)\n",
"min_heap.insert(8)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ed61bced-f000-41c6-8ecd-d669b4edb700",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"assert min_heap.pop() == 3\n",
"assert min_heap.peek() == 5\n",
"assert min_heap.peek() == 5"
]
},
{
"cell_type": "markdown",
"id": "a445d290-b04f-49b5-a8e7-2c6e259daf58",
"metadata": {
"tags": []
},
"source": [
"## Exercise 4: Evaluate a postfix expression\n",
"\n",
"_Write a code that given the following expression, provides the following evaluation (using arthmetic operations over numerical values)._\n",
"\n",
"Expression: `\"3 4 +\"`\n",
"Evaluation: `3 + 4 = 7`\n",
"\n",
"First step: write a function `apply_operator` that applies an operation (ie + - * /) over two elements."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4cc7f805-0887-4422-b6b7-3d591d0df1fb",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "eb88296bc1de3c5dd7c68059e0a071e8",
"grade": false,
"grade_id": "cell-8c5106f02f243455",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def apply_operator(op, b, a):\n",
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "e68bdf7c-ca08-4553-9874-8bd9038fd4b5",
"metadata": {},
"source": [
"Solution in pseudo-code:\n",
"- Split the input expression in to a list of tokens\n",
"- If not an operator\n",
" - Add the value to the stack\n",
"- If an operator \n",
" - Make sure there is enough parameters `a` and `b`\n",
" - Pop `a` and `b`\n",
" - Apply `apply_operator` on `a` and `b`\n",
" - Store the result in the stack"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e792c90d-1b38-47f5-9879-399debc934b9",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "73960d3c6b85c2efc0ad8e298e2649b7",
"grade": false,
"grade_id": "cell-e9236618b265b34f",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def evaluate_postfix(expression):\n",
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ea6e4840-1b7e-4265-b37d-e8c45ea6b3ed",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"postfix_expression = \"3 4 + 2 *\"\n",
"result = evaluate_postfix(postfix_expression)\n",
"print(\"Result:\", result)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0dc4dff8-089b-46a6-a08d-f53ee2fe72c3",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"assert evaluate_postfix(\"3 4 + 2 *\") == 14\n",
"assert evaluate_postfix(\"4 2 3 5 * + *\") == 68 # (4 * (2 + (3 * 5))\n",
"assert evaluate_postfix(\"8 4 / 6 2 * +\") == 14 # ((8 / 4) + (6 * 2))"
]
}
],
"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.10.9"
}
},
"nbformat": 4,
"nbformat_minor": 5
}