{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Stack class" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "class Stack:\n", " def __init__(self):\n", " self.items = []\n", "\n", " def is_empty(self):\n", " return self.items == []\n", "\n", " def push(self, item):\n", " self.items.append(item)\n", "\n", " def pop(self):\n", " return self.items.pop()\n", "\n", " def peek(self):\n", " return self.items[-1]\n", "\n", " def size(self):\n", " return len(self.items)\n", " \n", " # The following will be implemented in the workshop\n", " def __len__():\n", " pass\n", " \n", " def __bool__():\n", " pass\n", " \n", " def __repr__ ():\n", " pass\n", " \n", " def __str__():\n", " pass\n", " \n", " def __contains__():\n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# String reversal using a stack" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "def revstring(mystr):\n", " mystack = Stack()\n", " ret = \"\"\n", " for foo in mystr:\n", " mystack.push(foo)\n", "\n", " while mystack.is_empty() == False:\n", " ret += mystack.pop()\n", " return ret" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "elppa\n", "x\n", "0987654321\n" ] } ], "source": [ "print(revstring('apple'))\n", "print(revstring('x'))\n", "print(revstring('1234567890'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Balanced Parentheses using a stack" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "def par_checker(symbol_string):\n", " s = Stack()\n", " balanced = True\n", " index = 0\n", " \n", " while index < len(symbol_string) and balanced:\n", " symbol = symbol_string[index]\n", " if symbol == \"(\":\n", " s.push(symbol)\n", " else: \n", " # the case for a right/closing parens\n", " if s.is_empty():\n", " balanced = False\n", " else:\n", " s.pop()\n", " \n", " index += 1\n", " \n", " if balanced and s.is_empty():\n", " return True\n", " else:\n", " return False" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "par_checker(\")()\")" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "def par_counter(symbol_string):\n", " opencount = 0\n", " for symbol in symbol_string:\n", " if symbol == \"(\":\n", " opencount += 1\n", " else:\n", " opencount -= 1\n", " \n", " if opencount < 0:\n", " return False\n", "\n", " return opencount == 0\n", " " ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "par_counter(\")\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### But what if we consider \"( , [ , { ,<\" ?" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "def symbol_checker(symbol_string):\n", " s = Stack()\n", " balanced = True\n", " index = 0\n", " \n", " while index < len(symbol_string) and balanced:\n", " symbol = symbol_string[index]\n", " if symbol in '([{<':\n", " s.push(symbol)\n", " else:\n", " if s.is_empty():\n", " balanced = False\n", " else:\n", " top = s.pop()\n", " #print(s.items, top, symbol)\n", " if not matches(top, symbol):\n", " balanced = False\n", " index += 1\n", " \n", " #print(\"Balanced: {} empty: {}\".format(balanced, s.is_empty()))\n", " return (balanced and s.is_empty())" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "def matches(_open, close):\n", " openers = \"([{<\"\n", " closers = \")]}>\"\n", " return openers.index(_open) == closers.index(close)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True\n", "True\n", "False\n" ] } ], "source": [ "print(symbol_checker(\"[]<>(){}\"))\n", "print(symbol_checker('{{([][])}()}'))\n", "print(symbol_checker('[{()]}'))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Infix, Prefix, Postfix Expressions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Without operator precedence" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "import string\n", "\n", "def infix_to_postfix(infix_expr):\n", " operand_stack = Stack()\n", " postfix_list = []\n", " token_list = infix_expr.split()\n", " \n", " for token in token_list:\n", " if token in string.ascii_uppercase:\n", " postfix_list.append(token)\n", " elif token == '(': \n", " operand_stack.push(token)\n", " elif token == ')':\n", " top_token = operand_stack.pop()\n", " while top_token != '(':\n", " postfix_list.append(top_token)\n", " top_token = operand_stack.pop()\n", " else: # Operator\n", " if not operand_stack.is_empty() and operand_stack.peek() != '(':\n", " postfix_list.append(operand_stack.pop())\n", " operand_stack.push(token)\n", " \n", " while not operand_stack.is_empty():\n", " postfix_list.append(operand_stack.pop())\n", " \n", " return \"\".join(postfix_list) " ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "AB*C+D*\n" ] } ], "source": [ "print(infix_to_postfix(\"A * B + C * D\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### With operator precedence" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [], "source": [ "def infix_to_postfix2(infix_expr):\n", " prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}\n", " \n", " operand_stack = Stack()\n", " postfix_list = []\n", " token_list = infix_expr.split() # our infix_expr should have spaces in it!\n", " \n", " for token in token_list:\n", " if token in string.ascii_uppercase or token in string.digits:\n", " postfix_list.append(token)\n", " elif token == '(':\n", " operand_stack.push(token)\n", " elif token == ')':\n", " top_token = operand_stack.pop()\n", " while top_token != '(':\n", " postfix_list.append(top_token)\n", " top_token = operand_stack.pop()\n", " else:\n", " while (not operand_stack.is_empty() and\n", " prec[operand_stack.peek()] >= prec[token]):\n", " postfix_list.append(operand_stack.pop())\n", " \n", " operand_stack.push(token)\n", " \n", " while not operand_stack.is_empty():\n", " postfix_list.append(operand_stack.pop())\n", " \n", " return \" \".join(postfix_list)" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A B * C D * +\n", "A B + C * D E - F G + * -\n" ] } ], "source": [ "print(infix_to_postfix2(\"A * B + C * D\"))\n", "print(infix_to_postfix2(\"( A + B ) * C - ( D - E ) * ( F + G )\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Postfix expression evaluator" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "def postfix_eval(postfix_expr):\n", " operand_stack = Stack() # operAND stack\n", " token_list = postfix_expr.split()\n", " \n", " for token in token_list:\n", " if token in string.digits:\n", " operand_stack.push(int(token))\n", " else:\n", " operand2 = operand_stack.pop()\n", " operand1 = operand_stack.pop()\n", " result = do_math(token, operand1, operand2)\n", " # Can you eliminate `do_math` with a one-liner?\n", " operand_stack.push(result)\n", " \n", " return operand_stack.pop()" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [], "source": [ "def do_math(op, op1, op2):\n", " if op == '*':\n", " return op1 * op2\n", " elif op == '/':\n", " return op1 / op2\n", " elif op == '+':\n", " return op1 + op2\n", " else:\n", " return op1 - op2" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3.0\n" ] } ], "source": [ "print(postfix_eval('7 8 + 3 2 + /'))" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'2 2 7 * +'" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "infix_to_postfix2(\"2 + 2 * 7\")" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "28" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "postfix_eval(infix_to_postfix2(\"( 2 + 2 ) * 7\"))" ] } ], "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.3" } }, "nbformat": 4, "nbformat_minor": 4 }