Mission564Solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Importing the LinkedList and Stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from linked_list import LinkedList\n",
    "\n",
    "class Stack(LinkedList):\n",
    "    \n",
    "    def push(self, data):\n",
    "        self.append(data)\n",
    "\n",
    "    def peek(self):\n",
    "        return self.tail.data\n",
    "\n",
    "    def pop(self):\n",
    "        ret = self.tail.data\n",
    "        if self.length == 1:\n",
    "            self.tail = self.head = None\n",
    "        else:\n",
    "            self.tail = self.tail.prev\n",
    "            self.tail.next = None\n",
    "        self.length -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementing the tokenize function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['12', '2', '4', '+', '/', '21', '*']\n"
     ]
    }
   ],
   "source": [
    "def tokenize(expression):\n",
    "    return expression.split()\n",
    "\n",
    "print(tokenize(\"12 2 4 + / 21 *\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Functions to process operators in postfix evaluation\n",
    "\n",
    "The functions are all the same, the only thing that changes is the operator used to calculate the `result` variable.\n",
    "\n",
    "It is very important to perform the operation between the elements that was second to to and the top elements. If we do it the other way around we'll get the wrong result.\n",
    "\n",
    "For example, in the `process_minus()` function we do:\n",
    "\n",
    "```python\n",
    "result = second_to_top - top # Correct\n",
    "```\n",
    "\n",
    "and not\n",
    "\n",
    "```python\n",
    "result = top - second_to_top # Wrong\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_minus(stack):\n",
    "    top = stack.pop()\n",
    "    second_to_top = stack.pop()\n",
    "    result = second_to_top - top\n",
    "    stack.push(result)\n",
    "    \n",
    "def process_plus(stack):\n",
    "    top = stack.pop()\n",
    "    second_to_top = stack.pop()\n",
    "    # Same as process_minus but with + instead of -\n",
    "    result = second_to_top + top\n",
    "    stack.push(result)\n",
    "    \n",
    "def process_times(stack):\n",
    "    top = stack.pop()\n",
    "    second_to_top = stack.pop()\n",
    "    # Same as process_minus but with * instead of -\n",
    "    result = second_to_top * top\n",
    "    stack.push(result)\n",
    "\n",
    "def process_divide(stack):\n",
    "    top = stack.pop()\n",
    "    second_to_top = stack.pop()\n",
    "    # Same as process_minus but with / instead of -\n",
    "    result = second_to_top / top\n",
    "    stack.push(result)\n",
    "    \n",
    "def process_pow(stack):\n",
    "    top = stack.pop()\n",
    "    second_to_top = stack.pop()\n",
    "    # Same as process_minus but with ** instead of -\n",
    "    result = second_to_top ** top\n",
    "    stack.push(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Evaluating postfix expressions\n",
    "\n",
    "Here are the steps we need to follow to implement the `evaluate_postfix()` function.\n",
    "\n",
    "1. Initialize an empty stack.\n",
    "2. Tokenize the expression using the `tokenize()` function.\n",
    "3. For each token, do:\n",
    "    1. If the token an operator, call the corresponding function to process it. For example, if we find a `+` we call the `process_plus()` function.\n",
    "    2. Otherwise (the token is a number) and we push that number to the top of the stack. Since each token is a string, we'll need to convert it to a `float` first.\n",
    "4. Return the value that is left in the stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate_postfix(expression):\n",
    "    tokens = tokenize(expression)\n",
    "    stack = Stack()\n",
    "    for token in tokens:\n",
    "        if token == \"+\":\n",
    "            process_plus(stack)\n",
    "        elif token == \"-\":\n",
    "            process_minus(stack)\n",
    "        elif token == \"*\":\n",
    "            process_times(stack)\n",
    "        elif token == \"/\":\n",
    "            process_divide(stack)\n",
    "        elif token == \"**\":\n",
    "            process_pow(stack)\n",
    "        else:\n",
    "            # The token is not an operator so it must be a number\n",
    "            stack.push(float(token))\n",
    "    return stack.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Testing the implementation\n",
    "\n",
    "When testing with other expressions we need to add spaces between at two tokens. For example `1 + 3` will work but `1+3` won't."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-2.0\n",
      "8.0\n",
      "0.0\n",
      "2.0\n",
      "11.25\n",
      "45.0\n",
      "42.0\n",
      "4.0\n",
      "2.0\n"
     ]
    }
   ],
   "source": [
    "expressions = [\n",
    "    \"4 6 -\",\n",
    "    \"4 1 2 9 3 / * + 5 - *\",\n",
    "    \"1 2 + 3 -\",\n",
    "    \"1 2 - 3 +\",\n",
    "    \"10 3 5 * 16 4 - / +\",\n",
    "    \"5 3 4 2 - ** *\",\n",
    "    \"12 2 4 + / 21 *\",\n",
    "    \"1 1 + 2 **\",\n",
    "    \"1 1 2 ** +\"\n",
    "]\n",
    "\n",
    "for expression in expressions:\n",
    "    print(evaluate_postfix(expression))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Precedence dictionary\n",
    "\n",
    "The precedence dictionary is used to compare the precedence of two operators."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "precedence = {\n",
    "    \"+\": 1,\n",
    "    \"-\": 1,\n",
    "    \"*\": 2,\n",
    "    \"/\": 2,\n",
    "    \"**\": 3\n",
    "}\n",
    "\n",
    "print(precedence[\"/\"] < precedence[\"-\"])\n",
    "print(precedence[\"+\"] < precedence[\"*\"])\n",
    "print(precedence[\"+\"] < precedence[\"-\"])\n",
    "print(precedence[\"/\"] < precedence[\"**\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Processing tokens in infix to postfix conversions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Opening parenthesis\n",
    "\n",
    "- Opening parentheses, `(`: \n",
    "    1. Push the token into the stack. It will be used later when we find a closing parenthesis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_opening_parenthesis(stack):\n",
    "    stack.push(\"(\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Closing parenthesis\n",
    "\n",
    "- Closing parentheses `)`:\n",
    "    1. While the top of the stack is not an opening parenthesis, (, pop the top element and append it to the postfix token list.\n",
    "    2. Pop the opening parentheses out of the stack at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_closing_parenthesis(stack, postfix):\n",
    "    # Add tokens until we find the open bracket\n",
    "    while stack.peek() != \"(\":\n",
    "        postfix.append(stack.pop())\n",
    "    # Remove the opening bracket\n",
    "    stack.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Operators\n",
    "\n",
    "- Operator, `+`, `-`, `*`, `/` or `**`: \n",
    "    - While the top of the stack is also an operator whose precedence is greater than or equal to this operator, pop the top element and append it to the `postfix` token list. \n",
    "    - Push the current operator to the top of the stack.\n",
    "\n",
    "The `Stack.peek()` method will cause an error if the stack is empty. Thus, in the while loop we also need to check that the stack is not empty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_operator(stack, postfix, operator):\n",
    "    while len(stack) > 0 and stack.peek() in precedence and precedence[stack.peek()] >= precedence[operator]:\n",
    "        postfix.append(stack.pop())\n",
    "    stack.push(operator)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Numbers\n",
    "\n",
    "- Operand (any number):\n",
    "    1. Push the token into the the postfix token list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_number(postfix, number):\n",
    "    postfix.append(number)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Shunting-yard Algorithm\n",
    "\n",
    "1. We start by splitting the expression into tokens using the `tokenize()` function.\n",
    "2. We initialize an empty stack.\n",
    "3. We initialize and empty postfix token list.\n",
    "4. Iterate over all tokens and for each of them:\n",
    "    - If the token is `\"(\"` we call the `process_opening_parenthesis()` function.\n",
    "    - If the token is `\")\"` we call the `process_closing_parenthesis()` function.\n",
    "    - If the token is an operator we call the `process_operator()` function.\n",
    "    - Otherwise, the token is a number and we call the `process_number()` function.\n",
    "5. After processing all tokens, we use a while loop to pop the remaining stack element into the postfix token list.\n",
    "6. Use the `str.join()` method to convert the postfix token list into a string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def infix_to_postfix(expression):\n",
    "    tokens = tokenize(expression)\n",
    "    stack = Stack()\n",
    "    postfix = []\n",
    "    for token in tokens:\n",
    "        if token == \"(\":\n",
    "            process_opening_parenthesis(stack)\n",
    "        elif token == \")\":\n",
    "            process_closing_parenthesis(stack, postfix)\n",
    "        elif token in precedence:\n",
    "            process_operator(stack, postfix, token)\n",
    "        else:\n",
    "            process_number(postfix, token)\n",
    "    while len(stack) > 0:\n",
    "        postfix.append(stack.pop())\n",
    "    return \" \".join(postfix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Evaluating Infix Expressions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate(expression):\n",
    "    postfix_expression = infix_to_postfix(expression)\n",
    "    return evaluate_postfix(postfix_expression)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.0\n",
      "0.0\n",
      "8.0\n",
      "11.25\n",
      "256.0\n",
      "65536.0\n",
      "0.5\n",
      "9.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "expressions = [\n",
    "    \"1 + 1\",\n",
    "    \"1 * ( 2 - ( 1 + 1 ) )\",\n",
    "    \"4 * ( 1 + 2 * ( 9 / 3 ) - 5 )\",\n",
    "    \"10 + 3 * 5 / ( 16 - 4 * 1 )\",\n",
    "    \"2 * 2 * 2 * 2 * 2 * 2 * 2 * 2\",\n",
    "    \"2 ** 2 ** 2 ** 2 ** 2\",\n",
    "    \"( 1 - 2 ) / ( 3 - 5 )\",\n",
    "    \"9 / 8 * 8\",\n",
    "    \"64 / ( 8 * 8 )\",\n",
    "]\n",
    "\n",
    "for expression in expressions:\n",
    "    print(evaluate(expression))"
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}