Assignment 1 Data Base.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0d29a9ae",
   "metadata": {},
   "source": [
    "#### Q1. Write a program to find all pairs of an integer array whose sum is equal to a given number?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "40d2e5f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Pairs(arr, n, sum):\n",
    "    count = 0  \n",
    "    for i in range(0, n):\n",
    "        for j in range(i + 1, n):\n",
    "            if arr[i] + arr[j] == sum:\n",
    "                count += 1\n",
    " \n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5df6d9ec",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Count of pairs is 4\n"
     ]
    }
   ],
   "source": [
    "arr = [1, 5, 7, 1, 5]\n",
    "n = len(arr)\n",
    "sum = 6\n",
    "print(\"Count of pairs is\",Pairs(arr, n, sum))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0189a64",
   "metadata": {},
   "source": [
    "#### Q2. Write a program to reverse an array in place? In place means you cannot create a new array. You have to update the original array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "840dadcf",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_List(A, start, end):\n",
    "    if start >= end:\n",
    "        return\n",
    "    A[start], A[end] = A[end], A[start]\n",
    "    reverse_List(A, start+1, end-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4def2ed2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 4, 3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "A = [1, 2, 3, 4, 5]\n",
    "reverse_List(A, 0, 4)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4004ce33",
   "metadata": {},
   "source": [
    "#### Q3. Write a program to check if two strings are a rotation of each other?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "a803e452",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Rotations(string1, string2):\n",
    "    size1 = len(string1)\n",
    "    size2 = len(string2)\n",
    "    temp = ''\n",
    " \n",
    "    if size1 != size2:\n",
    "        return 0\n",
    " \n",
    "    temp = string1 + string1\n",
    " \n",
    "    if (temp.count(string2)> 0):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "9e15a4c1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Strings are rotations of each other\n"
     ]
    }
   ],
   "source": [
    "string1 = \"AACD\"\n",
    "string2 = \"ACDA\"\n",
    " \n",
    "if Rotations(string1, string2):\n",
    "    print(\"Strings are rotations of each other\")\n",
    "else:\n",
    "    print(\"Strings are not rotations of each other\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1902caff",
   "metadata": {},
   "source": [
    "#### Q4. Write a program to print the first non-repeated character from a string?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "2fa9cf44",
   "metadata": {},
   "outputs": [],
   "source": [
    "NO_OF_CHARS = 256\n",
    "\n",
    "def CharCount(string):\n",
    "    count = [0] * NO_OF_CHARS\n",
    "    for i in string:\n",
    "        count[ord(i)]+= 1\n",
    "    return count\n",
    "def firstNonRepeating(string):\n",
    "    count = CharCount(string)\n",
    "    index = -1\n",
    "    k = 0\n",
    "\n",
    "    for i in string:\n",
    "        if count[ord(i)] == 1:\n",
    "            index = k\n",
    "            break\n",
    "        k += 1\n",
    "\n",
    "    return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "b042afa2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First non-repeating character is e\n"
     ]
    }
   ],
   "source": [
    "string = \"edyoda\"\n",
    "index = firstNonRepeating(string)\n",
    "if index == 1:\n",
    "    print(\"Either all characters are repeating or string is empty\")\n",
    "else:\n",
    "    print(\"First non-repeating character is \" + string[index])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b9d3506",
   "metadata": {},
   "source": [
    "#### Q5. Read about the Tower of Hanoi algorithm. Write a program to implement it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "e679373c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Hanoi(n,source,temp,destination):\n",
    "    if n==1:\n",
    "        print(\"Move disk %s from %s ----->>>%s\"%(n,source,destination))\n",
    "    else:\n",
    "        Hanoi(n-1,source,destination,temp)\n",
    "        print(\"Move disk %s from %s ----->>>%s\"%(n,source,destination))\n",
    "        Hanoi(n-1, temp,source,destination)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "22ef5a41",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Move disk 1 from A ----->>>B\n",
      "Move disk 2 from A ----->>>C\n",
      "Move disk 1 from B ----->>>C\n",
      "Move disk 3 from A ----->>>B\n",
      "Move disk 1 from C ----->>>A\n",
      "Move disk 2 from C ----->>>B\n",
      "Move disk 1 from A ----->>>B\n",
      "Move disk 4 from A ----->>>C\n",
      "Move disk 1 from B ----->>>C\n",
      "Move disk 2 from B ----->>>A\n",
      "Move disk 1 from C ----->>>A\n",
      "Move disk 3 from B ----->>>C\n",
      "Move disk 1 from A ----->>>B\n",
      "Move disk 2 from A ----->>>C\n",
      "Move disk 1 from B ----->>>C\n"
     ]
    }
   ],
   "source": [
    "n = 4\n",
    "Hanoi(n,'A','B','C')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fe93fd6",
   "metadata": {},
   "source": [
    "#### Q6. Read about infix, prefix, and postfix expressions. Write a program to convert postfix to prefix expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "e0a49116",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Prefix :  +AB-CD\n"
     ]
    }
   ],
   "source": [
    "def Operator(x): \n",
    "    if x == \"+\":\n",
    "        return True\n",
    "    if x == \"-\":\n",
    "        return True\n",
    "    if x == \"/\":\n",
    "        return True\n",
    "    if x == \"*\":\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def postToPre(exp): \n",
    "    s = []\n",
    " \n",
    "    length = len(exp)\n",
    "    for i in range(length): \n",
    "        if (Operator(exp[i])):   \n",
    "            op1 = s[-1]\n",
    "            s.pop()\n",
    "            op2 = s[-1]\n",
    "            s.pop()\n",
    "            temp = exp[i] + op2 + op1\n",
    "            s.append(temp)\n",
    "        else:\n",
    "            s.append(exp[i])\n",
    "    ans = \"\"\n",
    "    for i in s:\n",
    "        ans += i\n",
    "    return ans\n",
    " \n",
    "if __name__ == \"__main__\":\n",
    "    exp = \"AB+CD-\"  \n",
    "    print(\"Prefix : \", postToPre(exp))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "078213b8",
   "metadata": {},
   "source": [
    "#### Q7. Write a program to convert prefix expression to infix expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "3453ae8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prefixToInfix(prefix):\n",
    "    stack = []\n",
    "    i = len(prefix) - 1\n",
    "    while i >= 0:\n",
    "        if not Operator(prefix[i]):\n",
    "             \n",
    "            stack.append(prefix[i])\n",
    "            i -= 1\n",
    "        else:\n",
    "            Str = \"(\" + stack.pop() + prefix[i] + stack.pop() + \")\"\n",
    "            stack.append(Str)\n",
    "            i -= 1\n",
    "     \n",
    "    return stack.pop()\n",
    "def Operator(c):\n",
    "    if c == \"*\" or c == \"+\" or c == \"-\" or c == \"/\" or c == \"^\" or c == \"(\" or c == \")\":\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "983cbb44",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'((A-(B/C))*((A/K)-L))'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Str = \"*-A/BC-/AKL\"\n",
    "prefixToInfix(Str)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aaccac14",
   "metadata": {},
   "source": [
    "#### Q8. Write a program to check if all the brackets are closed in a given code snippet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "ca0e6612",
   "metadata": {},
   "outputs": [],
   "source": [
    "def BracketsBalanced(expr):\n",
    "    stack = []\n",
    " \n",
    "    for char in expr:\n",
    "        if char in [\"(\", \"{\", \"[\"]:\n",
    " \n",
    "            stack.append(char)\n",
    "        else:\n",
    "            if not stack:\n",
    "                return False\n",
    "            current_char = stack.pop()\n",
    "            if current_char == '(':\n",
    "                if char != \")\":\n",
    "                    return False\n",
    "            if current_char == '{':\n",
    "                if char != \"}\":\n",
    "                    return False\n",
    "            if current_char == '[':\n",
    "                if char != \"]\":\n",
    "                    return False    \n",
    "    if stack:\n",
    "        return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "49dc3904",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "({})\n",
      "Balanced\n"
     ]
    }
   ],
   "source": [
    "expr = input()\n",
    " \n",
    "if BracketsBalanced(expr):\n",
    "    print(\"Balanced\")\n",
    "else:\n",
    "    print(\"Not Balanced\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11707956",
   "metadata": {},
   "source": [
    "#### Q9. Write a program to reverse a stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "94d6d064",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertAtBottom(stack, item):\n",
    "    if isEmpty(stack):\n",
    "        push(stack, item)\n",
    "    else:\n",
    "        temp = pop(stack)\n",
    "        insertAtBottom(stack, item)\n",
    "        push(stack, temp)\n",
    "def reverse(stack):\n",
    "    if not isEmpty(stack):\n",
    "        temp = pop(stack)\n",
    "        reverse(stack)\n",
    "        insertAtBottom(stack, temp)\n",
    "def createStack():\n",
    "    stack = []\n",
    "    return stack\n",
    "def isEmpty( stack ):\n",
    "    return len(stack) == 0\n",
    "\n",
    "def push( stack, item ):\n",
    "    stack.append( item )\n",
    "    \n",
    "def pop( stack ):\n",
    " \n",
    " \n",
    "    if(isEmpty( stack )):\n",
    "        print(\"Stack Underflow \")\n",
    "        exit(1)\n",
    " \n",
    "    return stack.pop()\n",
    " \n",
    "\n",
    "def prints(stack):\n",
    "    for i in range(len(stack)-1, -1, -1):\n",
    "        print(stack[i], end = ' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "36871cdd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Stack \n",
      "1 2 3 4 \n",
      "Reversed Stack \n",
      "4 3 2 1 \n"
     ]
    }
   ],
   "source": [
    "stack = createStack()\n",
    "push( stack, str(4) )\n",
    "push( stack, str(3) )\n",
    "push( stack, str(2) )\n",
    "push( stack, str(1) )\n",
    "print(\"Original Stack \")\n",
    "prints(stack)\n",
    " \n",
    "reverse(stack)\n",
    " \n",
    "print(\"Reversed Stack \")\n",
    "prints(stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "048eccae",
   "metadata": {},
   "source": [
    "#### Q10. Write a program to find the smallest number using a stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "e378ec11",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack():\n",
    "\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "        self.min_data = []\n",
    "\n",
    "    def push(self, item):\n",
    "        if self.size() == 0:\n",
    "            self.min_data.append(item)\n",
    "        else:\n",
    "            self.min_data.append(min(self.min_data[self.size() - 1], item))\n",
    "        self.data.append(item)\n",
    "\n",
    "    def pop(self):\n",
    "        self.min_data.pop()\n",
    "        return self.data.pop()\n",
    "\n",
    "    def minimum(self):\n",
    "        return self.min_data[self.size() - 1]\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.size() == 0\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "1b661d32",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stack_obj = Stack()\n",
    "stack_obj.push(3)\n",
    "stack_obj.push(5)\n",
    "stack_obj.push(1)\n",
    "stack_obj.minimum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "84cf5fb3",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.0"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}